Dimitris Simos speaks about Code-based Cryptography @ AIT
Dimitris Simos gives a talk about “An Overview of Code-based Cryptography” at the Austrian Institute of Technology (AIT) on December 5th.
Abstract:
In this talk, we address cryptographic schemes based on a particular type of alternative cryptography originating from error-correcting codes, called code-based cryptography. In this emerging field of cryptography the underlying hard problems which pose as its security assu\-mptions, decoding in a random linear code and recovering the code structure, does not seem so far to be susceptible to attacks mounted by quantum co\-mpu\-ters. The plan of the talk is two-fold: firstly, we introduce the necessary primitives from coding theory and in the aftermath we consider the theory and practice of code-based cryptographic systems. By this term, we mean the cry\-ptosystems in which the algorithmic primitive (the underlying one-way function) uses an error correcting code $\mathcal{C}$. This primitive may consist in adding an error to a word of $\mathcal{C}$ or in computing a syndrome relatively to a parity-check matrix of $\mathcal{C}$.
The first of those systems is a public-key encryption scheme and it was proposed by Robert J. McEliece in 1978. The private key is a random binary irreducible Goppa code and the public key is a random generator matrix of a randomly permuted version of that code. The ciphertext is a codeword to which some errors have been added, and only the owner of the private key (the Goppa code) can remove those errors. Three decades later, some Parameter adjustment have been required, but no attack is known to represent a serious threat on the system, even on a quantum computer. We give the state-of-the-art for the message security and key security of such code-based cryptographic systems, which are related to the hardness of the \textsc{Binary Syndrome Decoding} problem and to the hardness of the \textsc{Permutation Code Equivalence} problem, respectively. Also, we give the setting for these problems when a larger alphabet is desired and how this affects the design of code-based cryptographic systems.
Finally, similar ideas have been used to design other cryptosystems. Among others, we will give an overview of some public-key systems, like the Niederreiter encryption scheme or the CFS signature scheme and in addition some identification schemes like the Girault’s or Stern’s zero-knowledge protocols. We conclude, with some issues regarding the practice of code-based cryptography which is a trade-off between security and efficiency.