Problem statement and proposed solution
This project addresses the security problem of providing fundamental cryptographic mechanisms for the implementation of a secure communication infrastructure--a communication infrastructure that can provide strong security guarantees for Israel and its partners, even in a post-quantum era. To this aim, new cryptographic schemes need to be researched, developed and implemented. It is important to notice that it is not sufficient to explore post-quantum cryptography from a theoretical angle only, focusing on the needed mathematical hardness assumptions. Complementing this (relevant) theoretical work—often emphasizing asymptotic theoretical properties—practical methods and techniques are required that enable a secure implementation of post-quantum cryptography. This includes the choice of adequate parameters and protection of information leakage through side-channels. Once deployed, fixing a weakness at the theoretical or the implementation level can be extremely costly or infeasible. For instance, encrypted data known to the adversary cannot be recalled if a structural weakness in the cryptographic algorithm is found or an implementation turns out to be flawed. Similarly, revoking a verification key for a digital signature scheme can be impractical. More generally, if a secret key leaks from a device because of an insufficiently protected implementation, then a replacement of the implementation may not be possible before the adversary made use of the acquired information.
Consequently, post-quantum cryptography has to cope with two challenges:
- Large-scale quantum computers allow for efficient attacks on currently deployed (asymmetric) cryptographic schemes.[1]
- Side-channel attacks have the potential to break cryptographic schemes with strong (even provable) theoretical guarantees.
With code-and lattice-based cryptography, at least two promising candidate platforms have been identified, that could enable practical encryption and signature schemes—and possibly more: for some specialized applications such as fully-homomorphic encryption or threshold ring signatures, these new platforms actually have the potential to improve over existing constructions, even disregarding the question of quantum attacks. Other mathematical platforms are under exploration—e.g., the use of polynomial systems of equations in multiple variables or of finite and finitely presented non-abelian groups. The theoretical situation for the latter schemes is still rather unclear. Often times the available analyses lack provable security reductions (which are nowadays expected), and repeatedly successful attacks have been mounted against proposed schemes—cryptanalytic successes against braid-group-based schemes [HoSt02], the SFLASH signature scheme(s) [DFSS07], and MST3 [BCM09] being examples. While these platforms do remain interesting candidates, to minimize the financial risk and maximize the practical potential of the proposed work, this project emphasizes cryptographic constructions building on error-correcting codes and lattices. Over the years, the theoretical analysis in these areas, especially for schemes based on error-correcting codes, has reached cryptographic maturity [FiSe09], and the security problem of offering implementation-level defence mechanisms has become more pressing.
[1] For symmetric schemes, a scalable quantum computer may very well speed up an attack (specifically an exhaustive key search), but unlike the situation with asymmetric schemes, a (realistic) increase in key length seems at the moment sufficient to deal with this problem.