Analysis of error terms of signatures based on learning with errors

Abstract

Lyubashevsky proposed a lattice-based digital signature scheme based on short integer solution (SIS) problem without using trapdoor matrices [12]. Bai and Galbraith showed that the hard problem in Lyubashevsky's scheme can be changed from SIS to SIS and learning with errors (LWE) [4]. Using this change, they could compress the signatures. But Bai and Galbraith's scheme had some additional rejection processes on its algorithms. These rejection processes decreased the acceptance rate of the signing algorithm. We showed mathematically that the rejection process in key generation algorithm of [4] is not necessary. Using this fact, we suggested a scheme modified from [4]'s scheme, and doubled the acceptance rate of the signing algorithm. Furthermore, our implementation results show that our scheme is two times faster than that of [4] on similar parameter settings.