A note on a conjecture concerning symmetric resilient functions (Q5894752): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Privacy Amplification by Public Discussion / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4230354 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Analysis and design of stream ciphers / rank | |||
Normal rank |
Latest revision as of 10:42, 22 May 2024
scientific article; zbMATH DE number 446245
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on a conjecture concerning symmetric resilient functions |
scientific article; zbMATH DE number 446245 |
Statements
A note on a conjecture concerning symmetric resilient functions (English)
0 references
15 November 1993
0 references
Let \(n\geq m\geq 1\) be integers, \(f: \{0,1\}^ n\to \{0,1\}^ m\), and \(t\leq n\). A function \(f\) is said to be \((n,m,t)\)-resilient if for every \(t\)-subset \(\{i_ 1,\dots,i_ t\}\subset \{1,\dots,n\}\), for every choice of \(z_ j\in\{0,1\}\), \(1\leq j\leq t\), and for every \((y_ 1,\dots,y_ m)\in \{0,1\}^ m\) the number \[ \bigl|\bigl\{(x_ 1,\dots,x_ n):\;f(x_ 1,\dots,x_ n)=(y_ 1,\dots,y_ m),\;x_ j=z_ j,\;1\leq j\leq t\bigr\}\bigr| \] is equal to \(2^{n-m}\). A function \(f\) is called symmetric if for every permutation \(p\) on \(\{1,\dots,n\}\) we have \(f(x_ 1,\dots,x_ n)= f(x_{p(1)},\dots,x_{p(n)})\). So, for any symmetric Boolean function \(f\) (\(m=1\)) exists a function \(g: \{0,1,\dots,n\}\to \{0,1\}\) such that \(f(x_ 1,\dots,x_ n)= g(w(x_ 1,\dots,x_ n))\), where \(w(x_ 1,\dots,x_ n)\) is the Hamming weight of the \(n\)-tuple \((x_ 1,\dots,x_ n)\). In 1985 B. Chor et al. conjectured that the only \((n,1,1)\)-resilient symmetric Boolean functions are the exclusive-or of all \(n\) variables and its negation. In the present note the authors disprove the above conjecture by the following elegant construction: let \(r>2\) be an even number, \(n=r^ 2-2\), \(k=(r-2)(r+1)/2\), define a function \(h: \{0,1,\dots,n\}\to \{0,1\}\) as follows (for \(i\not\in \{k,k+1,n-k,n-k+1\}\)) \(h(i)=0\) if \(i\) is even and \(h(i)=1\) if \(i\) is odd; if \(i\in\{k,k+1,n-k,n-k+1\}\), then let \(h(i)=0\) if \(i\) is odd and \(h(i)=1\) if \(i\) is even. Theorem. The symmetric Boolean function \(f(x_ 1,\dots,x_ n)=h(w(x))\) is an \((n,1,2)\)-resilient function.
0 references
symmetric resilient functions
0 references
Boolean function
0 references