양자내성암호를 위한 고성능 NewHope 암호 아키텍처 = High-Performance NewHope Cryptography Architecture for Post-quantum Cryptography

국문 초록 (Abstract)

본 논문에서는 차세대 양자내성암호를 위한 NewHope 암호 알고리즘 기반의 고성능 NewHope 암호 아키텍처를 제안한다. Alkim 등에 의해 BCNS 프로토콜의 단점을 보완하여 개발된 NewHope 암호 알고리즘은 NIST(National Institute of Standards and Technology)에서 주관하는 양자내성암호 공모전 알고리즘 중 하나로 2019년 1월 2라운드 후보에 선정됐다. 제안하는 NewHope 암호 아키텍처는 암호화(Encryption)와 복호화(Decryption)에 필요한 키를 생성하는 키 생성(Key generation) 모듈과 암호화 모듈 그리고 복호화 모듈로 구성되어 있다.
양자내성암호로 꼽히는 격자-기반 암호 알고리즘은 주로 LWE(Learning With Error)기법을 사용한다. LWE는 격자-기반 암호 구현 시 에러를 삽입하여 행렬식의 해를 찾기 어렵도록 하는 기법이다. 하지만 계산시에 키가 커지는 단점과 연산속도 문제점 때문에 환(Ring) 안에서 계산하는 Ring-LWE 방법이 제안되었다. NewHope 암호 아키텍처는 격자-기반 알고리즘으로서 Ring-LWE(Learning With Error) 기법을 사용한다. Ring-LWE는 환(Ring) 안에서 계산되며 다항식 곱셈이 주로 쓰이는데 가장 많은 시간자원을 사용하므로 다항식 연산속도를 향상 시켜주는 고성능 NTT(Number Theoretic Transform)를 필요로 한다. 제안된 고성능 NTT 아키텍처는 높은 데이터 처리율을 얻기 위해 파이프라인이 가능한 구조인 Single-path Delay Feedback(SDF), 2-병렬 Multi-path Delay Feedback(MDF), 4-병렬 MDF 구조 방법을 사용하였다.
NewHope 암호 아키텍처는 안전성에 따라서 n의 값을 512와 1024로 나눠서 제안되었으며 본 논문에서는 보안수준이 더 높은 n=1024 파라미터를 기반으로 설계되었다. 또한 암호학적 해쉬 알고리즘인 SHA-3(Secure Hash Algorithm-3) 를 이용하여 알고리즘의 출력 길이를 확장할 수 있는 함수인 SHAKE128과 SHAKE256을 사용하고 샘플링 과정에 대한 효율적 구현의 어려움과 타이밍 공격으로부터 보호하기 위해 중심 이항 분포(Centerd binomial distribution)를 에러 분포로 사용하고 있다. NewHope 알고리즘은 다항식 연산에 사용되는 소수 값을 q=12289<2^14까지 파라미터의 크기를 줄인 것이 특징이며 본 논문에서는 시간 소요가 많이 요구되는 NTT 아키텍처를 연산속도와 면적을 고려한 설계를 위해 2-병렬 MDF-기반 NTT구조를 사용하였다.
제안된 고성능 NewHope 암호 아키텍처는 Xilinx VIVADO툴과 Virtex-7 FPGA 플랫폼에서 구현하였고 성능 비교 및 검증을 하였다.
본 논문에서 제안하는 양자내성암호를 위한 고성능 NewHope 암호 아키텍처는 차세대 도래할 양자 컴퓨터 시대에 데이터 유출을 방지하는 암호 알고리즘으로 사용할 수 있을 것으로 기대되며 고성능의 암호화 연산이 요구되는 분야에 적용할 수 있을 것으로 기대된다.

다국어 초록 (Multilingual Abstract)

