Paper 2022/873

\(\texttt{POLKA}\): Towards Leakage-Resistant Post-Quantum CCA-Secure Public Key Encryption

Clément Hoffmann, UCLouvain, Belgium
Benoît Libert, CNRS, ENS de Lyon, France
Charles Momin, UCLouvain, Belgium
Thomas Peters, UCLouvain, Belgium
François-Xavier Standaert, UCLouvain, Belgium

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 \(\texttt{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 \(\texttt{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.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2023
Post-QuantumHybrid EncryptionRLWESide-Channel
Contact author(s)
clement hoffmann @ uclouvain be
benoit libert @ ens-lyon fr
charles momin @ uclouvain be
thomas peters @ uclouvain be
fstandae @ uclouvain be
2023-03-23: revised
2022-07-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Clément Hoffmann and Benoît Libert and Charles Momin and Thomas Peters and François-Xavier Standaert},
      title = {\(\texttt{{POLKA}}\): Towards Leakage-Resistant Post-Quantum {CCA}-Secure Public Key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/873},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.