nach oben

Cryptography and Communications

Erschienen in:

29.06.2021

On the fast algebraic immunity of threshold functions

verfasst von: Pierrick Méaux

Erschienen in: Cryptography and Communications | Ausgabe 5/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Motivated by the impact of fast algebraic attacks on stream ciphers, and recent constructions using a threshold function as main part of the filtering function, we study the fast algebraic immunity of threshold functions. As a first result, we determine exactly the fast algebraic immunity of all majority functions in more than 8 variables. Then, For all n ≥ 8 and all threshold value between 1 and n we exhibit the fast algebraic immunity for most of the thresholds, and we determine a small range for the value related to the few remaining cases. Finally, provided m ≥ 2, we determine exactly the fast algebraic immunity of all threshold functions in 3 ⋅ 2^m or 3 ⋅ 2^m + 1 variables.

Vorheriger Artikel Quantum synchronizable codes from the Whiteman’s generalized cyclotomy

Nächster Artikel Three-phase Z-complementary triads and almost complementary triads

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Courtois, N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003, volume 2729 of LNCS, pp 176–194. Springer, Heidelberg (2003)

Courtois, N., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003, volume 2656 of LNCS. Springer, Heidelberg (2003)

Applebaum, B., Lovett, S.: Algebraic attacks against random local functions and their countermeasures. In: Wichs, Daniel, Mansour, Y (eds.) 48th ACM STOC. ACM Press, June (2016)

Armknecht, F.: Improving fast algebraic attacks. In: Roy, B.K., Meier, Willi (eds.) FSE 2004, volume 3017 of LNCS, pp 65–82. Springer, Heidelberg (2004)

Hawkes, P., Rose, G.G.: Rewriting variables: The complexity of fast algebraic attacks on stream ciphers. In: Franklin, M. (ed.) CRYPTO 2004, volume 3152 of LNCS, pp 390–406. Springer, Heidelberg (2004)

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, volume 4004 of LNCS. Springer, Heidelberg (2006)

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, Part I, volume 9665 of LNCS, pp 311–343. Springer, Heidelberg (2016)

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., Gupta, S.S. (eds.) Progress in cryptology - INDOCRYPT, volume 11898 of LNCS, pp. 68–91. Springer (2019)

Goldreich, O.: Candidate one-way functions based on expander graphs. Electron. Colloq. Comput. Complex. (ECCC) 7(90) (2000)

10.

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. Cryptol. ePrint Arch., Report 2019/483 (2019)

11.

Hoffmann, C., Méaux, P., Ricosset, T.: Transciphering, using filip and TFHE for an efficient delegation of computation. In: Progress in cryptology - INDOCRYPT 2020 - 21st International conference on cryptology in India, Bangalore, India, December 13-16, 2020, Proceedings, pp. 39–61 (2020)

12.

Applebaum, B., Lovett, S.: Algebraic attacks against random local functions and their countermeasures. SIAM J. Comput., 52–79 (2018)

13.

Maitra, S., Sarkar, P.: Maximum nonlinearity of symmetric boolean functions on odd number of variables. IEEE Trans. Inf. Theory 48, 2626–2630 (2002). https://doi.org/10.1109/TIT.2002.801482MathSciNetCrossRef

14.

Carlet, C.: On the degree, nonlinearity, algebraic thickness, and nonnormality of boolean functions, with developments on symmetric functions. IEEE Trans. Inf. Theory, 2178–2185 (2004)

15.

Canteaut, A., Videau, M.: Symmetric boolean functions. IEEE Trans. Inf. Theory, 2791–2811 (2005)

16.

An, B., Preneel, B.: On the algebraic immunity of symmetric boolean functions. In: Progress in cryptology - INDOCRYPT 2005, 6th International conference on cryptology in India, Bangalore, India, December 10-12, 2005, Proceedings, pp. 35–48 (2005)

17.

Qu, L., Feng, K., Liu, F., Wang, L.: Constructing symmetric boolean functions with maximum algebraic immunity. IEEE Trans. Inf. Theory, 2406–2412 (2009)

18.

Chen, Y., Lu, P.: Two classes of symmetric boolean functions with optimum algebraic immunity: Construction and analysis. IEEE Trans. Inf. Theory 57(4), 2522–2538 (2011). ISSN 1557-9654. https://doi.org/10.1109/TIT.2011.2111810MathSciNetCrossRef

19.

Gao, G., Guo, Y., Zhao, Y.: Recent results on balanced symmetric boolean functions. IEEE Trans. Inf. Theory 62(9), 5199–5203 (2016). ISSN 1557-9654. https://doi.org/10.1109/TIT.2015.2455052MathSciNetCrossRef

20.

Carlet, C., Méaux, P.: Boolean functions for homomorphic-friendly stream ciphers. In: Proceedings of the Conference on Algebra, Codes and Cryptology (A2C), pp 166–182. Springer, Cham (2019)

21.

Carlet, C., Méaux, P.: A complete study of two classes of boolean functions for homomorphic-friendly stream ciphers. IACR Cryptol. ePrint Arch. 2020, 1562 (2020)

22.

Tang, D., Luo, R., Du, X.: The exact fast algebraic immunity of two subclasses of the majority function. IEICE Trans., 2084–2088 (2016)

23.

Chen, Y., Guo, F., Zhang, L., Fast algebraic immunity of 2^m + 2 and 2^m + 3 variables majority function. Cryptol. ePrint Arch. Report 2019/286 (2019)

24.

Méaux, P.: On the fast algebraic immunity of majority functions. In: Schwabe, P., Thériault, N. (eds.) Progress in cryptology - LATINCRYPT, volume 11774 of LNCS, pp. 86–105. Springer (2019)

25.

Carlet, C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2020)CrossRef

26.

Dalai, D.K., Maitra, S., Sarkar, S.: Basic theory in construction of boolean functions with maximum possible annihilator immunity. Des. Codes Cryptogr. (2006)

27.

Qu, L., Li, C., Feng, K.: A note on symmetric boolean functions with maximum algebraic immunity in odd number of variables. IEEE Trans. Inf. Theory 53 (2007)

28.

Sarkar, P., Maitra, S.: Balancedness and correlation immunity of symmetric boolean functions. Discrete Math. :2351–2358. ISSN 0012-365X (2007)

29.

Linial, N., Rothschild, B.: Incidence matrices of subsets—a rank formula. SIAM J. Algebraic. Discrete Methods 2, 09 (1981)MathSciNetCrossRef

Titel: On the fast algebraic immunity of threshold functions
verfasst von: Pierrick Méaux
Publikationsdatum: 29.06.2021
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 5/2021
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-021-00505-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 5/2021

Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences

Quasi-cyclic constructions of asymmetric quantum error-correcting codes

Three-phase Z-complementary triads and almost complementary triads

Formal self duality

G-codes, self-dual G-codes and reversible G-codes over the ring

Several classes of minimal binary linear codes violating the Ashikhmin-Barg bound