This paper proposes a high-performance NewHope cryptographic architecture for next-generation post-quantum cryptography. The NewHope cryptographic algorithm, designed and implemented to complement the shortcomings of the BCNS protocol by Alkim et al., was selected as a candidate for the second round of January 2019 as one of the post-quantum cryptography competition algorithms hosted by the National Institute of Standards and Technology(NIST). The proposed NewHope cryptography architecture is composed of a key generation module, an encryption module, and a decryption module that generates keys necessary for encryption and decryption.
The lattice-based cryptographic algorithm, which is regarded as post-quantum cryptography, mainly uses LWE(Learning With Error) technique. LWE is a technique that makes it difficult to find the solution of a determinant by inserting an error when implementing a lattice-based cryptography. However, the Ring-LWE method of calculating in a Ring has been proposed due to the shortcoming of the key increase in calculation and the problem of calculation speed. The NewHope cryptographic processor uses a Ring-LWE(Learning With Error) technique as a lattice-based algorithm. Ring-LWE is calculated in a Ring, and polynomial multiplication is mainly used. Since it uses the most time resources, it requires a high-performance NTT(Number Theoretic Transform) that improves the polynomial operation speed. The proposed high-performance NTT architecture uses pipelined single-path delay feedback(SDF), 2-parallel multi-path delay feedback(MDF), and 4-parallel MDF architecture methods to achieve high data throughput.
The NewHope cryptographic algorithm is proposed by dividing the value of n=512 and 1024 according to safety, and this paper is designed based on n=1024 parameter with higher security level. Also, among the cryptographic hash algorithms Secure Hash Algorithm-3(SHA-3), SHAKE128 and SHAKE256, which are functions that can extend the output length of the algorithm, are used. The centered binomial distribution is used as an error distribution to protect the sampling process from the difficulty of efficient implementation and timing attacks. For this reason, the centered binomial distribution is used as the error distribution. The NewHope algorithm is characterized by reducing the size of the parameter to q=12289<2^14 for the value used in polynomial operation. In this paper, the NTT architecture, which requires a lot of time, is designed for the design considering the computational speed and area. 2-parallel MDF-based NTT architecture was used.
The proposed high performance NewHope cryptography architecture was compared and verified in Xilinx VIVADO tool and Virtex-7 FPGA. The high-performance NewHope cryptography architecture for post-quantum cryptography proposed in this paper is expected to be used as a next-generation cryptographic algorithm that prevents data leakage in the age of next generation quantum computers, and can be applied to fields requiring high-performance cryptographic operations.

목차 (Table of Contents)

• 제 1 장 서론 1
• 제 2 장 본론 5
• 제 1 절 배경 지식 5
• 1.1. 대칭키 암호 6
• 1.2. 공개키 암호 6
• 1.3. NIST 양자내성암호 공모전 8
• 1.4. 격자-기반(Lattice-based) 암호 알고리즘 9
• 1.5. Ring-LWE 암호 시스템 10
• 제 2 절 NewHope 암호 알고리즘 13
• 2.1 해쉬 알고리즘 17
• 2.2 Rejection Sampling 22
• 2.3 Binomial Sampling 23
• 2.4 Encode polynomial 알고리즘 25
• 2.5 Decode polynomial 알고리즘 26
• 2.6 Compress 알고리즘 27
• 2.7 Message Encoding 알고리즘 29
• 2.8 Message Decoding 알고리즘 30
• 2.9 Decompress 알고리즘 30
• 제 3 절 NTT 코어 아키텍처 32
• 3.1. NTT-기반 다항식 곱셈기 32
• 3.2. 파이프라인-기반 NTT 구조 37
• 3.3. 제안된 NTT 코어 구조 40
• 3.4. 제안된 NTT 코어 구조 성능 분석 및 비교 49
• 제 4 절 NewHope 암호 아키텍처 54
• 4.1. 키 생성 구조 56
• 4.2. 암호화 구조 60
• 4.3. 복호화 구조 63
• 제 5 절 구현 및 성능 비교 66
• 5.1. 제안된 NTT 코어를 이용한 NewHope 암호 아키텍처 기능 검증 66
• 5.2. 제안된 NTT 코어를 이용한 NewHope 암호 아키텍처 구현 결과 분석 69
• 제 3 장 결론 71
• 참고문헌 73