A note on the Walsh spectrum of the Flystel

Abstract is a family of compression and hash functions over finite fields $$\mathbb {F}_q$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:math> for efficient Zero-Knowledge applications. Its round function is based on a novel permutation $$\mathcal {H}: \mathbb {F}_q^2 \rightarrow \mathbb {F}_q^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo>:</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>→</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> </mml:mrow> </mml:math> , called the open , which is parametrized by a permutation $$E: \mathbb {F}_q \rightarrow \mathbb {F}_q$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>E</mml:mi> <mml:mo>:</mml:mo> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> <mml:mo>→</mml:mo> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:mrow> </mml:math> and two functions $$Q_\gamma , Q_\delta : \mathbb {F}_q \rightarrow \mathbb {F}_q$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>γ</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>δ</mml:mi> </mml:msub> <mml:mo>:</mml:mo> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> <mml:mo>→</mml:mo> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:mrow> </mml:math> . Over a prime field $$\mathbb {F}_p$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> </mml:msub> </mml:math> with E a power permutation and $$Q_\gamma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>γ</mml:mi> </mml:msub> </mml:math> , $$Q_\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>δ</mml:mi> </mml:msub> </mml:math> quadratic functions with identical leading coefficient, the designers conjectured for the absolute value of the Walsh transform that $$\max _{\textbf{a} \in \mathbb {F}_p^2,\ \textbf{b} \in \mathbb {F}_p^2 {\setminus } \{ \textbf{0} \}} \left| \mathcal {W}_\mathcal {H} (\psi , \textbf{a}, \textbf{b}) \right| \le p \cdot \log \left( p \right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mo>max</mml:mo> <mml:mrow> <mml:mi>a</mml:mi> <mml:mo>∈</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>,</mml:mo> <mml:mspace/> <mml:mi>b</mml:mi> <mml:mo>∈</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>\</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:mrow> </mml:msub> <mml:mfenced> <mml:msub> <mml:mi>W</mml:mi> <mml:mi>H</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ψ</mml:mi> <mml:mo>,</mml:mo> <mml:mi>a</mml:mi> <mml:mo>,</mml:mo> <mml:mi>b</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mfenced> <mml:mo>≤</mml:mo> <mml:mi>p</mml:mi> <mml:mo>·</mml:mo> <mml:mo>log</mml:mo> <mml:mfenced> <mml:mi>p</mml:mi> </mml:mfenced> </mml:mrow> </mml:math> . By exploiting that the open is CCZ-equivalent to the closed , we prove in this note that $$\max _{\textbf{a} \in \mathbb {F}_p^2,\ \textbf{b} \in \mathbb {F}_p^2 {\setminus } \{ \textbf{0} \}} \left| \mathcal {W}_\mathcal {H} (\psi , \textbf{a}, \textbf{b}) \right| \le (d - 1) \cdot p$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mo>max</mml:mo> <mml:mrow> <mml:mi>a</mml:mi> <mml:mo>∈</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>,</mml:mo> <mml:mspace/> <mml:mi>b</mml:mi> <mml:mo>∈</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>\</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:mrow> </mml:msub> <mml:mfenced> <mml:msub> <mml:mi>W</mml:mi> <mml:mi>H</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ψ</mml:mi> <mml:mo>,</mml:mo> <mml:mi>a</mml:mi> <mml:mo>,</mml:mo> <mml:mi>b</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mfenced> <mml:mo>≤</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow>