Code-based Identification and Signature Schemes

In an age of explosive growth of digital communications and electronic data storage, cryptography plays an integral role in our society. Some examples of daily use of cryptography are software updates, e-banking, electronic commerce, ATM cards, etc. The security of most currently used cryptosystems relies on the hardness of the factorization and discrete logarithm problems. However, in 1994 Peter Shor discovered polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. Therefore, it is of extreme importance to develop cryptosystems that remain secure even when the adversary has access to a quantum computer; such systems are called post-quantum cryptosystems. One promising candidate is based on codes; in this thesis we focus more specifically on code-based identification and signature schemes. Public key identification schemes are typically applied in cryptography to reach the goal of entity authentication. Their applications include authentication and access control services such as remote login, credit card purchases and many others. One of the most well-known systems of this kind is the zero-knowledge identification scheme introduced in Crypto 1993 by Stern. It is very fast compared to schemes based on number-theoretic problems since it involves only simple and efficiently executable operations. However, its main drawbacks are the high communication complexity and the large public key size, that makes it impractical for many applications. Our first contribution addresses these drawbacks by taking a step towards reducing communication complexity and public key size simultaneously. To this end, we propose a novel zero-knowledge five-pass identification scheme which improves on Stern's scheme. It reduces the communication complexity by a factor of 25 % compared to Stern's one. Moreover, we obtain a public key of size of 4 KB, whereas Stern's scheme requires 15 KB for the same level of security. To the best of our knowledge, there is no code-based identification scheme with better performance than our proposal using random codes. Our second contribution consists of extending one of the most important paradigms in cryptography, namely the one by Fiat and Shamir. In doing so, we enlarge the class of identification schemes to which the Fiat-Shamir transform can be applied. Additionally, we put forward a generic methodology for proving the security of signature schemes derived from this class of identification schemes. We exemplify our extended paradigm and derive a provably secure signature scheme based on our proposed five-pass identification scheme. In order to contribute to the development of post-quantum schemes with additional features, we present an improved code-based threshold ring signature scheme using our two previous results. Our proposal has a shorter signature length and a smaller public-key size compared to Aguilar et al.'s scheme, which is the reference in this area