Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. (English) Zbl 1400.94132

Summary: In typical applications of homomorphic encryption, the first step consists for Alice of encrypting some plaintext \(m\) under Bob’s public key \(\mathsf {pk}\) and of sending the ciphertext \(c = \mathsf {HE}_{\mathsf {pk}}(m)\) to some third-party evaluator Charlie. This paper specifically considers that first step, i.e., the problem of transmitting \(c\) as efficiently as possible from Alice to Charlie. As others suggested before, a form of compression is achieved using hybrid encryption. Given a symmetric encryption scheme \(\mathsf {E}\), Alice picks a random key \(k\) and sends a much smaller ciphertext \(c^\prime = (\mathsf {HE}_{\mathsf {pk}}(k), \mathsf {E}_k(m))\) that Charlie decompresses homomorphically into the original \(c\) using a decryption circuit \(\mathcal {C}_{{\mathsf {E}^{-1}}}\). In this paper, we revisit that paradigm in light of its concrete implementation constraints, in particular \(\mathsf {E}\) is chosen to be an additive IV-based stream cipher. We investigate the performances offered in this context by Trivium, which belongs to the eSTREAM portfolio, and we also propose a variant with 128-bit security: Kreyvium. We show that Trivium, whose security has been firmly established for over a decade, and the new variant Kreyvium has excellent performance. We also describe a second construction, based on exponentiation in binary fields, which is impractical but sets the lowest depth record to \(8\) for \(128\)-bit security.


94A60 Cryptography
Full Text: DOI Link


