Quantum-safe cryptography: crossroads of coding theory and cryptography

Cryptography is a subject area of long history, playing a crucial role in human society ever since the dawn of civilization. Claude Shannon's 1945 paper ``A Mathematical Theory of Cryptography'' is widely regarded as the beginning of modern cryptography, as a new science. In 1949, Shannon published another landmark paper ``A Mathematical Theory of Communication'', founding the area of Information Theory. As noted by Shannon himself, cryptography and information theory are very close together. Cryptography is the science of concealing information, while information theory is primarily concerned with transmitting information. Thus the two subjects can benefit from each other.

Current public-key cryptographic schemes based on integer factoring and discrete logarithm would collapse under quantum computing attacks. This is a serious concern to our modern data-driven society. Among the prospective methods which are expected to be implemented for post-quantum cryptography, lattice and code-based cryptography emerge as the most promising approaches.

Historically, there is a close connection between code and lattice-based cryptography, since both can be viewed as linear codes. The first code-based public-key cryptosystem is the well-known McEliece cryptosystem. Lattice-based cryptography can be viewed as a renaissance of code-based cryptography. In fact, developments in lattice and code-based cryptography often inspire each other.

The paper presents a coherent view of lattice and code-based cryptography in the context of post-quantum cryptography. Since both approaches are based on various problem of linear codes, the reintegration of coding theory and cryptography may give rise to fresh ideas.

###

See the article:

Wang J B, Liu L, Lyu S X, et al. Quantum-safe cryptography: crossroads of coding theory and cryptography. Sci China Inf Sci, 2022, 65(1): 111301, https://doi.org/10.1007/s11432-021-3354-7