×

On algebraic immunity of trace inverse functions on finite fields of characteristic two. (English) Zbl 1425.94058

Summary: The trace inverse functions \(\operatorname{Tr}(\lambda x^{-1})\) over the finite field \(\mathbb{F}_{2^n}\) are a class of very important Boolean functions and are used in many stream ciphers such as SFINKS, RAKAPOSHI, the simple counter stream cipher (SCSC) presented by W. Si and C. Ding [Cryptogr. Commun. 4, No. 2, 79–104 (2012; Zbl 1282.94065)], etc. In order to evaluate the security of those ciphers in resistance to (fast) algebraic attacks, the authors need to characterize algebraic properties of \(\operatorname{Tr}(\lambda x^{-1})\). However, currently only some bounds on algebraic immunity of \(\operatorname{Tr}(\lambda x^{-1})\) are given in the public literature, for example, the NGG upper bound and the Bayev lower bound, etc. This paper gives the exact value of the algebraic immunity of \(\operatorname{Tr}(\lambda x^{-1})\) over \({F_{{2^n}}}\), that is, \(\operatorname{AI}(\operatorname{Tr}(\lambda x^{-1}))=\lceil 2\sqrt{n}\rceil - 2\), where \(n\geq 2\), \(\lambda\in\mathbb{F}_{2^n}\) and \(\lambda\neq 0\), which shows that Dalai’s conjecture on the algebraic immunity of \(\operatorname{Tr}(\lambda x^{-1})\) is correct. What is more, the authors demonstrate some weak properties of \(\operatorname{Tr}(\lambda x^{-1})\) against fast algebraic attacks.

MSC:

94A60 Cryptography
06E30 Boolean functions

Citations:

Zbl 1282.94065

Software:

SNOW; JBool; RAKAPOSHI
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Crama Y and Hammer P L, Boolean Functions: Theory, Algorithms and Applications, Cambridge University Press, New York, 2011. · Zbl 1237.06001 · doi:10.1017/CBO9780511852008
[2] Ruepple R A, Analysis and Design of Stream Ciphers (Communications and Control Engineering Series), Springer, Berlin, 1986. · doi:10.1007/978-3-642-82865-2
[3] National Bureau of Standars, Data encryption standard, FIPS publication, No. 46, U. S. Department of Commerce, 1977.
[4] Daemen J and Rijmen V, The Design of Rijndael, Springer, Berlin, 2002. · Zbl 1065.94005 · doi:10.1007/978-3-662-04722-4
[5] Cusick T W and Stănică P, Cryptographic Boolean Functions and Applications, Access Online via Elsevier, 2009.
[6] Nyberg, K., Differentially uniform mappings for cryptography, 55-64 (1994) · Zbl 0951.94510
[7] Ekdahl, P.; Johansson, T., A new version of the stream cipher SNOW, 47-61 (2003) · Zbl 1027.68596
[8] ETSI/SAGE, Specification of the 3GPP confidentiality and integrity algorithms UEA2 & UIA2, Document 2: SNOW 3G Specification, v1.1, 2006.
[9] ETSI/SAGE, Specification of the 3GPP confidentiality and integrity algorithms 128-EEA3 & 128-EIA3, Document 2: ZUC Specification, v1.6, 2011.
[10] Golomb S W and Gong G, Signal Design for Good Correlation: For Wireless Communication, Cryptography and Radar, Cambridge University Press, New York, 2005. · Zbl 1097.94015 · doi:10.1017/CBO9780511546907
[11] Si W and Ding C, A simple stream cipher with proven properties, Cryptography and Communications, 2012, 4(2): 79-104. · Zbl 1282.94065 · doi:10.1007/s12095-011-0059-x
[12] Braeken A, Lano J, Mentens N, et al., SFINK: A synchronous stream cipher for restricted hardware environments, The eStream project, available at http:www.ecrypt.eu.org/stream.
[13] Cid, C.; Kiyomoto, S.; Kurihara, J., The rakaposhi stream cipher, ICICS 2009, 32-46 (2009)
[14] Courtois, N.; Meier, W., Algebraic attacks on stream ciphers with linear feedback, EUROCRYPT 2003, 346-359 (2003) · Zbl 1038.94525
[15] Courtois, N., Fast algebraic attacks on stream ciphers with linear feedback, 176-194 (2003) · Zbl 1122.94365
[16] Courtois, N.; Pieprzyk, J., Cryptanalysis of block ciphers with overdefined systems of equations, ASIACRYPT 2002, 267-287 (2002) · Zbl 1065.94543
[17] Armknecht, F., Algebraic attacks on combiners with memory, CRYPTO 2003, 162-176 (2003) · Zbl 1122.94346
[18] Courtois, N., Algebraic attacks on combiners with memory and several outputs, ICISC 2004, 3-20 (2004)
[19] Dalai, D.; Gupta, K.; Maitra, S., Results on algebraic immunity for cryptographically significant boolean function, INDOCRYPT 2004, 92-106 (2004) · Zbl 1115.94007
[20] Carlet, C.; Feng, K., An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, ASIACRYPT 2008, 425-440 (2008) · Zbl 1206.94060
[21] Tu Z and Deng Y, A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity, Design, Codes and Cryptography, 2011, 60(1): 1-14. · Zbl 1226.94013 · doi:10.1007/s10623-010-9413-9
[22] Liu, M.; Zhang, Y.; Lin, D., Perfect algebraic immune functions, ASIACRYPT 2012, 172-189 (2012) · Zbl 1292.94104
[23] Tang D, Carlet C, and Tang X, Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks, IEEE Trans. Inf. Theory, 2013, 59(1): 653-664. · Zbl 1364.94808 · doi:10.1109/TIT.2012.2217476
[24] Wang Q, Peng J, Kan H, et al., Constructions of cryptographically significant Boolean functions using primitive polynomials, IEEE Trans. Inf. Theory, 2010, 56(6): 3048-3053. · Zbl 1366.94541 · doi:10.1109/TIT.2010.2046195
[25] Zeng X, Carlet C, Shan J, and Hu L, More balanced Boolean functions with optimal algebraic immunity, and good nonlinearity and resistance to fast algebraic attacks, IEEE Trans. Inf. Theory, 2011, 57(9): 6310-6320. · Zbl 1365.94686 · doi:10.1109/TIT.2011.2109935
[26] Nawaz, Y.; Gong, G.; Gupta, K. C., Upper bounds on algebraic immunity of Boolean power functions, FSE 2006, 375-389 (2006) · Zbl 1234.94061
[27] Bayev V V, Some lower bounds on the algebraic immunity of functions given by their trace forms, Problems of Information Transmission, 2008, 44(3): 243-265. · Zbl 1171.94338 · doi:10.1134/S0032946008030071
[28] Dalai D K, Computing the rank of incidence matrix and algebraic immunity of Boolean functions, Available at http://eprint.iacr.org/2013/273.pdf. · Zbl 1401.94145
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.