Automatic tool, Stream ciphers, FiLIP cipher, Boolean functions.
Résumé :
[en] In this article, we propose a new tool to evaluate the security of instances of FiLIP cipher.
TooLIP is user friendly, it automatically evaluates the cost of several attacks on user-defined Boolean
functions. It allows to test new families of filters that are more homomorphic friendly for recent techniques of evaluations, and is designed to easily add new attacks, or change parameters in the considered
attacks. To demonstrate our tool we apply it in three contexts. First we show how the keysize can be
reduced for former instances with XOR-Threshold functions when the amount of encrypted plaintext
obtained by the adversary is limited. Then, we use TooLIP to determine secure instances with filters in
less variables for two new families of Boolean functions, leading to a more efficient evaluation and/or a
reduced bandwidth. Finally, we apply it to find other instances with filters where we know only (bounds
on) the algebraic immunity and resiliency.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
GERARD, François ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron
GINI, Agnese ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust > PI Coron > Team Jean-Sébastien CORON
MEAUX, Pierrick ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron
Co-auteurs externes :
no
Langue du document :
Anglais
Titre :
TooLIP: How to Find New Instances of FiLIP Cipher With Smaller Key Size and New Filters
Date de publication/diffusion :
2024
Nom de la manifestation :
Africacrypt
Date de la manifestation :
10/07 to 12/07
Manifestation à portée :
International
Titre de l'ouvrage principal :
Africacrypt
Maison d'édition :
Springer
Peer reviewed :
Peer reviewed
Focus Area :
Security, Reliability and Trust
Projet européen :
H2020 - 787390 - CLOUDMAP - Cloud Computing via Homomorphic Encryption and Multilinear Maps
[ACG+06] Armknecht, F., Carlet, C., Gaborit, P., Künzli, S., Meier, W., Ruatta, O.: Efficient computation of algebraic immunity for algebraic and fast algebraic attacks. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 147–164. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_10
Applebaum, B., Lovett, S.: Algebraic attacks against random local functions and their countermeasures. In: Wichs, D., Mansour, Y. (eds.) 48th ACM STOC. ACM Press (2016)
Applebaum, B., Lovett, S.: Algebraic attacks against random local functions and their countermeasures. SIAM J. Comput. 52–79 (2018)
Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)
Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. Cryptology ePrint Archive, Paper 2015/046 (2015)
[ARS+15] Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EURO-CRYPT 2015. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_17
[BIP+22] Bonte, C., Iliashenko, I., Park, J., Pereira, H.V.L., Smart, N.P.: FINAL: faster FHE instantiated with NTRU and LWE. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022. LNCS, vol. 13792, pp. 188–215. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22966-4_7
Bellare, M., Yee, B.: Forward-security in private-key cryptography. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 1–18. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36563-X_1
Carlet, C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021)
[CDM+18] Couteau, G., Dupin, A., Méaux, P., Rossi, M., Rotella, Y.: On the concrete security of Goldreich’s pseudorandom generator. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part I. LNCS, vol. 11273, pp. 96–124. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_4
Cong, K., Das, D., Park, J., Pereira, H.V.L.: SortingHat: efficient private decision tree evaluation via homomorphic encryption and transciphering. In: ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, pp. 563–577 (2022)
Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_1
[CHK+21] Cho, J., et al.: Transciphering framework for approximate homomorphic encryption. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13092, pp. 640–669. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92078-4_22
Cosseron, O., Hoffmann, C., Méaux, P., Standaert, F.-X.: Towards case-optimized hybrid homomorphic encryption-featuring the Elisabeth stream cipher. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022. LNCS, vol. 13793, pp. 32–67. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22969-5_2
Cid, C., Indrøy, J.P., Raddum, H.: FASTA – a stream cipher for fast FHE evaluation. In: Galbraith, S.D. (ed.) CT-RSA 2022. LNCS, vol. 13161, pp. 451–483. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-95312-6_19
Coron, J.-S., Lepoint, T., Tibouchi, M.: Scale-invariant fully homomorphic encryption over the integers. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 311–328. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_18
Courtois, N.T., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_21
Carlet, C., Méaux, P.: Boolean functions for homomorphic-friendly stream ciphers. In: Gueye, C.T., Persichetti, E., Cayrel, P.-L., Buchmann, J. (eds.) A2C 2019. CCIS, vol. 1133, pp. 166–182. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36237-9_10
Carlet, C., Méaux, P.: A complete study of two classes of Boolean functions: direct sums of monomials and threshold functions. IEEE Trans. Inf. Theory 68(5), 3404–3425 (2022)
Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_11
[Cou03b] Courtois, N.T.: Higher order correlation attacks, XL algorithm and cryptanalysis of toyocrypt. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 182–199. Springer, Heidelberg (2003). https://doi.org/10. 1007/3-540-36552-4_13
Cogliati, B., Tanguy, T.: Multi-user security bound for filter permutators in the random oracle model. Des. Codes Cryptogr. 87(7), 1621–1638 (2019)
[DEG+18] Dobraunig, C., et al.: Rasta: a cipher with low ANDdepth and Few ANDs per bit. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 662–692. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_22
[DGH+21] Dobraunig, C., Grassi, L., Helminger, L., Rechberger, C., Schofnegger, M., Walch, R.: Pasta: a case for hybrid homomorphic encryption. IACR Cryptol. ePrint Arch. 731 (2021)
Didier, F.: A new upper bound on the block error probability after decoding over the erasure channel. IEEE Trans. Inf. Theory 52(10), 4496–4503 (2006)
[DLR16] Duval, S., Lallemand, V., Rotella, Y.: Cryptanalysis of the FLIP family of stream ciphers. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 457–475. Springer, Heidelberg (2016). https://doi. org/10.1007/978-3-662-53018-4_17
Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 617–640. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_24
Dupin, A., Méaux, P., Rossi, M.: On the algebraic immunity-resiliency trade-off, implications for Goldreich’s pseudorandom generator. IACR Cryptol. ePrint Arch. 649 (2021)
Faugère, J.-C.: A new efficient algorithm for computing Groebner bases. J. Pure Appl. Algebra 139, 61–88 (1999)
Faugère, J.C.: A new efficient algorithm for computing Grobner bases without reduction to zero. In: Workshop on application of Groebner Bases 2002, Catania, Spain (2002)
Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES circuit. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 850–867. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_49
Goldreich, O.: Candidate one-way functions based on expander graphs. Electron. Colloquium Comput. Complexity (ECCC) 7(90) (2000)
[HKC+20] Ha, J., et al.: Masta: an he-friendly cipher using modular arithmetic. IEEE Access 8, 194741–194751 (2020)
[HKL+22] Ha, J., Kim, S., Lee, B., Lee, J., Son, M.: Rubato: noisy ciphers for approximate homomorphic encryption. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13275, pp. 581–610. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06944-4_20
Hebborn, P., Leander, G.: Dasta-alternative linear layer for rasta. IACR Trans. Symmetric Cryptol. 2020(3), 46–86 (2020)
Hoffmann, C., Méaux, P., Ricosset, T.: Transciphering, using FiLIP and TFHE for an efficient delegation of computation. In: Bhargavan, K., Oswald, E., Prabhakaran, M. (eds.) INDOCRYPT 2020. LNCS, vol. 12578, pp. 39–61. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-65277-7_3
Hoffmann, C., Méaux, P., Standaert, F.-X.: The patching landscape of Elisabeth-4 and the mixed filter permutator paradigm. IACR Cryptol. ePrint Arch. 1895 (2023)
Lepoint, T., Naehrig, M.: A comparison of the homomorphic encryption schemes FV and YASHE. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT 2014. LNCS, vol. 8469, pp. 318–335. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06734-6_20
Lobanov, M.S.: Exact relations between nonlinearity and algebraic immunity. J. Appl. Ind. Math. 3(3), 367–376 (2009)
Méaux, P., Carlet, C., Journault, A., Standaert, F.-X.: Improved filter permutators: combining symmetric encryption design, Boolean functions, low complexity cryptography, and homomorphic encryption, for private delegation of computations. Cryptology ePrint Archive, Report 2019/483 (2019)
Méaux, P., Carlet, C., Journault, A., Standaert, F.-X.: Improved filter permutators for efficient FHE: better instances and implementations. In: Hao, F., Ruj, S., Sen Gupta, S. (eds.) INDOCRYPT 2019. LNCS, vol. 11898, pp. 68–91. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35423-7_4
[Méa22] Méaux, P.: On the algebraic immunity of direct sum constructions. Discret. Appl. Math. 320, 223–234 (2022)
Méaux, P., Journault, A., Standaert, F.-X., Carlet, C.: Towards stream ciphers for efficient FHE with low-noise ciphertexts. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 311–343. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_13
Meier, W., Pasalic, E., Carlet, C.: Algebraic attacks and decomposition of Boolean functions. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 474–491. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_28
Méaux, P., Park, J., Pereira, H.V.L.: Towards practical transciphering for FHE with setup independent of the plaintext space. IACR Cryptol. ePrint Arch. 1531 (2023)
Naehrig, M., Lauter, K.E., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: CCSW, pp. 113–124. ACM (2011)
[Üna23] Ünal, A.: Worst-case subexponential attacks on PRGs of constant degree or constant locality. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14004, pp. 25–54. Springer, Cham (2023). https://doi.org/10. 1007/978-3-031-30545-0_2
Yang, J., Guo, Q., Johansson, T., Lentmaier, M.: Revisiting the concrete security of Goldreich’s pseudorandom generator. IEEE Trans. Inf. Theory 68(2), 1329–1354 (2022)
