Closest Vector Problem Based Interactive Proof
Kyung-Hee Lee, DaeHun Nyang · Information Security and Cryptology · 2012
ABSTRACT In this paper, we propose a new closest vector problem based in teractive proof that is useful for authentication. Contribution of this paper is that the proposed protocol does not use a spec ial form of a lattice, but a general lattice, which makes the protocol design very simple and easy to be proved. We prove its security in terms of completeness, soundness, simulatability. Keywords: Closest Vector Problem, Interactive Proof, Authentication Pro tocol I.서 론 래티스(Lattice)는 기하학 그리고 군론에서 의 이산 부분군 (discrete subgroup)으로 기저벡터 (basis vector)의 선형 결합에 의해 생성 (span)된다. 공개키 암호시스템의 개념이 제시되었을 때, 래티스를 암호시스템에 이용하려는 노력이 있었고, 그 결과로 Ajtai 등이 Shortest Vector Problem이 worst case에 안전스템을 제안했고[1], Goldreich 접수일(2012년 7월 18일), 게재확정일(2012년 11월 12일)* 이 논문은 인하대학교의 지원에 의하여 연구되었습니다. 이 논문은 2012년도 정부(교육과학기술부)의 재원으로 한국연구재단의 기초연구사업 지원을 받아 수행 되었습니다.† 주저자, [email protected]‡ 교신저자, [email protected] 등이 Closest Vector Problem에 기반한 공개키 암호시스템과 전자서명 기법을 제안했다[4]. GGH 암호 스킴은 곧 Nguyen 등에 의해 깨졌으며, 서명 기법은 Nyang등에 의해 깨졌다[8,10]. 이후, NTRU 암호기법이 래티스에 기반한 암호시스템으로 설계되었고, 표준화 되었지만, NTRU 전자 서명기법은 안전하지 않은 것으로 알려졌다[12]. NTRU 암호시스템은 타원곡선이나 소인수 기반 암호시스템에 비해 처리속도가 월등히 빠르지만 키 길이가 길다는 점, 그리고 암호문의 길이 대 평문의 길이 비인 expansion factor가 크다는 점이 단점으로 알려져 있다[13]. 이후에 래티스를 암호시스템에 이용하는 연구는 주로 암호 공격 쪽이었고, 설계에는 많은 진전이 이루어지지 않았다.