<p><Emphasis FontCategory="NonProportional">Anemoi</Emphasis> is a family of compression and hash functions over finite fields <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathbb {F}_q\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <mi>q</mi> </msub> </math></EquationSource> </InlineEquation> for efficient Zero-Knowledge applications. Its round function is based on a novel permutation <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq2.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="90" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {H}: \mathbb {F}_q^2 \rightarrow \mathbb {F}_q^2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">H</mi> <mo>:</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>q</mi> <mn>2</mn> </msubsup> <mo stretchy="false">→</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>q</mi> <mn>2</mn> </msubsup> </mrow> </math></EquationSource> </InlineEquation>, called the open <Emphasis FontCategory="NonProportional">Flystel</Emphasis>, which is parametrized by a permutation <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="88" /> </InlineMediaObject> <EquationSource Format="TEX">\(E: \mathbb {F}_q \rightarrow \mathbb {F}_q\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mo>:</mo> <msub> <mi mathvariant="double-struck">F</mi> <mi>q</mi> </msub> <mo stretchy="false">→</mo> <msub> <mi mathvariant="double-struck">F</mi> <mi>q</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> and two functions <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="123" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_\gamma , Q_\delta : \mathbb {F}_q \rightarrow \mathbb {F}_q\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>Q</mi> <mi>γ</mi> </msub> <mo>,</mo> <msub> <mi>Q</mi> <mi>δ</mi> </msub> <mo>:</mo> <msub> <mi mathvariant="double-struck">F</mi> <mi>q</mi> </msub> <mo stretchy="false">→</mo> <msub> <mi mathvariant="double-struck">F</mi> <mi>q</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. Over a prime field <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathbb {F}_p\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <mi>p</mi> </msub> </math></EquationSource> </InlineEquation> with <i>E</i> a power permutation and <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_\gamma \)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>γ</mi> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq7.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_\delta \)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>δ</mi> </msub> </math></EquationSource> </InlineEquation> quadratic functions with identical leading coefficient, the <Emphasis FontCategory="NonProportional">Anemoi</Emphasis> designers conjectured for the absolute value of the Walsh transform that <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq8.gif" Format="GIF" Height="24" Rendition="HTML" Resolution="72" Type="Linedraw" Width="307" /> </InlineMediaObject> <EquationSource Format="TEX">\(\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) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mo movablelimits="true">max</mo> <mrow> <mi mathvariant="bold">a</mi> <mo>∈</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mn>2</mn> </msubsup> <mo>,</mo> <mspace width="4pt" /> <mi mathvariant="bold">b</mi> <mo>∈</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mn>2</mn> </msubsup> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <mrow> <mo stretchy="false">{</mo> <mn mathvariant="bold">0</mn> <mo stretchy="false">}</mo> </mrow> </mrow> </msub> <mfenced close="|" open="|"> <msub> <mi mathvariant="script">W</mi> <mi mathvariant="script">H</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ψ</mi> <mo>,</mo> <mi mathvariant="bold">a</mi> <mo>,</mo> <mi mathvariant="bold">b</mi> <mo stretchy="false">)</mo> </mrow> </mfenced> <mo>≤</mo> <mi>p</mi> <mo>·</mo> <mo>log</mo> <mfenced close=")" open="("> <mi>p</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. By exploiting that the open <Emphasis FontCategory="NonProportional">Flystel</Emphasis> is CCZ-equivalent to the closed <Emphasis FontCategory="NonProportional">Flystel</Emphasis>, we prove in this note that <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq9.gif" Format="GIF" Height="24" Rendition="HTML" Resolution="72" Type="Linedraw" Width="315" /> </InlineMediaObject> <EquationSource Format="TEX">\(\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\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mo movablelimits="true">max</mo> <mrow> <mi mathvariant="bold">a</mi> <mo>∈</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mn>2</mn> </msubsup> <mo>,</mo> <mspace width="4pt" /> <mi mathvariant="bold">b</mi> <mo>∈</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mn>2</mn> </msubsup> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <mrow> <mo stretchy="false">{</mo> <mn mathvariant="bold">0</mn> <mo stretchy="false">}</mo> </mrow> </mrow> </msub> <mfenced close="|" open="|"> <msub> <mi mathvariant="script">W</mi> <mi mathvariant="script">H</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ψ</mi> <mo>,</mo> <mi mathvariant="bold">a</mi> <mo>,</mo> <mi mathvariant="bold">b</mi> <mo stretchy="false">)</mo> </mrow> </mfenced> <mo>≤</mo> <mrow> <mo stretchy="false">(</mo> <mi>d</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>·</mo> <mi>p</mi> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1589_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="85" /> </InlineMediaObject> <EquationSource Format="TEX">\(d = \deg \left( E \right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>=</mo> <mo>deg</mo> <mfenced close=")" open="("> <mi>E</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A note on the Walsh spectrum of the Flystel

  • Matthias Johann Steiner

摘要

Anemoi is a family of compression and hash functions over finite fields \(\mathbb {F}_q\) F q 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\) H : F q 2 F q 2 , called the open Flystel, which is parametrized by a permutation \(E: \mathbb {F}_q \rightarrow \mathbb {F}_q\) E : F q F q and two functions \(Q_\gamma , Q_\delta : \mathbb {F}_q \rightarrow \mathbb {F}_q\) Q γ , Q δ : F q F q . Over a prime field \(\mathbb {F}_p\) F p with E a power permutation and \(Q_\gamma \) Q γ , \(Q_\delta \) Q δ quadratic functions with identical leading coefficient, the Anemoi 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) \) max a F p 2 , b F p 2 \ { 0 } W H ( ψ , a , b ) p · log p . By exploiting that the open Flystel is CCZ-equivalent to the closed Flystel, 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\) max a F p 2 , b F p 2 \ { 0 } W H ( ψ , a , b ) ( d - 1 ) · p , where \(d = \deg \left( E \right) \) d = deg E .