Name
Title | ||
|---|---|---|
Practical $$\mathsf {MP} \text{- }\mathsf {LWE} $$ -based encryption balancing security-risk versus efficiency. |
Abstract | ||
|---|---|---|
Middle-product learning with errors (
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
) is a variant of the
$$\mathsf {LWE}$$
problem introduced at CRYPTO 2017 by Rosca et al. (Advances in cryptology—CRYPTO, Springer, Berlin, 2017). Asymptotically, the theoretical results of Rosca et al. (2017) suggest that
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
gives lattice-based public-key cryptosystems offering a ‘security-risk vs. efficiency’ trade-off: higher performance than cryptosystems based on unstructured lattices (
$$\mathsf {LWE}$$
problem) and lower risk than cryptosystems based on structured lattices (Polynomial/Ring
$$\mathsf {LWE}$$
problem). However, although promising in theory, Rosca et al. (2017) left the practical implications of
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
for lattice-based cryptography unclear. In this paper, we show how to build practical public-key cryptosystems with strong security guarantees based on
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
. On the implementation side, we present optimised fast algorithms for computing the middle-product operation over polynomial rings
$${\mathbb {Z}}_q[x]$$
, the dominant computation for
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
-based cryptosystems. On the security side, we show how to obtain a nearly tight security proof for
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
from the hardest Polynomial LWE problem over a large family of rings, improving on the loose reduction of Rosca et al. (2017). We also show and analyze an optimised cryptanalysis of
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
that narrows the complexity gap between best known attacks on
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
and Polynomial
$$\mathsf {LWE}$$
. To evaluate the practicality of
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
, we apply our results to construct, implement and optimise parameters for a practical
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
-based public-key cryptosystem,
$$\mathsf {Titanium} $$
, and compare its benchmarks to other lattice-based systems. Our results show that
$$\mathsf {MP} \text{- }\mathsf {LWE} $$
offers a new ‘security-risk vs. efficiency’ trade-off in lattice-based cryptography in practice, not only asymptotically in theory. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s10623-019-00654-5 | Designs, Codes and Cryptography |
Keywords | Field | DocType |
Middle-product learning with errors (
), Lattice-based cryptography, Quantum-resistant cryptography, Public-key encryption, KEM, Cryptography implementation, 68P25 | Discrete mathematics,Combinatorics,Polynomial,Lattice (order),Polynomial ring,Lattice-based cryptography,Mathematics,Learning with errors | Journal |
Volume | Issue | ISSN |
87 | 12 | 0925-1022 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ron Steinfeld | 1 | 23 | 7.99 |
| Amin Sakzad | 2 | 114 | 18.69 |
| Raymond K. Zhao | 3 | 4 | 1.13 |