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

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.