Paper 2018/794

Blending FHE-NTRU keys – The Excalibur Property

Louis Goubin and Francisco Vial-Prado


Can Bob give Alice his decryption secret and be convinced that she will not give it to someone else? This is achieved by a proxy re-encryption scheme where Alice does not have Bob’s secret but instead she can transform ciphertexts in order to decrypt them with her own key. In this article, we answer this question in a different perspective, relying on a property that can be found in the well-known modified NTRU encryption scheme. We show how parties can collaborate to one-way-glue their secret-keys together, giving Alice’s secret-key the additional ability to decrypt Bob’s ciphertexts. The main advantage is that the proto cols we propose can be plugged directly to the modified NTRU scheme with no post-key-generation space or time costs, nor any modification of ciphertexts. In addition, this property translates to the NTRU-based multikey homomorphic scheme, allowing to equip a hierarchic chain of users with automatic re-encryption of messages and supporting homomorphic operations of ciphertexts. To achieve this, we propose two-party computation protocols in cyclotomic polynomial rings. We base the security in presence of various types of adversaries on the RLWE and DSPR assumptions, and on two new problems in the modified NTRU ring.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Progress in Cryptology – INDOCRYPT 2016 pp 3-24
cryptographic protocolsmultiparty computaionfully homomorphic encryption
Contact author(s)
fvialp @ gmail com
2018-09-01: received
Short URL
Creative Commons Attribution


      author = {Louis Goubin and Francisco Vial-Prado},
      title = {Blending FHE-NTRU keys – The Excalibur Property},
      howpublished = {Cryptology ePrint Archive, Paper 2018/794},
      year = {2018},
      doi = {10.1007/978-3-319-49890-4_1},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.