HARE: Compact HQC via Distance-Informed Erasure Decoding

Abstract. We propose HARE, a compact variant of the HQC (Hamming Quasi-Cyclic) code-based key encapsulation mechanism. HARE reduces the public key and ciphertext sizes of HQC by introducing a distance-informed erasure decoding technique. Our key insight is that by exploiting the distance information available during decoding, we can correct erasures more efficiently than the standard decoding used in HQC, enabling smaller parameters while maintaining the same security level. We provide detailed security analysis and parameter selection, and show that HARE achieves significantly better bandwidth than the standard HQC submission to the NIST post-quantum standardization process, with minimal impact on computational performance.