A Gapless Post-quantum Hash Proof System in the Hamming Metric

A hash proof system (HPS) is a form of implicit proof of membership to a language. Out of the very few existing post-quantum HPS, most are based on languages of ciphertexts of code-based or lattice-based cryptosystems and inherently suffer from a gap caused by the possibility for an ill-formed ciphertext to decrypt to a valid plaintext. Since this gap is inconvenient when proving the security in the universal composability framework by Canetti et al., Bettaieb et al. proposed the first gapless post-quantum HPS based on the Rank Quasi-Cyclic (RQC) cryptosystem in the rank metric while conjecturing the existence of a similar HPS in the usual Hamming metric. We solve this conjecture by designing a gapless post-quantum HPS based on the Hamming Quasi-Cyclic (HQC) cryptosystem which, in contrast to RQC, is a NIST post-quantum cryptography standardization alternate candidate. We describe a novel proof of validity for HQC ciphertexts, thereby closing the adversarial gap and present a witness encryption scheme secure in the standard model and a password-based authenticated key exchange protocol secure in the Bellare–Pointcheval–Rogaway (BPR) model.