Name
Abstract | ||
|---|---|---|
We describe public key encryption schemes with security provably based on the worst case hardness of the approximate Shortest Vector Problem in some structured lattices, called ideal lattices. Under the assumption that the latter is exponentially hard to solve even with a quantum computer, we achieve CPA-security against subexponential attacks, with (quasi-)optimal asymptotic performance: if n is the security parameter, both keys are of bit-length ${\widetilde{O}}(n)$ and the amortized costs of both encryption and decryption are ${\widetilde{O}}(1)$ per message bit. Our construction adapts the trapdoor one-way function of Gentry et al. (STOC'08), based on the Learning With Errors problem, to structured lattices. Our main technical tools are an adaptation of Ajtai's trapdoor key generation algorithm (ICALP'99) and a re-interpretation of Regev's quantum reduction between the Bounded Distance Decoding problem and sampling short lattice vectors. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-10366-7_36 | IACR Cryptology ePrint Archive |
Keywords | DocType | Volume |
ideal lattices,bounded distance decoding problem,security provably,quantum computer,trapdoor key generation algorithm,public key encryption scheme,errors problem,structured lattice,quantum reduction,trapdoor one-way function,security parameter,efficient public key encryption,shortest vector problem,public key encryption,generic algorithm,one way function | Conference | 2009 |
ISSN | Citations | PageRank |
0302-9743 | 70 | 3.04 |
References | Authors | |
43 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Damien Stehlé | 1 | 1269 | 73.95 |
| Ron Steinfeld | 2 | 1065 | 72.74 |
| Keisuke Tanaka | 3 | 278 | 19.04 |
| Keita Xagawa | 4 | 258 | 20.51 |