SIMEC 경량암호에 대한 양자회로 구현 및 Post-Quantum 보안 강도 평가

송경주,장경배,심민주,서화정,Song Gyeong Ju,Jang Kyung Bae,Sim Min Joo,Seo Hwa Jeong 한국정보처리학회 2023 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.12 No.6

Grover 양자 알고리즘은 brute-force attack 가속화로 대칭키 암호의 보안 강도를 크게 감소시키므로 기존 블록 암호가 양자 컴퓨터에 안전하지 않을 것이라 예상한다. 따라서 대상 암호에 대한 양자회로 구현을 통해 Post-quantum 보안 강도를 확인하여 대규모 양자 컴퓨터 시대에 대비할 수 있다. 본 논문에서는 모든 SIMECK 경량 암호군에 대해 양자 자원(큐비트, 양자 게이트)을 최소화 한 기법으로 설계된 최적의 양자회로 구현 결과를 제시하고 각 함수별 양자 회로 동작을 설명한다. 마지막으로 제안된 SIMECK 양자회로에 대한 양자자원 추정 결과를 SIMON 양자 회로 결과와 비교하고 Grover 공격 비용을 계산하여 SIMECK 경량암호의 Post-quantum 보안 강도를 평가한다. Post-quantum 보안 강도 평가 결과 모든 SIMECK 경량 암호군이 NIST 보안 강도에 도달하지 못했다. 따라서 대규모 양자 컴퓨터 등장 시 SIMECK 암호의 안전성이 불명확하다고 예상하며 이에 대해 본 논문에서는 보안 강도를 높이기 위한 방안으로 블록사이즈 및 라운드 수와 키 길이를 증가시키는 것이 적합하다고 판단한다. Block cipher is not expected to be safe for quantum computer, as Grover's algorithm reduces the security strength by accelerating brute-force attacks on symmetric key ciphers. So it is necessary to check the post-quantum security strength by implementing quantum circuit for the target cipher. In this paper, we propose the optimal quantum circuit implementation result designed as a technique to minimize the use of quantum resources (qubits, quantum gates) for SIMECK lightweight cryptography, and explain the operation of each quantum circuit. The implemented SIMECK quantum circuit is used to check the estimation result of quantum resources and calculate the Grover attack cost. Finally, the post-quantum strength of SIMECK lightweight cryptography is evaluated. As a result of post-quantum security strength evaluation, all SIMECK family cipher failed to reach NIST security strength. Therefore, it is expected that the safety of SIMECK cipher is unclear when large-scale quantum computers appear. About this, it is judged that it would be appropriate to increase the block size, the number of rounds, and the key length to increase the security strength.

AES 양자 회로 구현 동향

장경배 ( Kyung-bae Jang ),김현지 ( Hyun-ji Kim ),송경주 ( Gyeong-ju Song ),양유진 ( Yu-jin Yang ),임세진 ( Se-jin Lim ),서화정 ( Hwa-jeong Seo ) 한국정보처리학회 2022 한국정보처리학회 학술대회논문집 Vol.29 No.1

특정 문제를 효율적으로 모델링하고 해결할 수 있는 자체적인 특성을 가지고 있는 양자 컴퓨터는 다양한 컴퓨팅 분야에서 강세를 보일 것으로 기대된다. 이러한 양자 컴퓨터는 가까운 미래에 암호학계에 다가올 가장 큰 위협으로 여겨지고 있다. 공개키 암호와는 달리 대칭키 암호에서 기반하고 있는 문제들은 양자 컴퓨터에 대해 아직은 안전할 것으로 여겨지지만, 안전한 양자 후 보안 시스템을 구축하기 위해 이에 대한 파급력을 확인하는 연구들이 수행되고 있다. NIST는 대칭키 암호 AES에 대한 상대적인 양자 공격 비용에 따라 양자 후 보안 강도를 추정하고 있으며, 이에 본 논문에서는 AES에 대한 양자 회로를 구현하고 공격 비용을 추정하는 다양한 연구들에 대해 살펴본다.

닥나무 인피섬유와 한지의 원산지 판별모델 개발을 위한 NIR 및 MIR 스펙트럼 데이터의 PLS-DA 적용

장경주(Kyung-Ju Jang),정소윤(So-Yoon Jung),고인희(In-Hee Go),정선화(Seon-Hwa Jeong) 한국분석과학회 2019 분석과학 Vol.32 No.1

Grover 알고리즘 공격 비용 추정을 통한 DES에 대한 양자 암호 분석

장경배(Kyung-bae Jang),김현지(Hyun-Ji Kim),송경주(Gyeong-Ju Song),심민주(Min-Ju Sim),엄시우(Eum-Si Woo),서화정(Hwa-Jeong Seo) 한국정보보호학회 2021 정보보호학회논문지 Vol.31 No.6

