[논문]그루버 알고리즘 적용을 위한 LEA 양자 회로 최적화

장경배; 김현준; 박재훈; 송경주; 서화정

doi:10.3745/ktccs.2021.10.4.101

그루버 알고리즘 적용을 위한 LEA 양자 회로 최적화
Optimization of LEA Quantum Circuits to Apply Grover's Algorithm 원문보기

정보처리학회논문지. KIPS transactions on computer and communication systems 컴퓨터 및 통신 시스템, v.10 no.4, 2021년, pp.101 - 106

장경배 (한성대학교 IT융합공학부) , 김현준 (한성대학교 IT융합공학부) , 박재훈 (한성대학교 IT융합공학부) , 송경주 (한성대학교 IT융합공학부) , 서화정 (한성대학교 IT융합공학부)

초록
AI-Helper

양자 알고리즘과 양자 컴퓨터는 우리가 현재 사용하고 있는 많은 암호들의 안전성을 깨뜨릴 수 있다. 그루버 알고리즘을 n-bit 보안레벨을 가지는 대칭키 암호에 적용한다면 보안레벨을 (n/2)-bit 까지 낮출 수 있다. 그루버 알고리즘을 적용하기 위해서는 오라클 함수에 대칭키 암호가 양자 회로로 구현되어야 하기 때문에 대상 암호를 양자 회로로 최적화하는 것이 가장 중요하다. 이에 AES 또는 경량 블록암호를 양자 회로로 구현하는 연구들이 최근 활발히 진행되고 있다. 본 논문에서는 국산 경량 블록암호 LEA를 양자 회로로 최적화하여 구현 하였다. 기존의 LEA 양자회로 구현과 비교하여 양자 게이트는 더 많이 사용하였지만, 큐빗을 획기적으로 줄일 수 있었으며 이러한 트레이드오프 문제에 대한 성능 평가를 수행하였다. 마지막으로 제안하는 LEA 양자 회로에 그루버 알고리즘을 적용하기 위한 양자 자원들을 평가하였다.

Abstract ▼ AI-Helper

Quantum algorithms and quantum computers can break the security of many of the ciphers we currently use. If Grover's algorithm is applied to a symmetric key cipher with n-bit security level, the security level can be lowered to (n/2)-bit. In order to apply Grover's algorithm, it is most important to optimize the target cipher as a quantum circuit because the symmetric key cipher must be implemented as a quantum circuit in the oracle function. Accordingly, researches on implementing AES(Advanced Encryption Standard) or lightweight block ciphers as quantum circuits have been actively conducted in recent years. In this paper, korean lightweight block cipher LEA was optimized and implemented as a quantum circuit. Compared to the previous LEA quantum circuit implementation, quantum gates were used more, but qubits were drastically reduced, and performance evaluation was performed for this tradeoff problem. Finally, we evaluated quantum resources for applying Grover's algorithm to the proposed LEA implementation.

주제어

표/그림 (9)

그림 Fig. 1. CNOT Gate
그림 Fig. 2. Toffoli Gate
그림 Fig. 3. Grover's Algorithm Quantum Circuit
그림 Fig. 4. Previous LEA-128 Key Schedule Quantum Circuit
표 Table 1. Previous Implementation Result [11]
그림 Fig. 6. Proposed LEA-128 Quantum Circuit
그림 Fig. 5. Previous LEA-128 Quantum Circuit
표 Table 2. LEA Quantum Circuit Comparison
표 Table 3. Quantum Resources for Applying Grover's Algorithm to LEA

참고문헌 (12)

L. Atzori, A. Iera, and G. Morabito, "The Internet of Things: A survey," Computer Networks, Vol.54, No.15, pp.2787-2805, 2010.

상세보기
D. Hong, J. K. Lee, D. C. Kim, D. Kwon, K. H. Ryu, and D. G. Lee, "LEA: A 128-bit block cipher for fast encryption on common processors," in International Workshop on Information Security Applications, Springer, pp.3-27, 2013.
B. Koo, D. Roh, H. Kim, Y. Jung, D.G. Lee, and D. Kwon, "CHAM: A Family of Lightweight Block Ciphers for Resource-Constrained Devices," in International Conference on Information Security and Cryptology (ICISC'17), 2017.
D. Hong, et al., "HIGHT: A new block cipher suitable for low-resource device," in International Workshop on Cryptographic Hardware and Embedded Systems, Springer, pp.46-59, 2006.
L. K. Grover, "A fast quantum mechanical algorithm for database search," in Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pp.212-219, 1996.
M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt, "Applying Grover's algorithm to AES: quantum resource estimates. Post-Quantum Cryptography," PQCrypto 2016, Springer, pp.29-43, 2016.
B. Langenberg, H. Pham, and R. Steinwandt, "Reducing the cost of implementing AES as a quantum circuit," Technical Report, Cryptology ePrint Archive, Report 2019/854, 2019.
S. Jaques, M. Naehrig, M. Roetteler, and F. Virdia, "Implementing Grover oracles for quantum key search on AES and LowMC," in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, pp.280-310, 2020.
R. Anand, A. Maitra, and S. Mukhopadhyay, "Grover on SIMON," arXiv:2004.10686, 2020.
K. B. Jang, S. J. Choi, H. D. Kwon, and H. J. Seo, "Grover on SPECK : Quantum Resource Estimates," ePrint Archive, Report 2020/640, 2020.
K. B. Jang, S. J. Choi, H. D. Kwon, H. J. Kim, J. H. Park, and H. J. Seo, "Grover on Korean Block Ciphers," Applied Sciences, Vol.10, No.18, pp.6407, 2020.

상세보기
D.S . Steiger, T. Haner, and M. Troyer, "ProjectQ: An Open Source Software Framework for Quantum Computing," arXiv:1612.08091, 2016.

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

연합인증