Publications

Detailed Information

Efficient Instantiation of LWE-based Public-Key Encryption and Commitment Schemes : LWE 문제 기반 공개키 암호 및 commitment 스킴의 효율적인 인스턴스화

DC Field Value Language
dc.contributor.advisor천정희-
dc.contributor.author김진수-
dc.date.accessioned2018-05-28T17:11:38Z-
dc.date.available2018-05-28T17:11:38Z-
dc.date.issued2018-02-
dc.identifier.other000000151441-
dc.identifier.urihttps://hdl.handle.net/10371/141141-
dc.description학위논문 (박사)-- 서울대학교 대학원 : 자연과학대학 수리과학부, 2018. 2. 천정희.-
dc.description.abstractThe Learning with Errors (LWE) problem has been used as a underlying problem of a variety of cryptographic schemes. It makes possible constructing advanced solutions like fully homomorphic encryption, multi linear map as well as basic primitives like key-exchange, public-key encryption, signature. Recently, developments in quantum computing have triggered interest in constructing practical cryptographic schemes. In this thesis, we propose efficient post-quantum public-key encryption and commitment schemes based on a variant LWE, named as spLWE. We also suggest related zero-knowledge proofs and LWE-based threshold cryptosystems as an application of the proposed schemes. In order to achieve these results, it is essential investigating the hardness about the variant LWE problem, spLWE. We describe its theoretical, and concrete hardness from a careful analysis.-
dc.description.tableofcontents1.Introduction 1
2.Preliminaries 5
2.1 Notations 5
2.2 Cryptographic notions 5
2.2.1 Key Encapsulation Mechanism 5
2.2.2 Commitment Scheme 6
2.2.3 Zero-Knowledge Proofs and Sigma-Protocols 7
2.3 Lattices 9
2.4 Discrete Gaussian Distribution 11
2.5 Computational Problems 12
2.5.1 SVP 12
2.5.2 LWE and Its Variants 12
2.6 Known Attacks for LWE 13
2.6.1 The Distinguishing Attack 14
2.6.2 The Decoding Attack 15
3.LWE with Sparse Secret, spLWE 16
3.1 History 16
3.2 Theoratical Hardness 17
3.2.1 A Reduction from LWE to spLWE 18
3.3 Concrete Hardness 21
3.3.1 Dual Attack (distinguish version) 21
3.3.2 Dual Attack (search version) 23
3.3.3 Modifed Embedding Attack 25
3.3.4 Improving Lattice Attacks for spLWE 26
4.LWE-based Public-Key Encryptions 29
4.1 History 29
4.2 spLWE-based Instantiations 31
4.2.1 Our Key Encapsulation Mechanism 31
4.2.2 Our KEM-Based Encryption Scheme 33
4.2.3 Security 35
4.2.4 Correctness 36
4.3 Implementation 37
4.3.1 Parameter Selection 38
4.3.2 Implementation Result 39
5.LWE-based Commitments and Zero-Knowledge Proofs 41
5.1 History 42
5.2 spLWE-based Instantiations 43
5.2.1 Our spLWE-based Commitments 44
5.2.2 Proof for Opening Information 47
5.3 Application to LWE-based Threshold Crytosystems 50
5.3.1 Zero-Knowledge Proofs of Knowledge for Threshold Decryption 50
5.3.2 Actively Secure Threshold Cryptosystems 58
6.Conclusions 63
-
dc.formatapplication/pdf-
dc.format.extent3578294 bytes-
dc.format.mediumapplication/pdf-
dc.language.isoen-
dc.publisher서울대학교 대학원-
dc.subjectlattice-
dc.subjectlearning with errors-
dc.subjectLWE-
dc.subjectsparse-
dc.subjectpublic-key encryption-
dc.subjectcommitment-
dc.subjectthreshold cryptosystems-
dc.subject.ddc510-
dc.titleEfficient Instantiation of LWE-based Public-Key Encryption and Commitment Schemes-
dc.title.alternativeLWE 문제 기반 공개키 암호 및 commitment 스킴의 효율적인 인스턴스화-
dc.typeThesis-
dc.contributor.AlternativeAuthorKim Jinsu-
dc.description.degreeDoctor-
dc.contributor.affiliation자연과학대학 수리과학부-
dc.date.awarded2018-02-
Appears in Collections:
Files in This Item:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share