Paper 2020/206

A Post-Quantum Non-Interactive Key-Exchange Protocol from Coding Theory

Jean-Francois Biasse, Giacomo Micheli, Edoardo Persichetti, and Paolo Santini

Abstract

This work introduces a new non-interactive key-exchange protocol, based on the hardness of the Code Equivalence Problem, a staple problem in coding theory. The protocol is modelled on the Diffie-Hellman framework. The novelty of the construction resides in the use of the code equivalence problem as the sole hardness assumption. To the best of our knowledge, our construction represents the first code-based non-interactive key-exchange protocol, and in fact, the first post-quantum scheme of this kind which is not built upon supersingular isogenies. Our scheme provides significantly better performance than its isogeny counterparts in terms of execution time (at the cost of larger keys). This performance trade-off is favorable to users in most of the cases where the bandwidth is not severely constrained.