[논문]부호 기반 양자 내성 암호의 이진 필드 상에서 곱셈 연산 양자 게이트 구현

최승주; 장경배; 권혁동; 서화정

doi:10.6109/jkiice.2020.24.8.1044

부호 기반 양자 내성 암호의 이진 필드 상에서 곱셈 연산 양자 게이트 구현
Implementation of Quantum Gates for Binary Field Multiplication of Code based Post Quantum Cryptography 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.24 no.8, 2020년, pp.1044 - 1051

최승주 (Department of IT Fusion Engineering, Hansung University) , 장경배 (Department of IT Fusion Engineering, Hansung University) , 권혁동 (Department of IT Fusion Engineering, Hansung University) , 서화정 (Department of IT Fusion Engineering, Hansung University)

초록
AI-Helper

양자 컴퓨터의 시대가 점점 현실로 다가오고 있다. 이에 대비해 미국 국립 표준 기술 연구소에서는 양자 알고리즘으로부터 내성이 있는 양자 내성 암호의 표준을 정하기 위해 후보군을 모집했다. 제출된 암호들은 양자 알고리즘으로부터 안전할 것으로 예상이 되지만 알고리즘이 실제 양자 컴퓨터상에서 작동이 되었을 때에도 양자 알고리즘의 공격으로부터 안전한지 검증을 할 필요가 있다. 이에 본 논문에서는 부호 기반 양자 내성 암호의 이진 필드 상에서의 곱셈 연산을 양자 컴퓨터에서 작동될 수 있게 양자 회로로 구현하였고 해당 회로를 최적화 하는 방안에 대하여 설명한다. 구현은 대표적인 부호 기반 암호인 Classic McEliece에서 제시하는 2개의 필드 다항식과 ROLLO에서 제시하는 3개의 필드 다항식에 대하여 일반 곱셈 알고리즘과 카라추바 곱셈 알고리즘으로 구현하였다.

Abstract ▼ AI-Helper

The age of quantum computers is coming soon. In order to prepare for the upcoming future, the National Institute of Standards and Technology has recruited candidates to set standards for post quantum cryptography to establish a future cryptography standard. The submitted ciphers are expected to be safe from quantum algorithm attacks, but it is necessary to verify that the submitted algorithm is safe from quantum attacks using quantum algorithm even when it is actually operated on a quantum computer. Therefore, in this paper, we investigate an efficient quantum gate implementation for binary field multiplication of code based post quantum cryptography to work on quantum computers. We implemented the binary field multiplication for two field polynomials presented by Classic McEliece and three field polynomials presented by ROLLO in generic algorithm and Karatsuba algorithm.

주제어

표/그림 (6)

표 Table. 1 Quantum gates for binary field multiplicatoin
표 Table. 2 Modular reduction for binary multiplication on x¹² + x³ + 1
표 Table. 3 Karatsuba multiplication order on x¹² + x³ + 1
표 Table. 4 Resource count result
그림 Fig. 3 Number of CNOT gate used during binary multiplication
그림 Fig. 4 Number of Toffoli gate used during binary multiplication

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 Classic McEliece[7]와 ROLLO[8]가 제시하는 필드 다항식에 대한 이진 필드 곱셈에 대하여 일반 곱셈 방식과 카라추바 방식에 대한 구현 및 평가한다.

제안 방법

