[논문]양자 컴퓨팅 환경에 안전한 NTRU 기반 인증 및 키 분배 프로토콜

정성하; 이경근; 박영호

doi:10.9717/kmms.2017.20.8.1321

양자 컴퓨팅 환경에 안전한 NTRU 기반 인증 및 키 분배 프로토콜
Secure NTRU-based Authentication and Key Distribution Protocol in Quantum Computing Environments 원문보기

멀티미디어학회논문지 = Journal of Korea Multimedia Society, v.20 no.8, 2017년, pp.1321 - 1329

정성하 (School of Electronics, Kyungpook National University) , 이경근 (Samsung Electronics Inc.) , 박영호 (School of Electronics, Kyungpook National University)

Abstract ▼ AI-Helper

A quantum computer, based on quantum mechanics, is a paradigm of information processing that can show remarkable possibilities of exponentially improved information processing. This paradigm can be solved in a short time by calculating factoring problem and discrete logarithm problem that are typically used in public key cryptosystems such as RSA(Rivest-Shamir-Adleman) and ECC(Elliptic Curve Cryptography). In 2013, Lei et al. proposed a secure NTRU-based key distribution protocol for quantum computing. However, Lei et al. protocol was vulnerable to man-in-the-middle attacks. In this paper, we propose a NTRU(N-the truncated polynomial ring) key distribution protocol with mutual authentication only using NTRU convolution multiplication operation in order to maintain the security for quantum computing. The proposed protocol is resistant to quantum computing attacks. It is also provided a secure key distribution from various attacks such as man-in-the middle attack and replay attack.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문은 Lei 등의 NTRU 키 분배 프로토콜의 취약점인 중간자 공격을 양자 컴퓨팅에 보안을 유지하기 위해 NTRU 컨볼루션 곱셈 연산만을 사용하여 상인증 단계를 추가하므로 중간자 공격과 양자 컴퓨 팅에 안전한 프로토콜로 개선하였다. 이러한 NTRU 알고리즘은 현재 널리 사용되고 있는 공개키 암호 알고리즘인 RSA나 ECC 보다 빠른 연산으로 컴퓨터 환경만이 아닌 저사양 환경으로 스마트카드, NFC 등에도 효과적으로 적용될 수 있다.
본 논문은 Lei 등의 프로토콜에 취약점인 중간자 공격으로 인해 비밀키가 노출되는 문제를 해결하기 위해 Park 등이 제안한 NTRU 영지식 대화형 증명 방식의 취약점을 보완하여 양방향 상호인증 단계를 제안한다. 제안한 프로토콜은 양방향 상호인증을 통해 중간자 공격에 안전하며 키 분배 프로토콜에 추가 적으로 발생될 수 있는 제사용 공격, 세션 키 노출 공격 등에도 안전하다.

제안 방법

본 논문에서 제안한 방식은 다음 informal analysis를 이용하여 안전성을 분석하였으며 Table 2와 같다.
본 논문에서 제안한 방식은 Lei 등의 NTRU 키분배 프로토콜의 장점을 그대로 보존하면서 Park 등의 NTRU 영지식 방식의 취약한 부분을 보완 후 응용하여 양방향 인증과정을 추가하므로 중간자 공격에 취약함을 보완하였다. 제안된 방식에서는 Alice와 Bob이 각각 임의의 다항식 r을 통해 x를 생성하여 상호인증을 하므로 중간자 공격을 방지 하였다.
Lei 등의 키 분배 방식은 인증 단계가 존재하지 않고 Park 등의 인증 방식은 단방향 인증만 가능하여 중간자 공격에 취약하다. 제안된 방식은 Lei 등과 Park 등의 방식에 비해 많은 연산을 필요로 하지만두 방식의 취약점을 방어하기 위해 양방향 인증이 추가된 키 분배 방식이다. 또한 컨볼루션 곱셈을 활용한 NTRU는 RSA에 비해 암호화 과정에서 5.
제안한 방식은 Lei 등과 Park 등의 방식의 취약점을 방어하기 위해 상호인증 단계를 추가하였다. 상호 간에 만들어낸 x,y와 공개키 h를 교환하여 Alice와 Bob이 각각 y_B∗ h_B=x_B ∗ x_A와 y_A ∗ h_A=x_A ∗ x_B를 계산하면 g_A ∗ r_A ∗ g_B ∗ r_B=g_A ∗ r_A ∗ g_B ∗ r_B와 같은 식이 성립되어 상호인증을 제공하며 x와 y는 사용 자의 개인키를 활용하여 계산되므로 공격자는 상호인증에 사용되는 정보를 알아내는 것은 불가능하다.
기밀성은 허락 되지 않은 사용자 또는 객체가 정보의 내용을 알 수 없도록 하는 것이다. 제안한 방식은 NTRU 기반 공개키를 사용하므로 데이터의 기밀성을 제공하며 세션키가 노출되어도 세션마다 임의로 생성되는 f와 r로 인해 통신상 기밀성을 제공한다.

