Paper 2021/026

A Gapless Code-Based Hash Proof System based on RQC and its Applications

Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Yann Connan, and Philippe Gaborit


Cramer and Shoup introduced at Eurocrypt’02 the concept of hash proof system, also designated as smooth projective hash functions. Since then, they have found several applications, from building CCA-2 encryption as they were initially created for, to being at the core of several authenticated key exchange or even allowing witness encryption. In the post-quantum setting, the very few candidates use a language based on ciphertexts to build their hash proof system. This choice seems to inherently introduce a gap, as some elements outside the language could not be distinguish from those in the language. This creates a lawless zone, where an adversary can possibly mount an undetectable attack, particularly problematic when trying to prove security in the UC framework. We show that this gap could be completely withdrawn using code-based cryptography. Starting from RQC, a candidate selected for the second round of the National Institute of Standards and Technology (NIST) post-quantum cryptography standardization project, we show how to build such a hash proof system from code-based cryptography and present a way, based on a proof of knowledge, to fully negate the gap. We propose two applications of our construction, a witness encryption scheme and a password authenticated key exchange (PAKE).

Available format(s)
Publication info
Preprint. MINOR revision.
Code-Based CryptographyHash Proof SystemRank Quasi-Cyclic SchemeWitness EncryptionPassword Authenticated Key Exchange
Contact author(s)
loic bidoux @ owndata org
2021-01-12: received
Short URL
Creative Commons Attribution


      author = {Slim Bettaieb and Loïc Bidoux and Olivier Blazy and Yann Connan and Philippe Gaborit},
      title = {A Gapless Code-Based Hash Proof System based on RQC and its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/026},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.