Recently, with the development of quantum computing technology, the possibility of realization of Grover‘s algorithm and Shor’s algorithm has increased, and there is the problem that these algorithms can break the security of existing public key cryptosystems, symmetric key cryptosystems and hash functions.

To solve this problem, research and standardization of the post-quantum cryptography which provides the security in a quantum computing environment, are actively being carried out. However, the post-quantum cryptography has secret key and public key which are bigger than the existing cryptosystem and matrix multiplication/vector addition and polynomial multiplication for lattice-based post-quantum cryptography take most of key generation, encryption and decryption execution time. For these reasons, it is needed to research on implementation and application of post-quantum cryptography for providing the security against side-channel attack and high-performance on the Internet-of-Things device environment.

In this thesis, we propose methods to provide security against side-channel attacks and high-speed performance of lattice-based post-quantum cryptography on the 32-bit Internet of Things device environment.

Proposed methods in this thesis use the ARM NEON SIMD and proposed efficient implementation methods are based on analysis results on previous works and the characteristic of the secret key polynomials. After then, we applied the proposed methods to Lizard/RLizard lattice-based post-quantum cryptography to verify the performance improvement.

Proposed methods 1 and 2 for high-performance of Polynomial Multiplication are based on the property that secret polynomial or random polynomial coefficients always have a value of 1, 0, -1. However, it has a vulnerability to side-channel attacks by using conditional statements depending on confidential information. For solving this problem, the proposed method 3 and 4 for polynomial multiplication provides high-speed performance compared to the conventional method, and guarantees the security against side-channel attack by ensuring constant-time execution through a structure that always performs same operations irrespective of confidential information. As a result, in the performance improvement, the polynomial multiplication proposal method 2 improved the performance most, In terms of providing security for a side-channel attack (timing attack), the proposed polynomial multiplication method 3 guarantees constant-time execution by having the smallest standard deviation value for execution time.  

최근 양자 컴퓨팅 기술의 발전에 따라 그로버 알고리즘과 쇼어 알고리즘의 실현화 가능성이 커지고, 이러한 알고리즘을 활용할 경우, 기존 공개키 암호와 대칭키 암호 및 해시 함수에 대한 안전성이 깨질 수 있는 문제가 발생한다. 이를 해결하고자 양자 컴 퓨팅 환경에서도 안전성을 제공하는 양자내성암호에 대한 연구 및 표준화가 활발히 이루어지고 있다. 하지만 양자내성암호는 기존의 암호 기법 보다 큰 공개키와 비밀키 를 사용하며, 격자 기반 양자내성암호에서 사용되는 대용량 행렬 곱셈 및 벡터 덧셈 연산과 다항식 곱셈 연산 시간이 전체 연산의 상당 부분을 차지한다. 이러한 특성으로 인해, 사물인터넷 디바이스 환경 상에서의 고속의 성능을 가지며, 부채널 공격에 안전 한 구현 및 적용 연구가 필요하다.

본 학위 논문에서는 대표적인 양자내성암호 유형인 격자 기반 양자내성암호에 대해 32비트 사물인터넷 디바이스 환경 상에서 부채널 공격에 대한 안전성과 고속의 성능 을 제공하기 위한 구현 기법들을 제안 한다. 이를 위해, 격자 기반 양자내성암호에서 수행 시간의 상당 부분을 차지하는 행렬 곱셈 및 벡터 덧셈 연산과 다항식 곱셈 연산 에 대해 기존 구현 기법 분석을 진행하였으며, 피연산자 비밀키 다항식 특성들을 통해, 성능 고속화 구현 기법 설계와 ARM NEON SIMD 기술을 활용하였다. 그리고 제안된 기법들에 대해 Lizard/RLizard 격자 기반 양자내성암호에 실 적용하여 성능 향상 효과 를 검증하였다. 이를 통해, 행렬 곱셈 및 벡터 덧셈을 위한 제안 방식 1은 속도는 향 상되었으나, 제안 방식 2에 비해 수행시간에 대한 높은 표준편차 값을 가짐으로써, 타 이밍 공격에 대한 constant-time 내 수행 보장성이 약한 것으로 확인되었다. 제안 방 식 2의 경우, 속도는 기존 대비 향상되었으나, 제안 기법 1보다 더 큰 용량에 대한 연 산이 필요한 단점으로 제안 기법 1보다는 느린 성능을 가지지만, 행렬 곱셈 및 벡터 덧셈 연산 전체를 ARM NEON SIMD 기반으로 처리함으로써 constant-time 내 수행을 보장하며, 이를 통한 부채널 공격(타이밍 공격)에 대한 안전성을 제공한다.

다항식 곱셈에 관한 제안 방식 1과 2는 성능 고속화 관점에서 비밀 다항식 혹은 난 수 다항식의 계수가 항상 1, 0, -1중 하나의 값을 가진다는 특성과 사전 계산 방식 그리고 누적 연산을 바탕으로 성능을 고속화하였지만, 비밀 정보에 종속적인 조건문을 사용함으로써 부채널 공격에 대한 취약성을 가진다. 이를 해결하기 위해, 제안 기법 3, 4는 기존 기법 대비 고속의 성능을 가지며, 비밀 정보와 상관없이 항상 동일한 연산을 수행하는 구조를 통해 constant-time 내 수행을 보장함으로써 부채널 공격(타이밍 공 격)에 대한 안전성을 제공한다. 이를 통해, 성능 향상 측면에서는 다항식 곱셈 제안 기 법 2가 가장 많은 성능을 향상시켰으며, 부채널 공격(타이밍 공격)에 대한 안전성 제공 측면에서는 다항식 곱셈 제안 기법 3이 수행 시간에 대한 가장 작은 표준편차 값을 가짐으로써 constant-time 내 수행을 보장하는 것으로 확인되었다.