[1] Adj, G; Menezes, A; Oliveira, T; Rodríguez-Henríquez, F, Computing discrete logarithms in \({\mathbb{F}_{3^{6*137}}}\) using magma, IACR Cryptol. ePrint Arch., 2014, 57, (2014) · Zbl 1400.11161
[2] M. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, M. Zohner, Ciphers for MPC and FHE, in EUROCRYPT, Part I. LNCS, vol. 9056 (Springer, 2015), pp. 430-454
[3] Algorithms, key size and parameters report 2014. Technical report, ENISA (2014) · Zbl 1402.94055
[4] F. Armknecht, V. Mikhalev, On lightweight stream ciphers with shorter internal states, in FSE. LNCS, vol. 9054, (Springer, 2015), pp. 451-470 · Zbl 1382.94050
[5] J. Aumasson, I. Dinur, W. Meier, A. Shamir, Cube testers and key recovery attacks on reduced-round MD6 and Trivium, in FSE. LNCS, vol. 5665 (Springer, 2009), pp. 1-22 · Zbl 1291.94051
[6] S. Babbage, A space/time trade-off in exhaustive search attacks on stream ciphers, in European Convention on Security and Detection, vol. 408, (IEEE, 1995)
[7] R. Barbulescu, P. Gaudry, A. Joux, E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, in EUROCRYPT. LNCS, vol. 8441 (Springer, 2014), pp. 1-16 · Zbl 1326.11080
[8] M. Bellare, A. Desai, E. Jokipii, P. Rogaway, A concrete security treatment of symmetric encryption, inFOCS, (IEEE Computer Society, 1997), pp. 394-403
[9] C. Berbain, H. Gilbert, On the security of IV dependent stream ciphers, in FSE. LNCS, vol. 4593 (Springer, 2007), pp. 254-273 · Zbl 1186.94423
[10] A. Biryukov, A. Shamir, Cryptanalytic time/memory/data tradeoffs for stream ciphers, in ASIACRYPT. LNCS, vol. 1976 (Springer, 2000), pp. 1-13 · Zbl 0980.94013
[11] M. Bodrato, Towards optimal toom-cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0, in WAIFI. LNCS, vol. 4547 (Springer, 2007), pp. 116-133 · Zbl 1213.68715
[12] J. Borghoff, A. Canteaut, T. Güneysu, E.B. Kavun, M. Knezevic, L.R. Knudsen, G. Leander, V. Nikov, C. Paar, C. Rechberger, P. Rombouts, S.S. Thomsen, T. Yalçin, PRINCE—a low-latency block cipher for pervasive computing applications, in ASIACRYPT. LNCS, vol. 7658 (Springer, 2012), pp. 208-225 · Zbl 1292.94035
[13] J.W. Bos, K.E. Lauter, J. Loftus, M. Naehrig, Improved security for a ring-based fully homomorphic encryption scheme, in IMACC. LNCS, vol. 8308 (Springer, 2013), pp. 45-64 · Zbl 1317.94088
[14] Z. Brakerski, Fully homomorphic encryption without modulus switching from classical GapSVP, in CRYPTO. LNCS, vol. 7417 (Springer, 2012), pp. 868-886 · Zbl 1296.94091
[15] Brakerski, Z; Gentry, C; Vaikuntanathan, V, (leveled) fully homomorphic encryption without bootstrapping, TOCT, 6, 13, (2014) · Zbl 1347.68121
[16] C. Carlet, P. Méaux, Y. Rotella, Boolean functions with restricted input and their robustness; application to the FLIP cipher. IACR Trans. Symmetric Cryptol. 2017(3), 192-227 (2017)
[17] S. Carpov, P. Dubrulle, R. Sirdey, Armadillo: a compilation chain for privacy preserving applications, in ACM CCSW (2015)
[18] A. Chakraborti, A. Chattopadhyay, M. Hassan, M. Nandi, TriviA: a fast and secure authenticated encryption scheme, in CHES. LNCS, vol. 9293 (Springer, 2015), pp. 330-353 · Zbl 1380.94077
[19] M. Chenal, Q. Tang, On key recovery attacks against existing somewhat homomorphic encryption schemes, in LATINCRYPT. LNCS, vol. 8895 (Springer, 2015), pp. 239-258 · Zbl 1370.94495
[20] J.H. Cheon, J. Coron, J. Kim, M.S. Lee, T. Lepoint, M. Tibouchi, A. Yun, Batch fully homomorphic encryption over the integers, in EUROCRYPT. LNCS, vol. 7881 (Springer, 2013), pp. 315-335 · Zbl 1306.94040
[21] I. Chillotti, N. Gama, M. Georgieva, M. Izabachène, Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds, in ASIACRYPT. LNCS, vol. 10031 (Springer, 2016), pp. 3-33 · Zbl 1384.94044
[22] J. Coron, T. Lepoint, M. Tibouchi, Scale-invariant fully homomorphic encryption over the integers, in PKC. LNCS, vol. 8383 (Springer, 2014), pp. 311-328 · Zbl 1335.94041
[23] N. Courtois, W. Meier, Algebraic attacks on stream ciphers with linear feedback, in EUROCRYPT. LNCS, vol. 2656 (Springer, 2003), pp. 345-359 · Zbl 1038.94525
[24] Cramer, R; Shoup, V, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, SIAM J. Comput., 33, 167-226, (2003) · Zbl 1045.94013
[25] C. De Cannière, O. Dunkelman, M. Knezevic, KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers, in CHES. LNCS, vol. 5747 (Springer, 2009), pp. 272-288
[26] C. De Cannière, J. Lano, B. Preneel, Comments on the rediscovery of time memory data tradeoffs. Technical report, eSTREAM—ECRYPT Stream Cipher Project (2005). www.ecrypt.eu.org/stream/papersdir/040.pdf. Accessed 21 Dec 2017
[27] C. De Cannière, B. Preneel, Trivium, in New Stream Cipher Designs—The eSTREAM Finalists. LNCS, vol. 4986 (Springer, 2008), pp. 244-266 · Zbl 1285.94054
[28] Dinur, I; Liu, Y; Meier, W; Wang, Q, Optimized interpolation attacks on lowmc, IACR Cryptol. ePrint Arch., 2015, 418, (2015) · Zbl 1382.94092
[29] I. Dinur, A. Shamir, Cube attacks on tweakable black box polynomials, in EUROCRYPT. LNCS, vol. 5479 (Springer, 2009), pp. 278-299 · Zbl 1239.94045
[30] Doröz, Y; Hu, Y; Sunar, B, Homomorphic AES evaluation using the modified LTV scheme, Des. Codes Cryptogr., 80, 333-358, (2016) · Zbl 1402.94055
[31] Y. Doröz, A. Shahverdi, T. Eisenbarth, B. Sunar, Toward practical homomorphic evaluation of block ciphers using Prince, in WAHC. LNCS, vol. 8438 (Springer, 2014), pp. 208-220
[32] L. Ducas, D. Micciancio, FHEW: bootstrapping homomorphic encryption in less than a second, in EUROCRYPT. LNCS, vol. 9056 (Springer, 2015), pp. 617-640 · Zbl 1370.94509
[33] S. Duval, V. Lallemand, Y. Rotella, Cryptanalysis of the FLIP family of stream ciphers, in CRYPTO. LNCS, vol. 9814 (Springer, 2016), pp. 457-475 · Zbl 1384.94059
[34] ECRYPT—European network of excellence in cryptology: the eSTREAM stream cipher project (2005). http://www.ecrypt.eu.org/stream/. Accessed 21 Dec 2017
[35] Fan, J; Vercauteren, F, Somewhat practical fully homomorphic encryption, IACR Cryptol. ePrint Arch., 2012, 144, (2012)
[36] S. Fau, R. Sirdey, C. Fontaine, C. Aguilar, G. Gogniat, Towards practical program execution over fully homomorphic encryption schemes, in IEEE International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, (2013), pp. 284-290
[37] P. Fouque, T. Vannet, Improving key recovery to 784 and 799 rounds of Trivium using optimized cube attacks, in FSE. LNCS, vol. 8424 (Springer, 2013), pp. 502-517 · Zbl 1321.94058
[38] T. Fuhr, B. Minaud, Match box meet-in-the-middle attack against KATAN, inFSE. LNCS, vol. 8540 (Springer, 2014), pp. 61-81 · Zbl 1382.94106
[39] C. Gentry, Fully homomorphic encryption using ideal lattices, in STOC, (ACM, 2009), pp. 169-178 · Zbl 1304.94059
[40] C. Gentry, S. Halevi, N.P. Smart, Homomorphic evaluation of the AES circuit, in CRYPTO. LNCS, vol. 7417 (Springer, 2012), pp. 850-867 · Zbl 1296.94117
[41] C. Gentry, A. Sahai, B. Waters, Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based, in CRYPTO. LNCS, vol. 8042 (Springer, 2013), pp. 75-92 · Zbl 1310.94148
[42] J.D. Golic, Cryptanalysis of alleged A5 stream cipher, in EUROCRYPT. LNCS, vol. 1233 (Springer, 1997), pp. 239-255
[43] T. Graepel, K.E. Lauter, M. Naehrig, ML confidential: machine learning on encrypted data, in ICISC. LNCS, vol. 7839 (Springer, 2012), pp. 1-21 · Zbl 1293.68110
[44] R. Granger, T. Kleinjung, J. Zumbrägel, Breaking ‘128-bit secure’ supersingular binary curves—(or how to solve discrete logarithms in \({\mathbb{F}_{2^{4 · 1223}}}\) and \({\mathbb{F}_{2^{12 · 367}}}\)), in CRYPTO, Part II. LNCS, vol. 8617 (Springer, 2014), pp. 126-145 · Zbl 1334.94080
[45] S. Halevi, V. Shoup, Algorithms in HElib, in CRYPTO, Part I. LNCS, vol. 8616 (Springer, 2014), pp. 554-571 · Zbl 1343.94061
[46] S. Halevi, V. Shoup, Bootstrapping for HElib, in EUROCRYPT. LNCS, vol. 9056 (Springer, 2015), pp. 641-670 · Zbl 1370.94516
[47] Herranz, J; Hofheinz, D; Kiltz, E, Some (in)sufficient conditions for secure hybrid encryption, Inf. Comput., 208, 1243-1257, (2010) · Zbl 1205.68148
[48] J. Hong, P. Sarkar, New applications of time memory data tradeoffs, in ASIACRYPT. LNCS, vol. 3788 (Springer, 2005), pp. 353-372 · Zbl 1154.68395
[49] T. Iwata, New block cipher modes of operation with beyond the birthday bound security, in FSE. LNCS, vol. 4047 (Springer, 2006), pp. 310-327 · Zbl 1234.94049
[50] T. Jakobsen, L.R. Knudsen, The interpolation attack on block ciphers, in FSE. LNCS, vol. 1267 (Springer, 1997), pp. 28-40 · Zbl 1385.94047
[51] A. Joux, C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms—simplified setting for small characteristic finite fields, in ASIACRYPT, Part I. LNCS, vol. 8873 (Springer, 2014), pp. 378-397 · Zbl 1306.94064
[52] J. Katz, Y. Lindell, Introduction to Modern Cryptography, 2nd edition. Chapman and Hall/CRC Press, Boca Raton (2014) · Zbl 1143.94001
[53] A. Khedr, G. Gulak, V. Vaikuntanathan, SHIELD: scalable homomorphic implementation of encrypted data-classifiers. IEEE Trans. Comput. 65(9), 2848-2858 (2016) · Zbl 1360.68435
[54] S. Knellwolf, W. Meier, M. Naya-Plasencia, conditional differential cryptanalysis of NLFSR-based cryptosystems, inASIACRYPT. LNCS, vol. 6477 (Springer, 2010), pp. 130-145 · Zbl 1253.94056
[55] S. Knellwolf, W. Meier, M, Naya-Plasencia, Conditional differential cryptanalysis of Trivium and KATAN, in SAC. LNCS, vol. 7118 (Springer, 2011), pp. 200-212 · Zbl 1292.94095
[56] K. Lauter, A. López-Alt, M. Naehrig, Private computation on encrypted genomic data, in LATINCRYPT. LNCS (2014) · Zbl 1378.94053
[57] T. Lepoint, M. Naehrig, A comparison of the homomorphic encryption schemes FV and YASHE, in AFRICACRYPT. LNCS, vol. 8469 (Springer, 2014), pp. 318-335 · Zbl 1318.94071
[58] T. Lepoint, P. Paillier, On the minimal number of bootstrappings in homomorphic circuits, in WAHC. LNCS, vol. 7862 (Springer, 2013), pp. 189-200
[59] M. Liu, Degree evaluation of NFSR-based cryptosystems, in CRYPTO. LNCS, vol. 10402 (Springer, 2017) · Zbl 1406.94073
[60] P. Méaux, A. Journault, F.X. Standaert, C. Carlet, Towards stream ciphers for efficient FHE with low-noise ciphertexts, in EUROCRYPT. LNCS, vol. 9665 (Springer, 2016), pp. 311-343 · Zbl 1384.94086
[61] A. Maximov, A. Biryukov, Two trivial attacks on Trivium, in SAC, vol. 4876 (Springer, 2007), pp. 36-55 · Zbl 1154.94418
[62] M. Naehrig, K.E. Lauter, V. Vaikuntanathan, Can homomorphic encryption be practical? in ACM CCSW, (ACM, 2011), pp. 113-124
[63] National Institute of Standards and Technology, Recommendation for block cipher modes of operation. NIST Special Publication 800-38A (2001)
[64] M. Paindavoine, B. Vialla, Minimizing the number of bootstrappings in fully homomorphic encryption, in SAC 2015. LNCS, vol. 9566 (Springer, 2016), pp. 25-43 · Zbl 1339.94057
[65] Pincin, A, A new algorithm for multiplication in finite fields, IEEE Trans. Comput., 38, 1045-1049, (1989) · Zbl 0693.12015
[66] C. Rechberger, The FHEMPCZK-cipher zoo. Presented at the FSE 2016 rump session (2016). http://fse.2016.rump.cr.yp.to/. Accessed 21 Dec 2017
[67] P. Rogaway, Evaluation of some block cipher modes of operation. Cryptrec (2011). http://web.cs.ucdavis.edu/ rogaway/papers/modes.pdf. Accessed 21 Dec 2017
[68] Smart, NP; Vercauteren, F, Fully homomorphic SIMD operations, Des. Codes Cryptogr., 71, 57-81, (2014) · Zbl 1323.94140
[69] Y. Todo, T. Isobe, Y. Hao, W. Meier, Cube attacks on non-blackbox polynomials based on division property, in CRYPTO. LNCS, vol. 10402 (Springer, 2017) · Zbl 1406.94081
[70] K. Yasuda, A new variant of PMAC: beyond the birthday bound, in CRYPTO. LNCS, vol. 6841 (Springer, 2011), pp. 596-609 · Zbl 1290.94139
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.