Multi-bit Cryptosystems Based on Lattice Problems

Keita Xagawa, Akinori Kawachi, Keisuke Tanaka

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.

Jiang Zhang, Zhenfeng Zhang

Shangping Wang, Lihua Liu, Jin Dong Sun +1 more

Concurrent signatures scheme is an effective way to solve the problem of fair exchange without the help of any trusted third party. Until now, all concurrent signatures are based on traditional cryptosystems, but the emergence of quantum computing poses a severe threat to the security of classic public–key cryptosystems. More and more attentions are being paid to lattice–based cryptosystems, which is one of the candidate cryptosystems against the attacks from quantum computing. In this paper, we present a new formal model of multi–party concurrent signatures scheme and a lattice–based multi–party concurrent signatures scheme. The scheme has comparative advantages in both efficiency and security over the existing concurrent signatures schemes based on traditional cryptosystem. In particular, our scheme is constructed based on constant–size ring signatures, and thus we have solved the open problem: how to construct a multi–party concurrent signatures scheme based on constant–size ring signatures, which was proposed by Tonien et al. (2006).

Keita Xagawa

Fletcher Gates

One attractive feature of lattice-based cryptosystems is the existence of security reductions relating the difficulty of breaking the cryptosystem to the difficulty of solving variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As there are no known polynomial-time algorithms which solve these lattice problems, this implies the asymptotic security of the cryptosystem. However, current lattice-based cryptosystems using the learning with errors (LWE) problem select parameters for which the reduction to the underlying lattice problem gives no meaningful assurance of concrete security. We analyze the runtime of the algorithm constructed in the reductions and select parameters for a cryptosystem under which the reductions give 128-bit security. While the resulting LWE-based cryptosystem is somewhat cumbersome, requiring a dimension of n = 1460, this is less than 2 times the dimension in the recently proposed Frodo cryptosystem (Bos et al., ACM CCS 2016), and could be implemented without catastrophic damage to communication times. We also investigate the runtime necessary for a reduction to give meaningful security assurances for current cryptosystems.

한대완