Classic McEliece의 필드 다항식 (x12 + x 3 + 1)과 (x13 + x⁴ + x³ + x + 1) 및 ROLLO의 필드 다항식 (x⁴⁷ + x⁵ + 1), (x⁵³ + x⁶ + x² + x + 1) 그리고 (x⁶⁷ + x⁵ + x² + x + 1) 에대하여도 앞서 설명한 두 가지 곱셈 방식 모두를 적용하여 구현하였다.
해당 논문의 연산 방식은 먼저 일반 적인 곱셈 연산을 통해 모듈러 연산을 취해주어야 하는 차수가 높은 값들을 먼저 도출해낸다. 그 후 해당 값들에 대한 모듈러 연산을 취해주고 차수가 낮아 모듈러 연산이 필요 없는 부분들에 대한 곱셈 연산을 진행하는 방식을 사용한다. 이러한 방식을 통해 빠른 이진 필드 곱셈 연산이 가능하다.
2장에서 언급하였던 것과 같이 현재 IBM ProjectQ는 개선단계에 있는 중이기에 연산할 수 있는 큐비트의 수에 한계가 있다. 그렇기 때문에 IBM ProjectQ에서 연산할 수 있는 필드 다항식 값들에 대해서는 ProjectQ 에서 연산을 진행하였고 큐비트 수가 많아 작동될 수 없는 다항식 값들에 대해서는 동일한 연산을 C 언어로 구현하여 이진 필드 곱셈 연산 결과 값을 확인하고 사용되는 게이트 자원의 수를 측정했다. 해당 결과는 표 4에 정리가 되어있고 CNOT 게이트와 토폴리(Toffoli) 게이트 각각 의사 용량에 대한 그래프는 그림 3과 그림 4에 나와 있다.
이에 본 논문에서는 실제 양자 컴퓨터상에서 작동될 수 있게 양자 내성 암호 중 부호 기반 암호들의 이진 필드 곱셈 연산을 일반 곱셈 방식과 카라추바 곱셈 방식으로 IBM PorjectQ 에서 양자 회로로 구현하여 각 방식의 자원 사용량에 대해 비교 분석하였다. 또한 일반 곱셈 연산의 모듈러 연산 횟수를 최적화 하였다.
이와 같은 양자 내성 암호들에 대한 제대로 된 보안 강도를 알기 위해서는 실제 양자 컴퓨터상에서 작동될 수 있게 구현하여 안전성을 확인할 필요가 있다. 이를 위해서 본 논문에서는 가장 오랫동안 보안성이 보장되었던 부호 기반 암호 중 하나인 Classic McEliece의이진 필드 곱셈 연산을 IBM ProjectQ를 이용하여 양자 컴퓨터에서 동작될 수 있게 양자 회로로 구현하였으며 또 다른 부호 기반 양자 내성 암호 후보인 ROLLO의 곱셈 연산 또한 구현하였다.
이와 같은 현상은 x¹과 x⁴사이에서도 볼 수 있다(x¹³, x²²). 이를 이용해 본 논문에서는 먼저 x⁰과 x¹에 대한 연산을 진행하고 해당 결과 값을 x³과 x⁴를 연산할 때 사용하여 x³ 과 x⁴를 연산하기 위해 각각 3번의 연산이 필요한 부분을 2번으로 줄였다.
대비 또한 동시에 준비되고 있다. 이에 본 논문에서는 실제 양자 컴퓨터상에서 작동될 수 있게 양자 내성 암호 중 부호 기반 암호들의 이진 필드 곱셈 연산을 일반 곱셈 방식과 카라추바 곱셈 방식으로 IBM PorjectQ 에서 양자 회로로 구현하여 각 방식의 자원 사용량에 대해 비교 분석하였다. 또한 일반 곱셈 연산의 모듈러 연산 횟수를 최적화 하였다.
이진 필드 곱셈에 대한 구현은 Classic McEliece에서 제시하는 필드 다항식 (x¹² + x³ + 1)과 (x¹³ + x⁴ + x³ + x + 1) 그리고 ROLLO에서 제시하는 필드 다항식 (x⁴⁷ + x⁵ + 1), (x⁵³ + x⁶ + x² + x + 1) 그리고 (x⁶⁷ + x⁵ + x² + x + 1)에 대하여 일반 곱셈 방식과 카라추바 방식으로 진행하였다. 구현에 대한 구체적인 설명은 Classic McEliece 의 필드 다항식 (x¹² + x³ + 1)에 대하여만 설명한다.

대상 데이터

