LWE와 LWR을 이용한 효율적인 다중 비트 암호화 기법 = Efficient Multi-bit Encryption Scheme Using LWE and LWR

국문 초록 (Abstract)

최근 양자 컴퓨터에 대한 개발이 활발히 진행 되면서, 기존에 널리 사용되고 있는 RSA와 타원곡선 암호 알고리즘의 안전성에 대한 문제가 제기되고 있다. 이에 대응하기 위하여 미국 표준기술연구원(NIST)은 양자 컴퓨팅 환경에서도 안전한 공개키 암호 기법에 대한 표준화 작업을 진행 하고 있다. 대표적인 포스트 양자 암호(post-quantum cryptography, PQC) 기법으로는 격자기반 암호(lattice-based cryptography)가 있으며, NIST의 PQC 표준화 공모에도 다양한 격자기반 암호 기법들이 제안되었다. 이 중 EMBLEM은 기존의 LWE(learning with errors) 가정을 기반으로 하여 설계된 암호 기법들과는 달리, 더 직관적이고 효율적으로 암/복호화가 가능한 새로운 다중 비트 암호화 방법을 제안하였다. 본 논문에서는 LWR(learning with rounding) 가정을 추가적으로 사용하여 더 효율적으로 동작하는 다중 비트 암호화 기법을 제안한다. 그리고 제안하는 기법의 안전성을 증명하고, EMBLEM 및 R.EMBLEM과의 비교를 통해 효율성을 분석한다.

주요어: 양자암호, 암호, 보안

다국어 초록 (Multilingual Abstract)

Recent advances in quantum computer development have raised the issue of the security of RSA and elliptic curve cryptography, which are widely used. In response, the National Institute of Standards and Technology(NIST) is working on the standardization of public key cryptosystem which is secure in the quantum computing environment. Lattice-based cryptography is a typical post-quantum cryptography(PQC), and various lattice-based cryptographic schemes have been proposed for NIST’s PQC standardization contest. Among them, EMBLEM proposed a new multi-bit encryption method which is more intuitive and efficient
for encryption and decryption phases than the existing LWE-based encryption schemes. In this paper, we propose a multi-bit encryption scheme with improved efficiency using LWR assumption. In addition, we prove the security of our schemes and analyze the efficiency by comparing with EMBLEM and R.EMBLEM.

keywords: PQC, cryptographic, security

목차 (Table of Contents)

• 그 림 차 례 ··········································································································Ⅰ
• 표 차 례 ················································································································Ⅱ
• 국 문 요 약 ··········································································································Ⅲ
• 1. 서론 ···················································································································1
• 1.1. 연구 목적 ·····································································································1
• 1.2. 연구 내용 및 방법 ·····················································································1
• 2. 배경지식 ···········································································································4
• 2.1. 공개키 암호 ·································································································4
• 2.1.1. 공개키 암호 개요 ··················································································4
• 2.1.2. 공개키 암호 정의 ··················································································5
• 2.1.3. 안전성 모델 ····························································································6
• 2.2. KEM (Key Encapsulation Mechanism) ····················································7
• 2.2.1. 알고리즘 ··································································································7
• 2.2.2. 안전성 모델 ····························································································8
• 2.3. 암호학적 가정 ·····························································································9
• 2.3.1. Learning with errors (LWE) ································································9
• 2.3.2. Learning with rounding (LWR) ·························································11
• 3. LWE와 LWR을 이용한 다중 비트 암호화 기법 ·····································12
• 3.1. 메시지 인코딩 ···························································································12
• 3.2. 선택 평문 공격 (IND-CPA) 에 안전한 기법 ·······································14
• 3.2.1. 안전성 증명 ··························································································17
• 3.3. 선택 암호문 공격 (IND-CCA) 에 안전한 기법 ···································19
• 3.3.1 안전성 증명 ···························································································21
• 4. RLWE와 RLWR을 이용한 다중 비트 암호화 기법 ································23
• 4.1. 메시지 인코딩 ···························································································23
• 4.2. 선택 평문 공격 (IND-CPA) 에 안전한 기법 ·······································24
• 4.2.1. 안전성 증명 ··························································································27
• 4.3. 선택 암호문 공격 (IND-CCA) 에 안전한 기법 ···································31
• 4.3.1 안전성 증명 ···························································································32
• 5. 파라미터 선택 ·································································································34
• 6. 실험 결과 비교 ·······························································································38
• 6.1. 구현 환경 ···································································································38
• 6.2. 구현 방법 ···································································································38
• 6.2.1 LWE와 LWR을 이용한 다중 비트 암호화 기법에서 사용하는 키
• 생성함수 상세 ······································································································38
• 6.2.2 LWE와 LWR을 이용한 다중 비트 암호화 기법 상세 ··················42
• 6.2.3 RLWE와 RLWR을 이용한 다중 비트 암호화 기법에서 사용하는
• 키 생성함수 상세 ································································································50
• 6.2.4 RLWE와 RLWR을 이용한 다중 비트 암호화 기법 상세 ·············53
• 6.3. 결과 정리 ···································································································61
• 6.3.1 LWE와 LWR을 이용한 다중 비트 암호화 기법 결과 ··················61
• 6.3.2 RLWE와 RLWR을 이용한 다중 비트 암호화 기법 결과 ·············66
• 7. 결론 ···················································································································70
• 참고문헌 ················································································································71
• ABSTRACT ············································································································74