Candidate Multilinear Maps , livre ebook

Association for Computing Machinery and Morgan & Claypool Publishers - Sanjam Garg

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

86 pages

English

Vous pourrez modifier la taille du texte de cet ouvrage

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

The aim of cryptography is to design primitives and protocols that withstand adversarial behavior. Information theoretic cryptography, how-so-ever desirable, is extremely restrictive and most non-trivial cryptographic tasks are known to be information theoretically impossible. In order to realize sophisticated cryptographic primitives, we forgo information theoretic security and assume limitations on what can be efficiently computed. In other words we attempt to build secure systems conditioned on some computational intractability assumption such as factoring, discrete log, decisional Diffie-Hellman, learning with errors, and many more.
In this work, based on the 2013 ACM Doctoral Dissertation Award-winning thesis, we put forth new plausible lattice-based constructions with properties that approximate the sought after multilinear maps. The multilinear analog of the decision Diffie-Hellman problem appears to be hard in our construction, and this allows for their use in cryptography. These constructions open doors to providing solutions to a number of important open problems.
Table of Contents: Introduction / Survey of Applications / Multilinear Maps and Graded Encoding Systems / Preliminaries I: Lattices / Preliminaries II: Algebraic Number Theory Background / The New Encoding Schemes / Security of Our Constructions / Preliminaries III: Computation in a Number Field / Survey of Lattice Cryptanalysis / One-Round Key Exchange / Generalizing Graded Encoding Systems / Bibliography / Author's Biography

Sujets

Computer Science

Computers

Informatique

Informations

Publié par	Association for Computing Machinery and Morgan & Claypool Publishers
Date de parution	01 mars 2015
Nombre de lectures	0
EAN13	9781627055482
Langue	English
Poids de l'ouvrage	1 Mo

Informations légales : prix de location à la page 0,2050€. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Extrait

