Mathematical Analysis of Multilinear Maps over the Integers

DC Field Value Language
dc.description학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2016. 8. 천정희.-
dc.description.abstractMultilinear maps have lots of cryptographic applications. Until now, there are three types of multilinear maps: the first is constructed using ideal lattices, the second is
defined over the integers, and the last is graph-induced one. However none of them have reduction to well-known hard problems. More serious matter is that they are all proven insecure when low-level encodings of zero are provided .

Especially, for multilinear maps over the integers, construction and analysis are being repeated. At {\sc Crypto} 2013, Coron, Lepoint, and Tibouchi proposed a
multilinear map using CRT (CLT13). However, it was revealed to be insecure so-called CHLRS attack (CHL$^+$15). After then, several attempts have been made to repair the scheme, but quickly proven insecure by extended CHLRS attack. The same authors revised their scheme at {\sc Crypto} 2015 again.

In this thesis, we describe attacks against CLT15. Our attacks share the essence of the cryptanalysis of CLT13 and exploits low level encodings of zero, provided by a ladder, as well as other public parameters. As in
CHL$^+$15, this leads to finding all the secret parameters of $\kappa$-multilinear maps in polynomial time of the security parameter. As a result, CLT15 is fully broken for all possible applications, while the security of CLT13 is not known when low-level encodings are not provided.
dc.description.tableofcontentsChapter 1. Introduction 1

Chapter 2. Introduction to Multilinear Maps 8
2.1 Notation 8
2.2 Multilinear Maps and Graded Encoding Schemes 10
2.3 Multilinear Map Procedures 13
2.4 Related Problems 16

Chapter 3. Break and Repair 18
3.1 The CLT13 Multilinear Map and CHLRS Attack 20
3.1.1 The CLT13 Multilinear Map 20
3.1.2 Zeroizing Attacks on CLT13 25
3.2 The CLT15 Multilinear Map 30

Chapter 4. Main Attack 37
4.1 Computing $\phi$-values 38
4.2 Computing Matrix Equation over Q 42

Bibliography 46

국문 초록 50
dc.format.extent616043 bytes-
dc.publisher서울대학교 대학원-
dc.subjectMultilinear maps-
dc.subjectgraded encoding schemes-
dc.titleMathematical Analysis of Multilinear Maps over the Integers-
dc.citation.pagesiv, 49-
dc.contributor.affiliation자연과학대학 수리과학부-
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Ph.D. / Sc.D._수리과학부)
Files in This Item:
  • mendeley

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