Public-Key Encryption and Functional Encryption from LWR

국문 초록 (Abstract)

2016년 미국 National Institute of Standards and Technology (NIST)에 의해 양자내성 암호 표준화 공모가 시작된 이래로 RSA 암호, 타원곡선 암호 등을 대체할 수 있는 실용적인 양자내성 암호에 대한 필요성이 대두되어, 양자내성 암호 스킴의 효율적인 인스턴스화를 위해 다양한 기법들과 방법론들이 제안되어 왔다.
본 논문에서는 공개키 암호, 동형 암호, 함수 암호 설계를 위한 LWE 기반 설계 방식으로 가장 범용적으로 사용되는 Dual-Regev 방식의 암호화 과정에서 랜덤 가우시안 오류를 더하는 대신 하위 비트를 소거하는 식으로 오류를 주입함으로 서 LWR의 어려움에 기반하여 안전성을 확보하는 방식을 제안하였다. 또한, 해당 LWR 기반 Dual-Regev 암호화 방식을 사용하는 공개키 암호와 신원 기반 암호, 속성 기반 암호 스킴에 대한 안전성을 수학적으로 증명하였다. 마지막으로 LWR 문제에 대한 구체적인 공격 방법들을 연구하고 각 스킴들의 복호화 실패 확률을 분석하여 공개키 암호와 신원 기반 암호, 속성 기반 암호에 대해 LWR 기반의 Dual-Regev 암호화 방식을 사용하는 효율적인 인스턴스화를 제안하였다.

다국어 초록 (Multilingual Abstract)

Post-quantum cryptography has gained a growing attention from the cryptography community at this moment due to the recent development of quantum computer and standardization project launched by the National Institute of Standards and Technology (NIST) in the United States. The dual-Regev encryption based on the Learning with Errors (LWE) problem has been widely employed in many constructions for post-quantum cryptography such as public-key encryption, fully homomorphic encryption, functional encryption, etc.

In this thesis, we propose an efficient post-quantum public-key encryption scheme with its variants and functional encryption schemes such as identity-based encryption and attribute-based encryption schemes based on Learning with Rounding (LWR) problem, all of which share the essence of the LWE-based dual-Regev encryption. Our approach accelerates encryption speeds by replacing the Gaussian sampling phase with efficient rounding process, and reduces the ciphertext sizes. To achieve these results, we investigate the concrete hardness of the LWR problem to assess the security of proposed schemes. We also analyze the respective conditions on which these schemes correctly work, and propose efficient instantiation with adequate quantum security.

목차 (Table of Contents)

• Abstract
• 1 Introduction
• 1.1 Public Key Encryption from LWR
• 1.2 Functional Encryption from LWR
• 1.3 List of Papers
• 2 Preliminaries
• 2.1 Notation
• 2.2 Cryptographic Notions
• 2.2.1 Key Encapsulation Mechanism
• 2.2.2 Identity-Based Encryption
• 2.2.3 Attribute-Based Encryption
• 2.3 Lattices
• 2.4 Distributions
• 2.5 Computational Problems
• 2.5.1 SIS
• 2.5.2 LWE
• 2.6 Lattice-based One Way Functions and Trapdoors
• 3 Learning with Rounding
• 3.1 Theoretical Hardness
• 3.2 Concrete Hardness
• 3.2.1 Primal Attack for LWR
• 3.2.2 Dual Attack for LWR
• 3.2.3 Measurement of the BKZ complexity
• 4 Public Key Encryption from LWR
• 4.1 History
• 4.2 Our Public Key Encryption Scheme
• 4.2.1 Construction
• 4.2.2 Security
• 4.2.3 IND-CCA Secure Encryption Scheme
• 4.3 Advantages of LWR-based PKE Scheme
• 4.4 Efficient Instantiation with Small Secrets
• 4.4.1 Correctness Analysis for Various Setups
• 4.4.2 Proposed Parameters
• 4.5 Ring Version
• 4.5.1 Construction
• 4.5.2 Security
• 4.5.3 IND-CCA Secure Key Encapsulation Mechanism
• 4.5.4 Proposed Parameters
• 5 Functional Encryptions from LWR
• 5.1 Previous Approach
• 5.2 Our Identity-Based Encryption Scheme
• 5.2.1 Construction
• 5.2.2 Correctness
• 5.2.3 Security
• 5.2.4 Ring Version
• 5.3 Attribute-Based Encryption
• 5.3.1 Construction
• 5.3.2 Correctness
• 5.3.3 Security
• 5.3.4 Ring Version
• 5.4 Efficient Instantiation and Advantages
• 5.4.1 Parameter Setting
• 5.4.2 Advantages
• 6 Implementation Results
• 6.1 Implementation Result for PKE
• 6.2 Implementation Result for Ring Version KEM
• 7 Conclusions
• Abstract (in Korean)