Candidate Multilinear Maps
ACM Books
Editor in Chief
M. Tamer zsu, University of Waterloo
ACM Books is a new series of high-quality books for the computer science community, published by ACM in collaboration with Morgan Claypool Publishers. ACM Books publications are widely distributed in both print and digital formats through booksellers and to libraries (and library consortia) and individual ACM members via the ACM Digital Library platform.
Candidate Multilinear Maps
Sanjam Garg, University of California, Berkeley
2015
Smarter than Their Machines: Oral Histories of Pioneers in Interactive Computing
John Cullinane, Northeastern University; Mossavar-Rahmani Center for Business and Government, John F. Kennedy School of Government, Harvard University
2015
A Framework for Scientific Discovery through Video Games
Seth Cooper, University of Washington
2014
Trust Extension as a Mechanism for Secure Code Execution on Commodity Computers
Bryan Jeffrey Parno, Microsoft Research
2014
Embracing Interference in Wireless Systems
Shyamnath Gollakota, University of Washington
2014
Candidate Multilinear Maps
Sanjam Garg
University of California, Berkeley
ACM Books 5
Copyright 2015 by the Association for Computing Machinery and Morgan Claypool Publishers
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means-electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews-without the prior permission of the publisher.
Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which Morgan Claypool is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.
Candidate Multilinear Maps
Sanjam Garg
books.acm.org
www.morganclaypool.com
ISBN: 978-1-62705-549-9 hardcover
ISBN: 978-1-62705-537-6 paperback
ISBN: 978-1-62705-538-3 ebook
ISBN: 978-1-62705-548-2 ePub
Series ISSN: (to come)
DOIs: 10.1145/2714451 Book
10.1145/2714451.2714452 Preface
10.1145/2714451.2714453 Chapter 1
10.1145/2714451.2714454 Chapter 2
10.1145/2714451.2714455 Chapter 3
10.1145/2714451.2714456 Chapter 4
10.1145/2714451.2714457 Chapter 5
10.1145/2714451.2714458 Chapter 6
10.1145/2714451.2714459 Chapter 7
10.1145/2714451.2714460 Chapter 8
10.1145/2714451.2714461 Chapter 9
10.1145/2714451.2714462 Chapter 10
10.1145/2714451.2714463 Bibliography
A publication in the ACM Books series, 5
Editor in Chief: M. Tamer zsu, University of Waterloo
First Edition
10 9 8 7 6 5 4 3 2 1
Contents
Preface
Chapter 1 Introduction
1.1 Our Results
1.2 Brief Overview
1.3 Organization
Chapter 2 Survey of Applications
2.1 How Flexible Can We Make Access to Encrypted Data?
2.2 Program Obfuscation
2.3 Other Applications
Chapter 3 Multilinear Maps and Graded Encoding Systems
3.1 Cryptographic Multilinear Maps
3.1.1 Efficient Procedures
3.1.2 Hardness Assumptions
3.2 Graded Encoding Schemes
3.2.1 Efficient Procedures-The Dream Version
3.2.2 Efficient Procedures-The Real-Life Version
3.2.3 Hardness Assumptions
Chapter 4 Preliminaries I: Lattices
4.1 Lattices
4.2 Gaussians on Lattices
4.3 Sampling from Discrete Gaussian
Chapter 5 Preliminaries II: Algebraic Number Theory Background
5.1 Number Fields and Rings of Integers
5.2 Embeddings and Geometry
5.3 Ideals in the Ring of Integers
5.4 Prime Ideals-Unique Factorization and Distributions
5.5 Ideal Lattices
Chapter 6 The New Encoding Schemes
6.1 The Basic Graded Encoding Scheme
6.2 Setting the Parameters
6.3 Extensions and Variants
Chapter 7 Security of Our Constructions
7.1 Our Hardness Assumption
7.2 Simplistic Models of Attacks
7.2.1 Hardness of GCDH in the Arithmetic Straight-Line Program Model
7.3 Cryptanalysis Beyond the Generic Models
7.3.1 Easily Computable Quantities
7.3.2 Using Averaging Attacks
7.3.3 Cryptanalysis with Extra Help
7.4 Some Countermeasures
7.5 Easiness of Other Problems
Chapter 8 Preliminaries III: Computation in a Number Field
8.1 Some Computational Aspects of Number Fields and Ideal Lattices
8.2 Computational Hardness Assumptions over Number Fields
Chapter 9 Survey of Lattice Cryptanalysis
9.1 Averaging Attacks
9.2 Gentry-Szydlo: Recovering from and
9.3 Nguyen-Regev: A Gradient Descent Attack
9.4 Ducas-Nguyen: Gradient Descent over Zonotopes and Deformed Parallelepipeds
9.5 A New Algorithm for the Closest Principal Ideal Generator Problem
9.6 Coppersmith Attacks
9.7 Dimension Halving in Principal Ideal Lattices
Chapter 10 One-Round Key Exchange
10.1 Definitions
10.2 Our Construction
Appendix A Generalizing Graded Encoding Systems
A.1 Efficient Procedures-The Dream Version
A.2 Efficient Procedures-The Real-Life Version
A.3 Hardness Assumptions
Bibliography
Author s Biography
Preface
Cryptography to me is black magic, enabling tasks that often seem paradoxical or simply just impossible. Like the space explorers, we cryptographers often wonder, What are the boundaries of this world of black magic ? This book lays one of the founding stones in furthering our understanding of these edges.
This book is based on my Ph.D. thesis, which was an extended version of a paper, Candidate Multilinear Maps from Ideal Lattices, co-authored with Craig Gentry and Shai Halevi. This paper was originally published at EUROCRYPT 2013.
Sanjam Garg
March 2014
1 Introduction
The aim of cryptography is to design primitives and protocols that withstand adversarial behavior. Information theoretic cryptography, how-so-ever desirable, is extremely restrictive and most non-trivial cryptographic tasks are known to be information theoretically impossible. In order to realize sophisticated cryptographic primitives, we forgo information theoretic security and assume limitations on what can be efficiently computed. In other words, we attempt to build secure systems conditioned on some computational intractability assumption, such as: factoring [ Rivest et al. 1978 ], discrete log [ Knuth 1997 ], decisional Diffie-Hellman [ Diffie and Hellman 1976 ], learning with errors [ Regev 2005 ], and many more (see Vercauteren 2013 ).
Last decade has seen a push toward using structured assumptions such as the ones based on bilinear maps, for realizing sophisticated cryptographic goals otherwise considered impossible according to folklore. For example, bilinear pairings have been used to design ingenious protocols for tasks such as one-round three-party key exchange [ Joux 2000 ], identity-based encryption [ Boneh and Franklin 2001 ], and non-interactive zero-knowledge proofs [ Groth et al. 2006 ]. By now the applications of bilinear maps have become too numerous to name.
Boneh and Silverberg [ 2003 ] show that cryptographic groups equipped with multilinear maps would have even more interesting applications, including one-round multi-party key exchange and very efficient broadcast encryption. However, they present strong evidence that such maps should be hard to construct. In particular, they attempt to construct multilinear maps from abelian varieties (extending known techniques for constructing bilinear maps), but identify serious obstacles, and conclude that such maps might have to either come from outside the realm of algebraic geometry, or occur as unnatural computable maps arising from geometry. Since then, the persistent absence of cryptographically useful multilinear maps has not stopped researchers from proposing applications of them. For example, R ckert and Schr der [ 2009 ] use multilinear maps to construct efficient aggregate and verifiably encrypted signatures without random oracles. Papamanthou et al. [ 2010 ] show that compact multilinear maps give very efficient authenticated data structures. Recently, Rothblum [ 2013 ] uses multilinear maps to construct a counterexample to the conjecture that all bit-encryption schemes [ Black et al. 2003 , Camenisch and Lysyanskaya 2001 ] are circularly secure (secure when bit-encryptions of the secret key are also given out).
1.1 Our Results
In this work [ Garg et al. 2012 , 2013a ], we put forth new plausible lattice-based constructions with properties that approximate the sought after multilinear maps. The multilinear analog of the decisional Diffie-Hellman problem appears to be hard in our constructions, and this allows for their use in cryptography. These constructions open doors to providing solutions (see Chapter 2 for details) to a number of important open problems.
Functionality Our multilinear maps are approximate in the sense that they are noisy. Furthermore, they are bounded to a polynomial degree. For very high degree, in our maps, the noisiness overwhelms the signal, somewhat like ciphertexts in somewhat homomorphic encryption [ Gentry 2009b ] schemes. In light of their noisiness, one could say that our multilinear maps are indeed unnatural computable maps arising from geometry. As a consequence, our multilinear maps differ quite substantially from the ideal multilinear maps envisioned by Boneh and Silverberg [ 2003 ].
The boundedness of our encodings has interesting consequences, both positive and negative. On the positive side, it hinders an attack based on Boneh and Lipton s subexponential algorithm for solving the discrete logarithm in black box fields [ Boneh and Lipton 1996 ]. This attack cannot be used to solve the discrete log problem in our setting, since their algorithm requires exponentiations with exponential degree. On the negative side, the dependence between the degree and parameter-size prevents us from realizing applications such as the ones envisioned by Papamanthou et al. [ 2010 ] because they need compact maps. Similarl