Grover 알고리즘 공격 비용 추정을 통한 DES에 대한 양자 암호 분석
Quantum Cryptanalysis for DES Through Attack Cost Estimation of Grover's Algorithm
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Brute force 공격을 가속화 시키는 Grover 알고리즘은 대칭키 암호의 키 복구에 적용 가능하며, NIST에서는 대칭키 암호에 대한 Grover 공격 비용을 양자 후 보안 강도 추정에 활용하고 있다. 본 논문에서는 DES를 양자 회로로 최적화 구현하여 Grover 알고리즘 공격 비용을 추정한다. NIST에서는 128, 192, 256-bit 키를 사용하는 대칭키 암호에 대해 AES의 공격 비용을 기준으로 양자 후 보안 강도를 추정하고 있다. DES에 대해 추정한 공격 비용은 DES가 양자 컴퓨터의 공격으로부터 어느 정도의 내성을 가지고 있는지 분석해볼 수 있다. 현재 64-bit 키를 사용하는 대칭키 암호들에 대한 양자 후 보안 지표가 아직 존재하지 않기 때문에 본 논문에서 추정한 64-bit 키를 사용하는 DES에 대한 Grover 공격 비용이 기준으로 활용될 수 있다. 제안하는 DES의 양자 회로 구현 적합성 및 공격 비용 분석에는 양자 프로그래밍 툴인 ProjectQ가 사용되었다.
Abstract
The Grover algorithm, which accelerates the brute force attack, is applicable to key recovery of symmetric key cryptography, and NIST uses the Grover attack cost for symmetric key cryptography to estimate the post-quantum security strength. In this paper, we estimate the attack cost of Grover’s algorithm by implementing DES as a quantum circuit. NIST estimates the post-quantum security strength based on the attack cost of AES for symmetric key cryptography using 128, 192, and 256-bit keys. The estimated attack cost for DES can be analyzed to see how resistant DES is to attacks from quantum computers. Currently, since there is no post-quantum security index for symmetric key ciphers using 64-bit keys, the Grover attack cost for DES using 64-bit keys estimated in this paper can be used as a standard. ProjectQ, a quantum programming tool, was used to analyze the suitability and attack cost of the quantum circuit implementation of the proposed DES.
참고문헌 (12)
- L. K. Grover, "A fast quantum mechanical algorithm for database search", Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp.212~219 (1996)
- M. Gras, "Applying Grover’s algorithm to AES:quantum resource estimates", Post-Quantum Cryptography, PQCrypto'16, 9606, pp.29~43 (2016)
- R. Anand, "Grover on SIMON", arXiv:2004.10686, ~ (2020)
- K. B. Jang, "Efficient Implementation of PRESENT and GIFT on Quantum Computers", Applied Sciences, 11(11), pp.4776~ (2021)
- K. B. Jang, "Grover on PIPO", Electronics, 10(10), pp.1194~ (2021)
- K. B. Jang, "Grover on Korean Block Ciphers", Applied Sciences, 10(18), pp.6407~ (2020)
- 장경배, "그루버 알고리즘 적용을 위한 LEA 양자 회로 최적화", 정보처리학회논문지. 컴퓨터 및 통신시스템, 10(4), pp.101~106 (2021), 한국정보처리학회
- "Submission requirements and evaluation criteria for the post-quantum cryptography standardization process"[URL]
- [URL]
- M. Boyer, "Tight bounds on quantum searching", arXiv:quant-ph, 1996
- Reducing the Gate Count of Bitslice DES, "M. Kwan", Cryptology ePrint Archive, ~, pp.Report 2000 (2000), 051
- M. Amy, "A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32(6), pp.818~830 (2013)