VI-MSS workshop: Mathematical and Statistical Aspects of Cryptography

The Virtual Institute for Mathematical and Statistical Sciences (VI-MSS) hosted a workshop on the Mathematical and Statistical Aspects of Cryptography from the 12th to the 14th of January. It took place at the Indian Statistical Institute (ISI) in Kolkata, India. The main focus of the workshop was public key cryptography and this resulted in talks on a broad range of subjects such as lattices, elliptic curves, RSA and even braid cryptography. These talks ranged from practical (the bit-security of ECC and parallel hardware implementations for cryptanalysis) to theoretical (weakly-programmable random oracles and non-malleable commitments). A sizeable portion of the talks was about lattice-based cryptography and the disparity between theory and practice in this area was a general theme throughout the talks. This led to discussions on how to bridge this gap between theory and practice.

One good example of how to do this was illustrated by Damien Stehle in his talk on making NTRU as secure as worst-case problems over lattices (pdf). While this paper describes some changes to the NTRU cryptosystem that lead to theoretical proofs of security, Damien explained that the point was not that these changes should be made in practice, as the result will not be as efficient as desired. Rather, his point was that NTRU is already quite close to something that is provably secure, which should inspire confidence in the system. Additionally, some minor changes might improve the security while retaining efficiency.

Another interesting talk was given by Nadia Heninger on approximate divisors via lattices (pdf). The approximate integer common divisor problem was first posed by Howgrave-Graham (pdf), who also proposed an algorithm to solve it using lattice reduction. The problem arises when factoring numbers while having some information on one of the factors, which is of interest in the RSA setting, where the modulus can be factored if enough bits from one of the primes have leaked. Recently, a multivariate version of the problem was used as a hardness assumption for the construction of fully homomorphic encryption over the integers (pdf) and for an improved version of this construction (pdf). In the talk, Nadia showed how to extend Howgrave-Graham's approach to this multivariate version, the partial approximate common divisor problem. An issue that arises in the analysis of this problem is that current lattice reduction methods such as the LLL algorithm have approximation factors that are exponential in the dimension of the lattice. If these approximation factors were even slightly subexponential in the dimension, this would lead to a polynomial-time break of the fully homomorphic encryption schemes based on approximate common divisor problems. Nadia also showed an analogy of approximate common divisor problems for polynomials, which leads to applications in coding theory such as Reed-Solomon codes and Parvaresh-Vardy codes. An interesting open problem proposed in the talk was to extend the approach to number fields without having to perform lattice basis reduction on the canonical embedding. This would allow for more efficient attacks on fully homomorphic encryption over ideal lattices, as using the canonical embedding leads to a gigantic blowup of the exponential factor for lattice basis reduction methods in this case.