Analysis of Error Terms of Signatures Based on Learning with Errors

详细信息    查看全文

• 关键词：Lattice ; Digital signature ; Learning with errors ; LWE ; Discrete random variable ; Discrete Gaussian distribution
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10157
• 期：1
• 页码：75-97
• 丛书名：Information Security and Cryptology ?ICISC 2016
• ISBN：978-3-319-53177-9
• 卷排序：10157

文摘

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.