Using the Rényi divergence rather than the statistical distance in lattice-based cryptography

To analyze the efficiency of the homomorphic encryption schemes at the core of the HEAT project, we studied how the Rényi divergence can be used instead of the statistical distance. The Rényi divergence is a measure of closeness of two probability distributions. In the HEAT project, we obtained that the latter divergence can often be used as an alternative to the statistical distance in security proofs for lattice-based cryptography, and therefore in homomorphic encryption schemes.

Our contributions are as follows:

• Smaller signatures for the Hash-and-Sign Gentry-Peikert-Vaikuntanathan signature scheme
• Smaller storage requirement for the Fiat-Shamir BLISS signature scheme
• Alternative proof that the Learning With Errors problem with noise chosen uniformly in an interval is no easier than the Learning With Errors problem with Gaussian noise (and tighter reduction!)
• Smaller parameters for the dual-Regev encryption scheme

and are described in the article

Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance

Shi Bai and Adeline Langlois and Tancrède Lepoint and Damien Stehlé and Ron Steinfeld

This article has been accepted for publication at ASIACRYPT 2015 and will receive the Best Paper Award.

ASIACRYPT 2015 is one of the top-tier conference of cryptography, organized by the IACR, and will take place in December 2015 in New Zealand.

Cryptanalysis of the Co-ACD Assumption

The HEAT project has a new public output: https://eprint.iacr.org/2014/1024

Homomorphic cryptography (at the core of the HEAT project) allows to securely delegate computation over encrypted data and is a very active research area. At ACM-CCS 2014, a top-tier conference on computer and communications security, a new scheme claimed to be the "most efficient of those that support an additive homomorphic property" was proposed by Cheon, Lee and Seo.

Understanding the security of the homomorphic cryptographic schemes is therefore of utmost importance, especially to select the most efficient and secure systems in HEAT. In this paper that will appear at CRYPTO 2015, a top-tier conference in cryptography, we show that the latter scheme is completely insecure. We present new lattice-based attacks that are effectively devastating for the proposed constructions. More precisely, we show that the parameters proposed by Cheon et al. and originally aiming at 128-bit security can be broken in a matter of seconds. And while it is possible to select parameters outside of the range in which our attacks run in polynomial time, they have to be so large as to render the proposed constructions severely uncompetitive (e.g. our asymptotic estimates indicate that 128 bits of security against our attacks require a modulus of at least 400,000 bits).