We proposc multi-bit versions of several single-bit cryptosystems based on lattioe problems, the error-ffee version of the Ajtai-Dwork cryptosystem by Goldoeich, Goldwasser, and Halevi $[\mathrm{C}\mathrm{R}\mathrm{Y}\mathrm{P}\Gamma \mathrm{O} ' 97]$ , the Regev cryptosystems [STOC $2\alpha 13$ and STOC 205], and the Ajtai $\mathrm{c}\iota \mathrm{y}\mathrm{p}-$ tosystem $[\mathrm{S}\mathrm{T}\propto 2W5]$ .Based on a common $\mathrm{s}\mathrm{t}\mathrm{I}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}$ amongst them, we devclop a generic oechnique for constructin $\mathrm{g}$ their multi-bit versions without increase in the size of ciphertexts.By analyzing the trade-off between the decryption enor and the hardness of underlying lattice problems.it is shown that our multi-bit versions encrypt $O(\log n)$ -bit plaintexts into ciphertexts of the same length as the original ones with the reasonable sacrifices of the hxdness of the underlying lattice problems.Our technique also provides a ncw algebraic property pseudo-homomorphism of the lattice-based crypto- systems.We proposc multi-bit versions of several single-bit cryptosystems based on lattioe problems, the error-ffee version of the Ajtai-Dwork cryptosystem by Goldoeich, Goldwasser, and Halevi $[\mathrm{C}\mathrm{R}\mathrm{Y}\mathrm{P}\Gamma \mathrm{O} ' 97]$ , the Regev cryptosystems [STOC $2\alpha 13$ and STOC 205], and the Ajtai $\mathrm{c}\iota \mathrm{y}\mathrm{p}-$ tosystem $[\mathrm{S}\mathrm{T}\propto 2W5]$ .Based on a common $\mathrm{s}\mathrm{t}\mathrm{I}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}$ amongst them, we devclop a generic oechnique for constructin $\mathrm{g}$ their multi-bit versions without increase in the size of ciphertexts.By analyzing the trade-off between the decryption enor and the hardness of underlying lattice problems.it is shown that our multi-bit versions encrypt $O(\log n)$ -bit plaintexts into ciphertexts of the same length as the original ones with the reasonable sacrifices of the hxdness of the underlying lattice problems.Our technique also provides a ncw algebraic property pseudo-homomorphism of the lattice-based crypto- systems.

May 1, 20061 citation

An optimally secure relativized cryptosystem

Giles Brassard

ACM SIGACT NewsJan 1, 19838 citations

Approaches to Efficient and Robust Cryptographic Protocols

Bartosz Przydatek

Jan 1, 20070 citations

Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

Chris Peikert

We construct public-key cryptosystems that are secure assuming the *worst-case* hardness of approximating the shortest vector problem on lattices. Prior cryptosystems with worst-case connections (e.g., the Ajtai-Dwork system) were based either on a *special case* of the shortest vector problem, or on the conjectured hardness of lattice problems for *quantum* algorithms. Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions. (Duration: 30 minutes, on or before Wednesday.)We construct public-key cryptosystems that are secure assuming the *worst-case* hardness of approximating the shortest vector problem on lattices. Prior cryptosystems with worst-case connections (e.g., the Ajtai-Dwork system) were based either on a *special case* of the shortest vector problem, or on the conjectured hardness of lattice problems for *quantum* algorithms. Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions. (Duration: 30 minutes, on or before Wednesday.)

Dagstuhl Seminar ProceedingsJan 1, 2009192 citations

We proposc multi-bit versions of several single-bit cryptosystems based on lattioe problems, the error-ffee version of the Ajtai-Dwork cryptosystem by Goldoeich, Goldwasser, and Halevi

[\mathrm{C}\mathrm{R}\mathrm{Y}\mathrm{P}\Gamma \mathrm{O} ' 97]

, the Regev cryptosystems [STOC

2\alpha 13

and STOC 205], and the Ajtai

\mathrm{c}\iota \mathrm{y}\mathrm{p}-

tosystem

[\mathrm{S}\mathrm{T}\propto 2W5]

.Based on a common

\mathrm{s}\mathrm{t}\mathrm{I}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}

amongst them, we devclop a generic oechnique for constructin

\mathrm{g}

their multi-bit versions without increase in the size of ciphertexts.By analyzing the trade-off between the decryption enor and the hardness of underlying lattice problems.it is shown that our multi-bit versions encrypt

O(\log n)

-bit plaintexts into ciphertexts of the same length as the original ones with the reasonable sacrifices of the hxdness of the underlying lattice problems.Our technique also provides a ncw algebraic property pseudo-homomorphism of the lattice-based crypto- systems.