We provide an alternative scheme for lattice-based digital signature without using hash-and-sign paradigm of C. Gentry, C. Peikert, and V. Vaikuntanathan (STOC 2008). Our signature scheme basically follows the methodology of ``rejection sampling" of V. Lyubashevsky and "Fiat-Shamir transformation". Not only the sizes of public key, secret key, and signature are quite remarkable but also the signing step is relatively simple while the hash-and-sign paradigm requires a very large trapdoor matrix. We then provide the security analysis of our scheme based on Learning With Errors and analyze the appropriate parameters.
2008년에 C. Gentry, C. Peikert 및 V. Vaikuntanathan의 놀랄만한 연구 결과로 '해시 및 서명' 방식을 이용한 최초의 구현 가능한 전자 서명 스킴이 제시되었고, 이 연구를 바탕으로 수많은 연구 결과들이 발표된다. 하지만 이 스킴은 상대적으로 큰 덧문(trapdoor) 함수를 요구하기에 사전 계산 과정이 많이 요구되며 실질적인 효율성 또한 낮다. 본 논문에서는 덧문 함수를 이용하지 않는 `피아트-샤미르 변환' 기법을 바탕으로 새로운 전자 서명 기법을 소개한다. 기본적으로 피아트-샤미르 변환 기법을 처음 격자 암호에 적용한 V. Lyubashevsky의 논문을 따라가나, 기반으로 하는 격자 난제를 SIS가 아닌 LWE로 바꾸어 더욱 높은 효율을 얻어내는 데에 중점을 두고자 한다.