Brute force 공격을 가속화 시키는 Grover 알고리즘은 대칭키 암호의 키 복구에 적용 가능하며, NIST에서는 대칭키 암호에 대한 Grover 공격 비용을 양자 후 보안 강도 추정에 활용하고 있다. 본 논문에서는 DES를 양자 회로로 최적화 구현하여 Grover 알고리즘 공격 비용을 추정한다. NIST에서는 128, 192, 256-bit 키를 사용하는 대칭키 암호에 대해 AES의 공격 비용을 기준으로 양자 후 보안 강도를 추정하고 있다. DES에 대해 추정한 공격비용은 DES가 양자 컴퓨터의 공격으로부터 어느 정도의 내성을 가지고 있는지 분석해볼 수 있다. 현재 64-bit 키를 사용하는 대칭키 암호들에 대한 양자 후 보안 지표가 아직 존재하지 않기 때문에 본 논문에서 추정한 64-bit 키를 사용하는 DES에 대한 Grover 공격 비용이 기준으로 활용될 수 있다. 제안하는 DES의 양자 회로 구현 적합성 및 공격 비용 분석에는 양자 프로그래밍 툴인 ProjectQ가 사용되었다. 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.

SPECK 양자 회로 최적화를 통한 양자 후 보안 강도 평가

장경배 ( Kyung-bae Jang ),엄시우 ( Si-woo Eum ),송경주 ( Gyeong-ju Song ),양유진 ( Yu-jin Yang ),서화정 ( Hwa-jeong Seo ) 한국정보처리학회 2021 한국정보처리학회 학술대회논문집 Vol.28 No.2

양자 알고리즘이 수행 가능한 양자 컴퓨터는 기존 암호 시스템의 보안성을 낮추거나 깨뜨릴 수 있다. 이에 양자 컴퓨터의 공격 관점에서 기존 암호 시스템의 보안성을 재평가하는 연구들이 활발히 수행되고 있다. NIST는 대칭키 암호 시스템에 대한 양자 후 보안 강도에 평가에 Grover 알고리즘의 적용 비용을 채택하고 있다. Grover 알고리즘이 대칭키 암호 시스템의 보안성을 절반으로 줄일 수 있는 시점에서 중요한 건 공격 비용이다. 본 논문에서는 경량블록암호 SPECK 양자 회로 최적화 구현을 제시한다. ARX 구조의 SPECK에 대해 최적의 양자 덧셈기를 채택하고 병렬 덧셈을 수행한다. 그 결과, 최신 구현물과 비교하여 depth 측면에서 56%의 성능향상을 제공한다. 최종적으로, 제시하는 SPECK 양자 회로를 기반으로 Grover 알고리즘 적용 비용을 추정하고 양자 후 보안 강도를 평가한다.

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

장경배 ( Kyung Bae Jang ),김현준 ( Hyun Jun Kim ),박재훈 ( Jae Hoon Park ),송경주 ( Gyeung Ju Song ),서화정 ( Hwa Jeong Seo ) 한국정보처리학회 2021 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.10 No.4

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

해시함수 LSH 양자 회로 최적화를 통한 그루버 알고리즘 적용 자원 추정

송경주(Gyeong-ju Song),장경배(Kyung-bae Jang),서화정(Hwa-jeong Seo) 한국정보보호학회 2021 정보보호학회논문지 Vol.31 No.3

최근에는 양자 컴퓨터의 빠른 연산의 장점이 알려지면서 큐비트를 활용한 양자회로에 대한 관심이 높아지고 있다. 그루버 알고리즘은 n-bit의 보안 레벨의 대칭키 암호와 해시 함수를 n/2-bit 보안 레벨까지 낮출 수 있는 양자 알고리즘이다. 그루버 알고리즘은 양자 컴퓨터상에서 동작하기 때문에 적용 대상이 되는 대칭키 암호와 해시함수는 양자 회로로 구현되어야 한다. 이러한 연구 동기로, 최근 들어 대칭키 암호 또는 해시 함수를 양자 회로로 구현하는 연구들이 활발히 수행되고 있다. 하지만 현재는 큐비트의 수가 제한적인 상황으로 최소한의 큐비트 개수로 구현하는 것에 관심을 가지고 효율적인 구현을 목표로 하고 있다. 본 논문에서는 국산 해시함수 LSH 구현에 큐빗 재활용, 사전 연산을 통해 사용 큐빗 수를 줄였다. 또한, Mix, Final 함수와 같은 핵심 연산들을 IBM에서 제공하는 양자 프로그래밍 툴인 ProjectQ를 사용하여 양자회로로 효율적으로 구현하였고 이에 필요한 양자 자원들을 평가하였다. Recently, the advantages of high-speed arithmetic in quantum computers have been known, and interest in quantum circuits utilizing qubits has increased. The Grover algorithm is a quantum algorithm that can reduce n-bit security level symmetric key cryptography and hash functions to n/2-bit security level. Since the Grover algorithm work on quantum computers, the symmetric cryptographic technique and hash function to be applied must be implemented in a quantum circuit. This is the motivation for these studies, and recently, research on implementing symmetric cryptographic technique and hash functions in quantum circuits has been actively conducted. However, at present, in a situation where the number of qubits is limited, we are interested in implementing with the minimum number of qubits and aim for efficient implementation. In this paper, the domestic hash function LSH is efficiently implemented using qubits recycling and pre-computation. Also, major operations such as Mix and Final were efficiently implemented as quantum circuits using ProjectQ, a quantum programming tool provided by IBM, and the quantum resources required for this were evaluated.

