Characterization of linear structures

DOI10.1023/A:1008399109102MaRDI QIDQ1841525zbMATH OpenOpenAlexFDO

Authors Sylvie Dubuc

Publication date 18 February 2001

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1008399109102

zbMATH Keywords

Boolean functionFourier transformlinear structurevectorial function

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60)

Review text

Let \(F\) be a function defined from \(F_2^m\) to \(F_2^n\) and \((\alpha,a)\) be an element of \(F_2^m\times F_2^n\), with \(\alpha\neq 0\). Then \((\alpha,a)\) is defined to be a linear structure of \(F\) if \(F(x)= F(x+\alpha)+ a\) for all \(x\in F_2^m\). In this paper the existence of linear structures for \(F\) is characterized using the Fourier transform of the function. In particular the case of Boolean functions, i.e. where \(n=1\) is carefully studied. For cryptographic applications Boolean functions without linear structures are desirable. Two constructions of resilient (i.e., correlation-immune and balanced) Boolean functions which have no linear structure are presented.

Recommendations

• scientific article; zbMATH DE number 1076147
• scientific article; zbMATH DE number 1455092
• Algebraic nonlinearity and its applications to cryptography
• On the linear structures of balanced functions and quadratic APN functions
• scientific article; zbMATH DE number 6001305

Cited in

(20)

• Improved BV-based quantum attack on block ciphers
• The \textit{crooked} property
• Polynomial-time quantum algorithms for finding the linear structures of Boolean function
• Using Bernstein-Vazirani algorithm to attack block ciphers
• A quantum related-key attack based on the Bernstein-Vazirani algorithm
• Quantum key-recovery attack on Feistel constructions: Bernstein-Vazirani meet Grover algorithm
• scientific article; zbMATH DE number 3851283 (Why is no real title available?)
• On a Class of Permutation Polynomials over $\mathbb{F}_{2^n}$
• scientific article; zbMATH DE number 40988 (Why is no real title available?)
• scientific article; zbMATH DE number 1076147 (Why is no real title available?)
• scientific article; zbMATH DE number 1455092 (Why is no real title available?)
• A quantum algorithm to approximate the linear structures of Boolean functions
• On the conjecture about the linear structures of rotation symmetric Boolean functions
• On derivatives of polynomials over finite fields through integration
• Maximal complete permutations over \(\mathbb{F}_2^n \)
• Some remarks on the TKIP key mixing function of IEEE 802.11i
• When does \(G(x)+\gamma \, \text{Tr}(H(x))\) permute \(\mathbb F_{p^n}\)?
• Quantum algorithm for finding impossible differentials and zero-correlation linear hulls of symmetric ciphers
• The linear structures and fast points of rotation symmetric Boolean functions
• Zero-correlation linear analysis for block ciphers based on the Bernstein-Vazirani and Grover algorithms

This page was built for publication: Characterization of linear structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1841525)