<p>Achieving (at least) a worst-case correctness error is essential for an underlying public-key encryption (PKE) scheme to which the Fujisaki-Okamoto (FO) transformation is applied. There are three average-case to worst-case (ACWC) transformations—denoted as <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\textsf{ACWC}_{0}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="sans-serif">ACWC</mi> <mn>0</mn> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\textsf{ACWC}_{1}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="sans-serif">ACWC</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> (PKC 2023), and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\textsf{ACWC}_{2}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="sans-serif">ACWC</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> (TIFS 2023)-which generically convert a PKE scheme with an average-case correctness error into one with a worst-case correctness error. However, in these ACWC transformations the <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>γ</mi> </math></EquationSource> </InlineEquation>-<i>spreadness</i>, a critical factor in determining explicit rejection (<InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\textsf{FO}^{\perp }$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi mathvariant="sans-serif">FO</mi> <mo>⊥</mo> </msup> </math></EquationSource> </InlineEquation>) or implicit rejection (<InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\textsf{FO}^{\not \perp }$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi mathvariant="sans-serif">FO</mi> <mo>⊥̸</mo> </msup> </math></EquationSource> </InlineEquation>), has not been established with rigorous proofs. Existing analyses of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>γ</mi> </math></EquationSource> </InlineEquation>-spreadness lack rigorous proofs, include analytical flaws, or fail to achieve the tightest possible bounds. In this work, we reprove the <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>γ</mi> </math></EquationSource> </InlineEquation>-spreadness of ACWC-transformed PKE schemes by leveraging two key facts: the random oracle is chosen at random and the encoding mechanism used in the ACWC framework is message-hiding. Our new proofs are applied to the previous NTRU-based PKE schemes, called <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\textsf{NTRU}\text {-}\textsf{C}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">NTRU</mi> <mtext>-</mtext> <mi mathvariant="sans-serif">C</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\textsf{NTRU}\text {-}\textsf{B}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">NTRU</mi> <mtext>-</mtext> <mi mathvariant="sans-serif">B</mi> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$\mathsf {NTRU+}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">NTRU</mi> <mo>+</mo> </mrow> </math></EquationSource> </InlineEquation>, giving the corrected <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$\gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>γ</mi> </math></EquationSource> </InlineEquation>-spreadness for those PKE schemes with concrete parameters.</p>

On the $\gamma $-spreadness of average-case to worst-case transformations

期刊论文
发表日期：

2026年6月3日

查看全文

Hyun Ji Kwag,
Jonghyun Kim,
Changmin Lee,
Jong Hwan Park

摘要

Achieving (at least) a worst-case correctness error is essential for an underlying public-key encryption (PKE) scheme to which the Fujisaki-Okamoto (FO) transformation is applied. There are three average-case to worst-case (ACWC) transformations—denoted as $\textsf{ACWC}_{0}$ ${ACWC}_{0}$ , $\textsf{ACWC}_{1}$ ${ACWC}_{1}$ (PKC 2023), and $\textsf{ACWC}_{2}$ ${ACWC}_{2}$ (TIFS 2023)-which generically convert a PKE scheme with an average-case correctness error into one with a worst-case correctness error. However, in these ACWC transformations the $\gamma $ $γ$ -spreadness, a critical factor in determining explicit rejection ( $\textsf{FO}^{\perp }$ ${FO}^{⊥}$ ) or implicit rejection ( $\textsf{FO}^{\not \perp }$ ${FO}^{⊥̸}$ ), has not been established with rigorous proofs. Existing analyses of $\gamma $ $γ$ -spreadness lack rigorous proofs, include analytical flaws, or fail to achieve the tightest possible bounds. In this work, we reprove the $\gamma $ $γ$ -spreadness of ACWC-transformed PKE schemes by leveraging two key facts: the random oracle is chosen at random and the encoding mechanism used in the ACWC framework is message-hiding. Our new proofs are applied to the previous NTRU-based PKE schemes, called $\textsf{NTRU}\text {-}\textsf{C}$ $NTRU - C$ , $\textsf{NTRU}\text {-}\textsf{B}$ $NTRU - B$ , and $\mathsf {NTRU+}$ $NTRU +$ , giving the corrected $\gamma $ $γ$ -spreadness for those PKE schemes with concrete parameters.

On the \(\gamma \)-spreadness of average-case to worst-case transformations

摘要