SIMECK에 대한 양자회로 최적화 구현

송경주 ( Gyeong-ju Song ),장경배 ( Kyung-bae Jang ),심민주 ( Min-joo Sim ),서화정 ( Hwa-jeong Seo ) 한국정보처리학회 2022 한국정보처리학회 학술대회논문집 Vol.29 No.2

대규모 양자컴퓨터가 등장하면 기존 암호체계가 더 이상 안전하지 않을 것이라 예상한다. 양자 알고리즘인 Grover‘s 알고리즘은 대칭키 암호에 대한 brute-force attack을 가속화 시켜 보안강도를 감소시킨다. 따라서 양자컴퓨터의 가용 자원이 암호공격에 필요한 자원에 도달했을 때, 공격 대상 암호가 깨지는 시점으로 보고 있다. 많은 선행 연구들은 암호를 양자회로로 구현하여 공격에 필요한 자원을 추정하고 암호에 대한 양자 강도를 확인하였다. 본 논문에서는 이러한 연구동기로 ARX 구조의 SIMECK 경량암호에 대한 양자회로를 처음으로 제안한다. 우리는 SIMECK 양자회로에 대한 최적의 양자회로 구현을 제시하고 각 함수의 동작을 설명한다. 마지막으로 SIMECK 양자회로에 대한 양자자원을 추정하고 SIMON 양자회로와 비교하여 평가한다.

코드기반암호에 대한 ISD 공격 알고리즘 연구 동향

송경주 ( Gyeong-ju Song ),강예준 ( Ye-june Kang ),장경배 ( Kyung-bae Jang ),서화정 ( Hwa-jeong Seo ) 한국정보처리학회 2021 한국정보처리학회 학술대회논문집 Vol.28 No.1

현재, 주요 선진국들을 포함하여 Google과 IBM과 같은 국제 대기업들을 필두로 양자 컴퓨터 개발에 전폭적인 투자들을 하고 있다. 양자 컴퓨터는 특정 분야에 있어 월등한 계산 능력을 보여주며, 기존 컴퓨터에서는 해결할 수 없던 몇몇 문제들을 빠른 시간 내에 해결한다. 이러한 양자 컴퓨터의 등장은 기존 컴퓨터에서는 사실상 풀 수 없는 암호 알고리즘들을 빠른 시간 내에 해결하여 암호학계에 큰 위협이 되고 있다. 현재 사용하고 있는 대부분의 공개키 암호 알고리즘인 RSA와 ECC(Elliptic Curve Cryptography) 또한 공격 대상이다. NIST에서는 다가오는 양자 컴퓨터 시대에 대비하여 양자내성암호 공모전을 주최하였으며 현재 라운드 3에 도입하였다. 본 논문에서는 라운드 3의 후보 알고리즘인 코드기반암호를 공격하는 ISD(Information Set Decoding) 알고리즘에 관한 동향을 조사하였다.

Quantum neural network를 활용한 암호 연구 동향

송경주 ( Gyeong-ju Song ),장경배 ( Kyung-bae Jang ),엄시우 ( Si-woo Eum ),심민주 ( Min-joo Sim ),서화정 ( Hwa-jeong Seo ) 한국정보처리학회 2021 한국정보처리학회 학술대회논문집 Vol.28 No.2

고전적인 인공 신경망을 암호 분야에 사용하기 위한 연구들이 이뤄지고 있으며 다양한 암호 관련 분야에서의 사용이 제안되었다. 더 나아가 최근에는 양자 컴퓨터의 연산속도 이점을 활용해서 고전적인 인공 신경망을 학습하기 위한 연구들이 진행되고 있다. 양자컴퓨터의 양자 알고리즘은 기존 컴퓨터에서 보여주지 못한 연산속도를 보여주었으며 앞으로의 잠재력이 기대되고 있다. 본 논문에서는 Quantum Neural Network (QNN)를 활용한 암호 연구 동향에 대해 살펴본다.