Paper 2023/1798

Somewhat Homomorphic Encryption based on Random Codes

Carlos Aguilar-Melchor, Sandbox AQ
Victor Dyseryn, XLIM, University of Limoges
Philippe Gaborit, XLIM, University of Limoges

We present a secret-key encryption scheme based on random rank metric ideal linear codes with a simple decryption circuit. It supports unlimited homomorphic additions and plaintext absorptions as well as a fixed arbitrary number of homomorphic multiplications. We study a candidate bootstrapping algorithm that requires no multiplication but additions and plaintext absorptions only. This latter operation is therefore very efficient in our scheme, whereas bootstrapping is usually the main reason which penalizes the performance of other fully homomorphic encryption schemes. However, the security reduction of our scheme restricts the number of independent ciphertexts that can be published. In particular, this prevents to securely evaluate the bootstrapping algorithm as the number of ciphertexts in the key switching material is too large. Our scheme is nonetheless the first somewhat homomorphic encryption scheme based on random ideal codes and a first step towards full homomorphism. Random ideal codes give stronger security guarantees as opposed to existing constructions based on highly structured codes. We give concrete parameters for our scheme that shows that it achieves competitive sizes and performance, with a key size of 3.7 kB and a ciphertext size of 0.9 kB when a single multiplication is allowed.

Available format(s)
Cryptographic protocols
Publication info
Homomorphic encryptionRank metricIdeal codesCode-based cryptographyBootstrapping
Contact author(s)
carlos @ sandboxquantum com
victor dyseryn_fostier @ unilim fr
gaborit @ unilim fr
2023-11-24: approved
2023-11-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carlos Aguilar-Melchor and Victor Dyseryn and Philippe Gaborit},
      title = {Somewhat Homomorphic Encryption based on Random Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1798},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.