Multi-Client Order-Revealing Encryption and Its Extensions
Multi-Client Order-Revealing Encryption and Its Extensions
- 주제(키워드) Cryptography , Security
- 발행기관 고려대학교 정보보호대학원
- 지도교수 이동훈
- 발행년도 2019
- 학위수여년월 2019. 2
- 유형 Text
- 학위구분 박사
- 학과 정보보호대학원 정보보호학과
- 원문페이지 112 p
- 실제URI http://www.dcollection.net/handler/korea/000000083490
- UCI I804:11009-000000083490
- DOI 10.23186/korea.000000083490.11009.0000930
- 본문언어 영어
- 제출원본 000045978774
초록/요약
Order-revealing encryption (ORE) is a useful cryptographic primitive that provides range queries on encrypted data since anyone can compare the order of plaintexts by running a public comparison algorithm. When a client uploads his/her ORE-encrypted database to a remote server and requests a range query, the server can answer the query without decryption. Currently, most studies on order-revealing encryption focus only on comparing ciphertexts generated by a single client, and there is no study comparing ciphertexts generated by multiple clients. In this thesis, the notion of multi-client order-revealing encryption (MC-ORE) is introduced and a specific MC-ORE scheme with its extensions are presented. The first result of this thesis introduces the concept of multi-client order-revealing encryption that supports comparisons not only on ciphertexts generated by one client but also on ciphertexts generated by multiple clients. A simulation-based (SIM) security model for multi-client order-revealing encryption is also defined with respect to the leakage function which quantifies how much information is leaked from the scheme. The second results present three realizable multi-client order-revealing encryption schemes with different leakage functions in bilinear maps. The first scheme is a basic construction that follows a design principle of Chenette et al.’s practical ORE scheme. It additionally supports comparisons on ciphertexts of different clients. The second scheme is an enhanced version of the basic scheme in terms of the reduced leakage. The third scheme is a modification of the basic scheme that enables designating a client whose ciphertext can be compared. The SIM-security of those schemes is proven in the random oracle model. The third results address a multi-client range query scheme over encrypted data as a main application of MC-ORE. For an encrypted database, not only the owner of the database but also other authorized clients can retrieve data through range queries. The constructions use the notion of MC-ORE so that a server can answer the range query by running the comparison algorithm of MC-ORE. In addition, improved search methods in terms of efficiency are given with the comparison results of these suggested methods.
more목차
1 Introduction 1
1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Definitions of MC-ORE . . . . . . . . . . . . . . . . . . 3
1.2.2 Realizable MC-ORE Schemes . . . . . . . . . . . . . . . 4
1.2.3 Multi-Client Range Queries from MC-ORE . . . . . . . . 5
1.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Background 10
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Bilinear Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Complexity Assumptions . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Order-Revealing Encryption . . . . . . . . . . . . . . . . . . . . 13
2.4.1 ORE of Chenette et al. [14] . . . . . . . . . . . . . . . . . 16
2.4.2 ORE of Lewi et al. [37] . . . . . . . . . . . . . . . . . . . 17
2.4.3 ORE of Cash et al. [10, 11] . . . . . . . . . . . . . . . . . 18
3 Multi-Client Order-Revealing Encryption 20
3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
iii
3.1.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2 Security Model . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Basic MC-ORE . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.1 Design Principle . . . . . . . . . . . . . . . . . . . . . . 25
3.2.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.3 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 Enhanced Multi-Client Order-Revealing Encryption 40
4.1 MC-ORE with Reduced Leakage . . . . . . . . . . . . . . . . . . 40
4.1.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1.2 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 MC-ORE with Designated Comparison . . . . . . . . . . . . . . 51
4.2.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.2 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5 Multi-Client Range Query over Encrypted Data 67
5.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2 Basic MC-RQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2.2 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.3 Designated MC-RQ . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3.2 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6 Implementation 83
6.1 Performance of MC-ORE . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Range Query Methods . . . . . . . . . . . . . . . . . . . . . . . 86
iv
7 Discussion 90
7.1 Reducing Trust on the Center. . . . . . . . . . . . . . . . . . . . 90
7.2 Removing the Trusted Center. . . . . . . . . . . . . . . . . . . . 91
7.2.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . 91
8 Conclusion 94