이론/모형

양자 컴퓨팅 공격에 안전하다고 알려진 암호는 Code, Lattice, Hash 및 Multivariate 기반의 4가지 암호방식이 있으며 본 논문에서는 격자(Lattice) 기반 암호의 표준으로 채택된 NTRU 공개키 암호를 사용한다. NTRU는 1996년 Jeffrey Hoffstein[4] 등에 의해 제안된 격자 기반 공개키 암호체계로서 기존의 공개키 암호와 비교하여 동일한 안전성을 제공하면서 암호화 및 복호화 속도가 빠르며 양자 연산 알고리즘을 이용한 공격에도 안전하다는 이점이 있다[5].

성능/효과

본 논문에서 제안한 방식은 Lei 등의 NTRU 키분배 프로토콜의 장점을 그대로 보존하면서 Park 등의 NTRU 영지식 방식의 취약한 부분을 보완 후 응용하여 양방향 인증과정을 추가하므로 중간자 공격에 취약함을 보완하였다. 제안된 방식에서는 Alice와 Bob이 각각 임의의 다항식 r을 통해 x를 생성하여 상호인증을 하므로 중간자 공격을 방지 하였다.
허락 되지 않은 사용자 또는 객체가 정보를 함부로 수정할 수 없도록 하는 것이다. 제안한 방식은 NTRUSign을 통해 메시지의 서명값을 생성하여 전달하므로 위ㆍ변조가 되더라도 검증과정을 통해 확인이 가능하며 또한 상호인증 단계에서 x,y와 공개키 h를 사용하여 인증과정을 거치므로 무결성을 제공한다.
재사용 공격은 사용자가 사용한 정보를 공격자가 도청으로 가로채 다시 사용하는 공격이다. 제안한 방식은 매 세션마다 임의로 생성되는 r을 사용하여 상호인증에 사용되는 x를 계산하므로 한번 사용한 정보를 재사용하여 인증하는 것은 불가능하다.
본 논문은 Lei 등의 프로토콜에 취약점인 중간자 공격으로 인해 비밀키가 노출되는 문제를 해결하기 위해 Park 등이 제안한 NTRU 영지식 대화형 증명 방식의 취약점을 보완하여 양방향 상호인증 단계를 제안한다. 제안한 프로토콜은 양방향 상호인증을 통해 중간자 공격에 안전하며 키 분배 프로토콜에 추가 적으로 발생될 수 있는 제사용 공격, 세션 키 노출 공격 등에도 안전하다.
하지만 제안한 방식은 사용 자간에 x, y와 공개키 h를 교환하여 yB ∗ hB=xB ∗ xA, yA ∗ hA=xA ∗ xB를 계산하여 상호인증을 하게 되므로 중간에서 값이 위ㆍ변조 되었는지 확인이 가능하여 중간자 공격이 불가능하다.

질의응답

