Introduction to the Lattice Crypto Day

pefav

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

37 pages

English

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

A propos
Informations
Extrait

Description

Introduction to the Lattice Crypto Day Phong Nguy?n May 2010 MAYA

phong nguy?n

Informations

Publié par	pefav
Nombre de lectures	10
Langue	English
Poids de l'ouvrage	7 Mo

Extrait

MAYA
Introduction to the Lattice Crypto Day
Phong Nguyễn
http://www.di.ens.fr/~pnguyen
May 2010Summary
History of Lattice-based Crypto
Background on Lattices
Lattice-based Crypto vs. “Classical” PKC
Program of the DayLattice-
Based
Crypto: A
long storyLattices and Cryptology
Two years stand out:
1982
1996First use of Publication
lattices in of LLL
cryptanalysis1982Ajtai’s worst-case to
average-case reduction
Invention of
NTRU1996Lattices and Cryptology
Two years stand out:
1982: First use of lattices in
cryptanalysis
1996: First crypto schemes based on
hard lattice problemsLattice-based Crypto
Somewhat a revival of knapsack crypto
(MerkleHellman78,...)
Two Families:
“Theoretical”: [Ajtai96...] focus on security
proofs.
“Applied”: [NTRU96...] focus on efﬁciency.
They “interact” more and more:
[Micc02,GPV08,Gentry09,Peikert10,LPR10,...]Lattice Problems in Crypto
In many crypto schemes, one actually deals
with problems not deﬁned using lattices:
SIS. ‘minicrypt’: OWF, hashing, signatures,
identiﬁcation.
LWE. ‘cryptomania’: pk-encryption, (H)IBE,
oblivious transfer.
Both are connected to lattice problems.Background
on Lattices