In this paper we continue the development of a new technique for computing elimination ideals by substitution which has been called Z-separating re-embeddings. Given an ideal I in the polynomial ring <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$K[x_1,\dots ,x_n]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>K</mi> <mo stretchy="false">[</mo> <msub> <mi>x</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>x</mi> <mi>n</mi> </msub> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> over a field K, this method searches for tuples <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$Z=(z_1,\dots ,z_s)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Z</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>z</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>z</mi> <mi>s</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of indeterminates with the property that I contains polynomials of the form <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$f_i = z_i - h_i$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>f</mi> <mi>i</mi> </msub> <mo>=</mo> <msub> <mi>z</mi> <mi>i</mi> </msub> <mo>-</mo> <msub> <mi>h</mi> <mi>i</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$i=1,\dots ,s$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation> such that no term in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$h_i$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>h</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> is divisible by any indeterminate in Z. As there are frequently many candidate tuples Z, the task addressed by this paper is to efficiently check whether a given tuple Z has this property. We construct fast algorithms which check whether the vector space spanned by the generators of I or a somewhat enlarged vector space contains the desired polynomials <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$f_i$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>f</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation>. We also extend these algorithms to Boolean polynomials and apply them to cryptoanalyze round reduced versions of the AES cryptosystem more efficiently.

Efficient Checking of Separating Indeterminates

期刊论文
出版模式：

开放获取
发表日期：

2025年8月14日

查看全文

Bernhard Andraschko,
Martin Kreuzer,
Le Ngoc Long

摘要

In this paper we continue the development of a new technique for computing elimination ideals by substitution which has been called Z-separating re-embeddings. Given an ideal I in the polynomial ring $K[x_1,\dots ,x_n]$ $K [x_{1}, \dots, x_{n}]$ over a field K, this method searches for tuples $Z=(z_1,\dots ,z_s)$ $Z = (z_{1}, \dots, z_{s})$ of indeterminates with the property that I contains polynomials of the form $f_i = z_i - h_i$ $f_{i} = z_{i} - h_{i}$ for $i=1,\dots ,s$ $i = 1, \dots, s$ such that no term in $h_i$ $h_{i}$ is divisible by any indeterminate in Z. As there are frequently many candidate tuples Z, the task addressed by this paper is to efficiently check whether a given tuple Z has this property. We construct fast algorithms which check whether the vector space spanned by the generators of I or a somewhat enlarged vector space contains the desired polynomials $f_i$ $f_{i}$ . We also extend these algorithms to Boolean polynomials and apply them to cryptoanalyze round reduced versions of the AES cryptosystem more efficiently.