핵심어	질문	논문에서 추출한 답변
	NTRU 암호는 누구에 의해 제안되었는가?	NTRU 암호는 1996년 Jeffrey Hoffstein[4] 등에 의해 제안되었으며 격자 문제를 기반으로 하는 공개키 암호 체계로 기본 연산은 다항식 환(Polynomial rings)상에서 이루어진다. 현재 널리 사용되는 공개키 암호인 RSA, ECC 등과 비교하여 동일한 안정성을 제공하면서 암·복호화 속도가 빠르며 양자 컴퓨팅 공격에 내성이 있다는 이점[11,12]을 갖는다.
	공개키 암호는 어떤것이 있는가?	NTRU 암호는 1996년 Jeffrey Hoffstein[4] 등에 의해 제안되었으며 격자 문제를 기반으로 하는 공개키 암호 체계로 기본 연산은 다항식 환(Polynomial rings)상에서 이루어진다. 현재 널리 사용되는 공개키 암호인 RSA, ECC 등과 비교하여 동일한 안정성을 제공하면서 암·복호화 속도가 빠르며 양자 컴퓨팅 공격에 내성이 있다는 이점[11,12]을 갖는다.
	양자 컴퓨팅 환경에서 효과적인 암호 알고리즘은?	양자 컴퓨팅 공격에 안전하다고 알려진 암호는 Code, Lattice, Hash 및 Multivariate 기반의 4가지 암호방식이 있으며 본 논문에서는 격자(Lattice) 기반 암호의 표준으로 채택된 NTRU 공개키 암호를 사용한다. NTRU는 1996년 Jeffrey Hoffstein[4] 등에 의해 제안된 격자 기반 공개키 암호체계로서 기존의 공개키 암호와 비교하여 동일한 안전성을 제공하면서 암호화 및 복호화 속도가 빠르며 양자 연산 알고리즘을 이용한 공격에도 안전하다는 이점이 있다[5].

참고문헌 (12)

R.P. Feynman, "Simulating Pysics with Computers," International Journal of Theoretical Physics, Vol. 21, No. 6-7, pp. 467-488, 1982.

상세보기
P.W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring," Proceedings of 35th Annual Symposium on Foundations of Computer Science and IEEE Computer Society, pp. 124-134, 1994.
S.Y. Lee, K.S. Park, Y.H. Park, and Y.H. Park, “Symmetric Key-Based Remote User Authentication Scheme with Forward Secrecy,” Journal of Korea Multimedia Society, Vol. 19, No. 3, pp. 585-594, 2016.

원문보기 상세보기
J. Hoffstein, J. Pipher, and J.H. Silverman, "NTRU: A Ring-Based Public Key Cryptosystem," Algorithmic Number Theory and Lecture Notes in Computer Science, Vol. 1423, pp. 267-288, 1998.
IEEE, IEEE P1363.1 Draft 10: Draft Standard for Public Key Cryptographic Techniques Based on Hard Problems over Lattices, International Association for Cryptologic Research Eprint archive, 2008.
X. Lei and X. Liao, "NTRU-KE: A Lattice-based Public Key Exchange Protocol," IACR Cryptology ePrint Archive 2013/ 718, 2013.
S.W. Park and I.Y. Lee, "Anonymous Authentication Scheme Based on NTRU for the Protection of Payment Information in NFC Mobile Environment," Journal of Information Processing Systems, Vol. 9, No. 3, pp. 461-476, 2013.

원문보기 상세보기
S.W. Park and I.Y. Lee, “Authentication Scheme Based on NTRU for the Protection of Payment Information in NFC Mobile Environment,” Korea Information Processing Society Transactions on Computer and Communication Systems, Vol. 2, No. 3, pp. 133-142, 2013.
M.R. Valluri, Cryptanalysis of Xinyu et al.'s NTRU-Lattice Based Key Exchange Protocol, https://arxiv.org/abs/1611.08686v1, 2016.
Y.S. Jheng, "Security Analysis of a NTRU-based Mutual Authentication Scheme," Proceeding of Asia-Pacific Network Operations and Management Symposium, pp. 3, 2016.
ETSI, Quantum Safe Cryptography and Security, ISBN No. 979-10-92620-09-0, 2015.
NIST, Report on Post-Quantum Cryptography, NISTIR 8105, 2016.

저자의 다른 논문 :

LOADING...

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증