Goldreich-Goldwasser-Halevi 전자서명의 선택 평문 공격
Chosen Message Attack Against Goldreich-Goldwasser-Halevi's Lattice Based Signature Scheme
0
조회
0
다운로드
1
인용
0
참고문헌
초록
이 논문에서는 Crypto97에 발표된 잘 알려진 lattice 문제에 기반한 Goldreich-Goldwasser-Halevi(GGH)의 전자 서명을 암호해독한다. GGH의 서명방법에 선택 평문공격을 수행하고 제안하는 공격방법에 취약함을 보인다. 암호해독 방법에서는 서로 선형 독립적인 n개의 lattice 점을 모아서 원래 lattice의 sub-lattice를 생성하는 새로운 basis를 생성한다. 이 sub-lattice가 유효한 서명을 생성하는데 사용될 수 있음을 보인다. 이 공격방법의 유효성을 실험을 통해서 보이고, 마지막으로 비밀키를 생성하는데 사용되는 cube-like parameter가 안전성에 좋지 않은 영향을 미침을 보인다.
Abstract
The Goldreich-Goldwasser-Halevi(GGH)'s signature scheme from Crypto '97 is cryptanalyzed, which is based on the well-known lattice problem. We mount a chosen message attack on the signature scheme, and show the signature scheme is vulnerable to the attack. We collects n lattice points that are linearly independent each other, and constructs a new basis that generates a sub-lattice of the original lattice. The sub-lattice is shown to be sufficient to generate a valid signature. Empirical results are presented to show the effectiveness of the attack. Finally, we show that the cube-like parameter used for the private-key generation is harmful to the security of the scheme.
참고문헌 (7)
- "Generating hard instances of lattice problems", pp.99~108 (1996)
- "A public-key cryptosystem with worst-case", average- case equivalence, 1997, 284~293
- "Public-key cryptosystems from lattice reduction problems", pp.112~131 (1997)
- "Factoring polynomials with rational coefficients", pp.515~534 (1982)
- "Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97", pp.112~131 (1999)
- "Another NP-complete problem and the complexity of computing short vectors in a lattice University of Amsterdam" (1981)
- "A C++ Library For Computational Number Theory Available from http"