We provide two homomorphic-based BKEM constructions, based on Gen-try’s homomorphic encryption scheme (Section2.3) and theNTRUvariant by Stehlé and Steinfeld (Section2.4). We show that (for some parameters) our BKEM schemes are post-quantum secure, by Theorem5, as long as the
underlying HE schemes are post-quantum secure [24,36,41]. We only re-quire the HE scheme to support one homomorphic operation, and we have chosen addition. OurHEschemes do not need to support bootstrapping or any multiplicative depth.
5.1 Two Homomorphic-basedBKEMSchemes
Let HE = (KGHE,EncHE,DecHE) be a homomorphic encryption scheme described in Section2.3or Section2.4with(1−3)-correctness for negli-gible3. LetLbe any full-rank n-dimensional lattice, for any ∈ (0,1), s≥ η(L), andr ≥2ω(log(n))·s. The abstract construction ofHE-BKEM is in Figure8.
KG(λ) :
pk,sk←KGHE(λ) (ek,dk)←(pk,sk) returnek,dk Encapek :
k←− K$ F
C ←EncHE(ek, s, k) returnC, k
Blindek(C) : k0←− K$ R
C0 ←EncHE(ek, r, k0) C˜ ←AddHE(C, C0) uk ← −k0 mod B returnC,˜ uk Decapdk( ˜C) :
˜k←DecHE(dk,C)˜ return˜k
Unblinduk(˜k) :
k←˜k+uk mod B returnk
Figure 8:HE-BKEM, whereBis the basis of the plaintext spaceP.
5.2 Constructions of random-looking blinded keys
We want the blinded keys to be in the-blinded blinded key setSwith high probability, and we analyze the requirements of the blinding values. We provide two constructions of the-blinded blinded keys setSas follows.
Construction I. A file encryption key ofHE-BKEMis a random element located in a subspace of the underlyingHE scheme’s message space M.
We want to take a small file encryption keykand add a large blinding value k0to produce a slightly larger blinded key˜k, hence, the corresponding key sets should satisfyKF ⊆ KR ⊆ KB ⊆ M Suppose MisHE scheme’s so the probability that a blinded key is located in the-blinded blinded set is
In this construction, HE-BKEM has -blinded blinded keys with =
n b√q
2c. For suitably largeq, the abovecan be made negligible.
Construction II. Let the file encryption keykbe an element in a subset ofM: we want to add a random blinding valuek0from the whole message space M to produce a random-looking blinded key k, hence, the corre-˜ sponding key sets should satisfyKF ⊆ KR=KB =M. For any blinded keyk˜ ∈ Mand any file encryption keyk ∈ KF there exists a unique ran-dom valuek0 = ˜k−k mod B∈ Msuch thatk˜ =k+k0 modB, thus the-blinded blinded setSisMand thus
Prh
˜k=k+k0 mod B∈S|k←− K$ F, k0 ←− M$ i
= 1.
In this construction,HE-BKEMhas-blinded blinded keys with= 0.
Remark 2. Both of these constructions can be applied to our HE-BKEM schemes.
5.3 Construction of fresh-looking blinded encapsulations We claim thatHE-BKEMin Figure8has-blinded blinded encapsulations with negligible. The idea is to take the small constant ciphertext and add a ciphertext with large error(s) and the resulting ciphertext should look like a fresh ciphertext with large error(s). The details are given in the following lemma.
Lemma 4. Let HE-BKEM be a homomorphic based BKEM with the un-derlying homomorphic encryption scheme described in Section 2.3or2.4 Letek be any encapsulation key, and recall that the encryption algorithm EncHE(ek, s,·)uses the discrete Gaussian distributionDL,s,0 as the error distribution. Suppose C0 = EncHE(ek, s, k0) is an encapsulation of the underlying file encryption key k0. For any ∈ (0,1), let s ≥ η(L) and r ≥2ω(log(n))·s, then the statistical distance between the following distri-butions is negligible
X={C0⊕1C0|k0←− K$ R, C0 ←EncHE(ek, r, k0)} Y ={C|k0 ←− K$ R, C ←EncHE(ek, r, k0⊕2k0)}.
Proof. We prove the result for Gentry’s scheme; similar analysis forNTRU follows the same approachch. SupposeC0=k0+e0, wheree0←DL,s,0. Then
C0⊕1EncHE(ek, r, k0) =k0+e0+k0+DL,r,0=k0+k0+e0+DL,r,0.
By Lemma1, we have ke0k > s√
n with negligible probability. For ke0k ≤ s√n, we have ker0k ≤ 2ω(log(n))√n , which is negligible for sufficient largen. By Lemma2, we havee0+DL,r,0 ≈sDL,r,0. Therefore,
C0⊕1EncHE(ek, r, k0)≈s k0+k0+DL,r,0=EncHE(ek, r, k0⊕2k0).
5.4 Indistinguishability of our HE-BKEM
TheHE-BKEMschemes, defined in Section5.1, have random-looking blinded keys, which follows from the designs discussed in Section5.2. Further-more, these schemes have fresh-looking blinded encapsulations, which fol-lows from from Lemma4 discussed in Section5.3. The following corol-laries showGHE-BKEMandNTRU-BKEMareIND-secure BKEMs with post-quantum security.
Corollary 1. LetGHE-BKEMbe a homomorphic-based BKEM described in Section5.1. For negligible, 2, choose parameters as in Lemma4, The-orem1and Thm.2. Suppose GHE-BKEM has2-blinded blinded keys. If there is an algorithm that breaks the indistinguishability ofGHE-BKEM, i.e. the distinguishing advantage of this algorithm against GHE-BKEM getting r blinded encapsulation and their blinded decapsulation tuples is non-negligible, then there exists a quantum algorithm that solves worst-caseSIVP.
Proof. By Lemma4there exists a negligible1such thatGHE-BKEMhas 1-blinded blinded encapsulations. Then we can apply Theorem5, which states that if there is an algorithm that breaks the indistinguishability of GHE-BKEM then there exists an algorithm breaks IND-CPA security of GHE, and by Theorem3 we have a quantum algorithm that solves worst-caseSIVP.
Corollary 2. LetNTRU-BKEMbe a homomorphic-based BKEM described in Section 5.1. For negligible , 2, choose parameters as in Lemma 4, Lemma3, and Thm.4. SupposeNTRU-BKEMhas2-blinded blinded keys.
If there is an algorithm that breaks indistinguishability ofNTRU-BKEM then there exists a quantum algorithm that solvesO(√n/α)-approximate SIVP(orSVP) on ideal lattices.
Proof. Similar to the proof of Corollary1, from Lemma 4and Theorem 5 we know that if there is an algorithm that breaks the indistinguishability of NTRU-BKEMthen there exists an algorithm that breaksIND-CPAsecurity ofNTRU. By Lemma3there exists an adversary solvingR-LWE×HNF and by Theorem4there exists a quantum algorithm that solvesSIVP.
Parameter settings. For our HE-BKEMschemes, the parameters of the underlying homomorphic encryption schemes are chosen from Gentry [24]
or Stehlé and Steinfeld [41], which is required to achieveIND-CPAsecurity.
Furthermore, ourBKEMschemes require thatr= 2ω(log(n))·s, wheresis the standard deviations of a “narrow” Gaussian distributionsDL,s,0andris the standard deviations of a “wider” Gaussian distributionsDL,r,0. We also follows the designs discussed in Section 5.2 to construct random-looking blinded keys. We conclude that for these parameter settings our proposed BKEMschemes are post-quantum secure.
References
[1] Abe, M., Gennaro, R., Kurosawa, K., Shoup, V.: Tag-kem/dem:
A new framework for hybrid encryption and A new analysis of kurosawa-desmedt KEM. In: Cramer, R. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 3494, pp. 128–146. Springer (2005).
https://doi.org/10.1007/11426639_8
[2] Albrecht, M., Bai, S., Ducas, L.: A subfield lattice attack on over-stretched NTRU assumptions - cryptanalysis of some FHE and graded encoding schemes. In: Robshaw, M., Katz, J. (eds.) CRYPTO (1). pp.
153–178. Springer-Verlag (2016). https://doi.org/10.1007/978-3-662-53018-4_6
[3] Alkim, E., Bos, J.W., Ducas, L., Easterbrook, K., LaMac-chia, B., Longa, P., Mironov, I., Nikolaenko, V., Peikert, C., Raghunathan, A., Stebila, D.: FrodoKEM: Learning With Errors Key Encapsulation. https://frodokem.org/files/
FrodoKEM-specification-20190330.pdf, Submission to the NIST Post-Quantum Standardization project, round 2
[4] Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - A new hope. In: Holz, T., Savage, S. (eds.) USENIX Security Symposium. pp. 327–343. USENIX Association (2016) [5] Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky,
V., Schanck, J.M., Schwabe, P., Seiler, G., Stehlé, D.: CRYSTALS-Kyber (version 2.0). https://pq-crystals.org/kyber/
data/kyber-specification-round2.pdf, Submission to the NIST Post-Quantum Standardization project, round 2
[6] Aviram, N., Gellert, K., Jager, T.: Session resumption protocols and efficient forward security for TLS 1.3 0-RTT. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT (2). Lecture Notes in Computer Science, vol.
11477, pp. 117–150. Springer (2019). https://doi.org/10.1007/978-3-030-17656-3_5
[7] Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.:
NTRU prime: Reducing attack surface at low cost. In: Adams, C., Camenisch, J. (eds.) SAC. Lecture Notes in Computer Science, vol.
10719, pp. 235–260. Springer (2017)
[8] Bos, J.W., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Niko-laenko, V., Raghunathan, A., Stebila, D.: Frodo: Take off the ring!
practical, quantum-secure key exchange from LWE. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM Conference on Computer and Communications Security. pp. 1006–
1018. ACM (2016). https://doi.org/10.1145/2976749.2978425 [9] Bos, J.W., Lauter, K.E., Loftus, J., Naehrig, M.: Improved security
for a ring-based fully homomorphic encryption scheme. In: Stam, M.
(ed.) IMACC. Lecture Notes in Computer Science, vol. 8308, pp. 45–
64. Springer (2013). https://doi.org/10.1007/978-3-642-45239-0_4 [10] Boyd, C., Davies, G.T., Gjøsteen, K., Jiang, Y.: Offline assisted
group key exchange. In: Chen, L., Manulis, M., Schneider, S. (eds.) ISC. Lecture Notes in Computer Science, vol. 11060, pp. 268–285.
Springer (2018). https://doi.org/10.1007/978-3-319-99136-8_15 [11] Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled)
fully homomorphic encryption without bootstrapping. In:
Goldwasser, S. (ed.) ITCS. pp. 309–325. ACM (2012).
https://doi.org/10.1145/2090236.2090262
[12] Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-lwe and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 6841, pp.
505–524. Springer (2011). https://doi.org/10.1007/978-3-642-22792-9_29
[13] Chen, C., Danba, O., Hoffstein, J., Hülsing, A., Rijneveld, J., Schanck, J.M., Schwabe, P., Whyte, W., Zhang, Z.: NTRU). https://
ntru.org/f/ntru-20190330.pdf, Submission to the NIST Post-Quantum Standardization project, round 2
[14] Cheon, J.H., Han, K., Kim, J., Lee, C., Son, Y.: A practical post-quantum public-key cryptosystem based on spLWE. In: Hong, S., Park, J.H. (eds.) ICISC. Lecture Notes in Computer Science, vol.
10157, pp. 51–74 (2016). https://doi.org/10.1007/978-3-319-53177-9_3
[15] Cheon, J.H., Jeong, J., Lee, C.: An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level en-coding of zero. LMS Journal of Computation and Mathematics19(A), 255–266 (2016). https://doi.org/10.1112/S1461157016000371 [16] Cheon, J.H., Kim, A., Kim, M., Song, Y.S.: Homomorphic encryption
for arithmetic of approximate numbers. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT (1). Lecture Notes in Computer Science, vol. 10624, pp.
409–437. Springer (2017). https://doi.org/10.1007/978-3-319-70694-8_15
[17] Cohn-Gordon, K., Cremers, C., Garratt, L., Millican, J., Mil-ner, K.: On ends-to-ends encryption: Asynchronous group mes-saging with strong security guarantees. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) CCS. pp. 1802–1819. ACM (2018).
https://doi.org/10.1007/978-3-030-17656-3_5
[18] Cramer, R., Shoup, V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext
at-tack. Cryptology ePrint Archive, Report 2001/108 (2001), https:
//eprint.iacr.org/2001/108
[19] Cramer, R., Shoup, V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003).
https://doi.org/10.1137/S0097539702403773
[20] D’Anvers, J., Karmakar, A., Roy, S.S., Vercauteren, F.: Saber:
Module-LWR based key exchange, cpa-secure encryption and cca-secure KEM. In: Joux, A., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT. Lecture Notes in Computer Science, vol. 10831, pp.
282–305. Springer (2018). https://doi.org/10.1007/978-3-319-89339-6_16
[21] Dent, A.W.: A designer’s guide to KEMs. In: Paterson, K.G. (ed.) IMACC. Lecture Notes in Computer Science, vol. 2898, pp. 133–151.
Springer (2003). https://doi.org/10.1007/978-3-540-40974-8_12 [22] Derler, D., Jager, T., Slamanig, D., Striecks, C.: Bloom filter
encryp-tion and applicaencryp-tions to efficient forward-secret 0-rtt key exchange.
In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT (3). Lecture Notes in Computer Science, vol. 10822, pp. 425–455. Springer (2018).
https://doi.org/10.1007/978-3-319-78372-7_14
[23] Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144 (2012), https://eprint.iacr.org/2012/144
[24] Gentry, C.: A Fully Homomorphic Encryption Scheme. Ph.D. thesis, Stanford University, Stanford, CA, USA (2009), aAI3382729
[25] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) STOC. pp.
197–206. ACM (2008). https://doi.org/10.1145/1374376.1374407 [26] Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from
learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO (1).
Lecture Notes in Computer Science, vol. 8042, pp. 75–92. Springer (2013). https://doi.org/10.1007/978-3-642-40041-4_5
[27] Green, M.D., Miers, I.: Forward secure asynchronous messag-ing from puncturable encryption. In: IEEE Symposium on Se-curity and Privacy. pp. 305–320. IEEE Computer Society (2015).
https://doi.org/10.1109/SP.2015.26
[28] Günther, F., Hale, B., Jager, T., Lauer, S.: 0-RTT key exchange with full forward secrecy. In: Coron, J., Nielsen, J.B. (eds.) EUROCRYPT (3). Lecture Notes in Computer Science, vol. 10212, pp. 519–548 (2017). https://doi.org/10.1007/978-3-319-56617-7_18
[29] Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based pub-lic key cryptosystem. In: Buhler, J. (ed.) ANTS. Lecture Notes in Computer Science, vol. 1423, pp. 267–288. Springer (1998).
https://doi.org/10.1007/BFb0054868
[30] Hofheinz, D., Kiltz, E.: Secure hybrid encryption from weakened key encapsulation. In: Menezes, A. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 4622, pp. 553–571. Springer (2007).
https://doi.org/10.1007/978-3-540-74143-5_31
[31] Hülsing, A., Rijneveld, J., Schanck, J.M., Schwabe, P.: High-speed key encapsulation from NTRU. In: Fischer, W., Homma, N. (eds.) CHES. Lecture Notes in Computer Science, vol. 10529, pp. 232–252.
Springer (2017). https://doi.org/10.1007/978-3-319-66787-4_12 [32] Kurosawa, K., Desmedt, Y.: A new paradigm of hybrid
encryp-tion scheme. In: Franklin, M.K. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 3152, pp. 426–442. Springer (2004).
https://doi.org/10.1007/978-3-540-28628-8_26
[33] López-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryp-tion. In: Karloff, H.J., Pitassi, T. (eds.) STOC. pp. 1219–1234. ACM (2012). https://doi.org/10.1145/2213977.2214086
[34] Lu, X., Liu, Y., Jia, D., Xue, H., He, J., Zhang, Z., Liu, Z., Yang, H., Li, B., Wang, K.: LAC Lattice-based Cryptosystems, Submission to the NIST Post-Quantum Standardization project, round 2
[35] Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learn-ing with errors over rlearn-ings. In: Gilbert, H. (ed.) EUROCRYPT. Lec-ture Notes in Computer Science, vol. 6110, pp. 1–23. Springer (2010).
https://doi.org/10.1007/978-3-642-13190-5_1
[36] Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learn-ing with errors over rlearn-ings. J. ACM 60(6), 43:1–43:35 (Nov 2013).
https://doi.org/10.1145/2535925
[37] Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for Ring-LWE cryptography. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT.
Lecture Notes in Computer Science, vol. 7881, pp. 35–54. Springer (2013). https://doi.org/10.1007/978-3-642-38348-9_3
[38] Marlinspike, M., Perrin, T.: The X3DH key agreement protocol.
https://signal.org/docs/specifications/x3dh/
(November 2016)
[39] Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput.37(1), 267–302 (Apr 2007). https://doi.org/10.1137/S0097539705447360
[40] NIST Post-Quantum Cryptography
Stan-dardization. https://csrc.nist.gov/
projects/post-quantum-cryptography/
post-quantum-cryptography-standardization, accessed: 2019-11-15
[41] Stehlé, D., Steinfeld, R.: Making NTRU as secure as worst-case prob-lems over ideal lattices. In: Paterson, K.G. (ed.) EUROCRYPT. pp.
27–47. Lecture Notes In Computer Science, Springer-Verlag (2011).
https://doi.org/10.1007/978-3-642-20465-4_4
[42] The messaging layer security (MLS) protocol. Internet draft, in progress. https://datatracker.ietf.org/wg/mls/
about, accessed: 2019-11-25