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

Hoffmann, Clément;Libert, Benoît;Momin, Charles;Peters, Thomas;Standaert, François-Xavier
(2023) Public-Key Cryptography - PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography — Location: Atlanta, USA (7.May.2023)

Files

LRPQ.pdf
  • Open Access
  • Adobe PDF
  • 1.13 MB
Download

Details

Authors
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 to reduce this cost. It leverages various ingredients in order to enable efficient side-channel protected implementations such as: (i) the rigidity property (which intuitively means that the 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 problems 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, the operations of POLKA can be protected against leakage in a cheaper way than state-of-the-art designs, opening the way towards schemes that are both quantum-safe and leakage-resistant.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Hoffmann, C., Libert, B., Momin, C., Peters, T., & Standaert, F.-X. (2023). POLKA: Towards Leakage-Resistant Post-quantum CCA-Secure Public Key Encryption. PKC 2023 - LNCS, p. 114-144. https://doi.org/10.1007/978-3-031-31368-4_5