International Association for Cryptologic Research

International Association
for Cryptologic Research


POLKA: Towards Leakage-Resistant Post-Quantum CCA-Secure Public Key Encryption

Clément Hoffmann , UCLouvain, Belgium
Benoit Libert , Zama, France
Charles Momin , UCLouvain, Belgium
Thomas Peters , UCLouvain, Belgium
François-Xavier Standaert , UCLouvain, Belgium
DOI: 10.1007/978-3-031-31368-4_5
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: As for any cryptographic algorithm, the deployment of post-quantum CCA-secure public key encryption schemes may come with the need to be protected against side-channel attacks. For existing post-quantum schemes that have not been developed with leakage in mind, recent results showed that the cost of these protections can make their implementations more expensive by orders of magnitude. In this paper, we describe a new design, coined POLKA, that is specifically tailored for this purpose. It leverages various ingredients in order to enable efficient side-channel protected implementations such as: (i) the rigidity property (which intuitively means that de-randomized encryption and decryption are injective functions) to avoid the very leaky re-encryption step of the Fujisaki-Okamoto transform, (ii) the randomization of the decryption thanks to the incorporation of a dummy ciphertext, removing the adversary's control of its intermediate computations and making these computations ephemeral, (iii) key-homomorphic computations that can be masked against side-channel attacks with overheads that scale linearly in the number of shares, (iv) hard physical learning problem to argue about the security of some critical unmasked operations. Furthermore, we use an explicit rejection mechanism (returning an error symbol for invalid ciphertexts) to avoid the additional leakage caused by implicit rejection. As a result, all the operations of POLKA can be protected against leakage in a much cheaper way than state-of-the-art designs, opening the way towards schemes that are both quantum-safe and leakage-resistant.
  title={POLKA: Towards Leakage-Resistant Post-Quantum CCA-Secure Public Key Encryption},
  author={Clément Hoffmann and Benoit Libert and Charles Momin and Thomas Peters and François-Xavier Standaert},