이에 대비하기 위하여 미국 국립 표준 기술 연구소(NIST; National Institute of Standards and Technology)에서는 양자 내성 암호 표준 후보군을 선출하기 위한 공모전을 진행하고 있다. 후보군으로는 격자, 다변수 다항식, 타원 곡선, 해시 기반 암호 등 다양한 암호들이 제출되었는데 이들 중 가장 오랫동안 보안상으로 치명적인 취약점이 없었던 부호 기반암호 또한 제출되었다. 제출된 암호들은 NIST에서 요구하는 양자 컴퓨터로부터도 안전한 암호 알고리즘이 되기 위한 조건들에 부합되기 위해 계속해서 개선되고 있다.

성능/효과

그러나 (x¹³ + x⁴ + x³ + x + 1), (x⁵³ + x⁶ + x² + x + 1) 그리고 (x⁶⁷ + x⁵ + x² + x + 1)을 연산함에 있어 다항식의 항이 많아 추가적인 큐비트가 필요하다. 하여 본 논문의 4장에 나오는 표 3에 나오는 일반 곱셈 연산 시 필요한 큐비트의 개수를 확인하면 x¹²와 x⁴⁷은 각각 정확히 필드 다항식 차수의 3배만큼의 큐비트가 사용되는 것을 확인할 수 있다. 그에 반해 x¹³, x⁵³와 x⁶⁷과 같은 경우 필드 다항식 차수의 3배 만큼에 추가적인 큐비트가 더 필요한 것을 볼 수가 있다.
일반적으로 두 n자리 수의 곱셈은 n²에 비례하는 횟수의 연산이 필요한데 카라추바 알고리즘을 사용하면 이를 n^{log2^3} 회로 줄이는 것이 가능하다. 해당 알고리즘을 양자 내성 암호의 이진 필드 곱셈 방식에 적용을 하여 연산 최적화가 가능하다. 그러나 카라추바를 적용하기 위해서는 일반적인 곱셈 방식에 비해 추가적으로 발생되는 중간 결과 값들을 저장하기 위해 큐비트를 더 할당해야 한다는 단점이 있다.

후속연구

향후 연구로는 카라추바 알고리즘의 큐비트 사용량을 줄일 수 있는 방안을 연구할 예정이며 전체적인 이진 필드 곱셈 연산에서 사용되는 게이트 수를 줄일 수 있는 방안을 연구를 할 예정이다.

참고문헌 (10)

R. Feynman, "Simulating Physics with Computers," International Journal of Theoretical Physics, 21, 467, 1982.

상세보기
Join Extra Crunch. IBM unveils its first commercial quantum computer [Internet]. Available: https://techcrunch.com/2019/01/08/ibm-unveils-its-first-commercial-quantum-computer/.
A. G. Aruna, K. H. Vani, C. Sathya, and R. Sowndarya Meena, "A Study on Reversible Logic Gates of Quantum Computing," International Journal of Computer Science and Information Technologies, vol. 7, no. 1, pp. 427-432. 2016.
D. Cheung, D. Maslov, J. Mathew, and D. K. Pradhan, "On the design and optimization of a quantum polynomial-time attack on elliptic curve cryptography," In Workshop on Quantum Computation, Communication, and Cryptography, pp. 96-104, 2008.
S. Kepley, and R. Steinwandt, "Quantum circuits for multiplication with subquadratic gate count," Quantum Information Processing, vol. 14, no. 7, pp. 2373-2386, 2015.

상세보기
D. S. Steiger, T. Haner, and M. Troyer, "ProjectQ: An Open Source Software Framework for Quantum Computing. Quantum," ResearchGate, 2. 10.22331/q-2018-01-31-49, 2016.

상세보기
D. J. Bernstein, T. Chou, T. Lange, I. V. Maurich, R. Misoczki, R. Niederhagen, and J. Szefer, "Classic McEliece: conservative code-based cryptography," NIST submissions, 2017.
C. A. Melchor, N. Aragon, and M. Bardet, "ROLLO: Rank-Ouroboros, Lake & Locker," NIST submissions, 2019.
I. V. Hoof, "Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count," arXiv preprint arXiv:1910.02849, 2019.
V. Shende, and I. L. Markov, "On the CNOT-cost of TOFFOLI gates," Quantum Information and Computation, 2008.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증