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.
Lyubashevsky는 SIS(short integer solution) 문제를 기반으로 하는 격자 기반 전자 서명 스킴을 제시하였고, Bai와 Galbraith는 그가 제시한 스킴에 LWE(learning with errors) 문제를 추가하여 더 크기가 작은 서명을 가질 수 있다는 것을 보였다 [12][4]. 하지만 Bai와 Galbraith의 스킴에서는 기존 Lyubashevsky의 스킴에 거부 과정을 추가했으며, 그에 따라 서명 과정의 승인 확률이 낮아졌다. 이 논문에서는 Bai와 Galbraith의 키 생성 과정에서 거부 과정이 필요 없다는 것을 수학적으로 보인다. 이를 이용하여 수정된 스킴을 제안하고, 구현한 결과를 제공한다. 결과를 통해 우리의 스킴이 Bai와 Galbraith의 스킴보다 서명 과정의 속도가 약 2배가량 빠르다는 것을 알 수 있다.
