Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika. Supplement, 2022, Issue 15, Pages 67–70
DOI: https://doi.org/10.17223/2226308X/15/17
(Mi pdma582)
 

Mathematical Methods of Cryptography

The additive differential probability of $k$ successive exclusive-OR

I. A. Sutorminab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University
References:
Abstract: We study the additive differential probability of a composition of bitwise XOR — $\mathrm{adp}^{\oplus}_k$. For a set of vectors $\alpha^1 \ldots \alpha^{k + 1} \in \mathbb{Z}_2^{n}$, it is defined as
$$ \textstyle\mathrm{adp}^{\oplus}_k(\alpha^{1}, \ldots, \alpha^{k} \to \alpha^{k + 1}) = \dfrac{1}{2^{kn}} \big|\lbrace x^1, \ldots, x^{k}\in \mathbb{Z}_{2}^{n} : {\bigoplus\limits_{i = 1}^{k}(x^i \boxplus \alpha^i)} = \alpha^{k + 1} \boxplus \bigoplus\limits_{i = 1}^{k} x^i \rbrace\big|.$$
It is used when analyzing symmetric key primitives, such as Addition-Rotation-XOR constructions. It is proven that: 1) $\mathrm{adp}^{\oplus}_k$ is a symmetric function; 2) the value of $\mathrm{adp}^{\oplus}_k$ does not change if $2^{n - 1}$ is added to any two arguments; 3) the value of $\mathrm{adp}^{\oplus}_k$ does not change if any two arguments are replaced by the opposite element of $\mathbb{Z}_{2}^{n}$, and if $k$ is even, then the value of $\mathrm{adp}^{ \oplus}_k$ does not change if any argument is replaced. Recurrence formulas are obtained allowing to calculate the value $\mathrm{adp}^{\oplus}_k$ for arguments of dimension $n + 1$ using the set of values $\mathrm{adp}^{\oplus}_k$ for arguments of dimension $n$. Using recurrent formulas we prove that $\mathrm{adp}^{\oplus}_k$ is equal to zero if and only if there exists a position $i$ such that $(\alpha^1_i, \ldots, \alpha^{ k + 1}_i) \neq (0, \ldots, 0)$; $(\alpha^1_j, \ldots, \alpha^{k + 1}_j ) = (0, \ldots, 0)$ for any $j$, $n \geq j > i$, and either Hamming weight of the vector $(\alpha^1_i, \ldots, \alpha^{k + 1}_i)$ is odd, or $k$ is odd, $i > 1$, vector $(\alpha^1_i, \ldots, \alpha^{k + 1}_i)$ is equal to the $(1, \ldots, 1)$ and Hamming weight of the vector $(\alpha^1_{i - 1}, \ldots, \alpha^{k + 1}_{i - 1})$ is odd. In the case of even $k$, it is proved that $\mathrm{adp}^{\oplus}_k(0, \ldots, 0, \gamma \to \gamma)$ is maximal when the last argument is fixed. In the case of odd $k$, it is conjectured that $\mathrm{adp}^{\oplus}_k(\gamma, \ldots, \gamma \to \gamma)$ is maximum when the last argument is fixed.
Keywords: differential cryptanalysis, ARX, XOR, modular addition.
Funding agency Grant number
Ministry of Science and Higher Education of the Russian Federation 075-15-2022-281
Document Type: Article
UDC: 519.7
Language: Russian
Citation: I. A. Sutormin, “The additive differential probability of $k$ successive exclusive-OR”, Prikl. Diskr. Mat. Suppl., 2022, no. 15, 67–70
Citation in format AMSBIB
\Bibitem{Sut22}
\by I.~A.~Sutormin
\paper The additive differential probability of $k$ successive exclusive-OR
\jour Prikl. Diskr. Mat. Suppl.
\yr 2022
\issue 15
\pages 67--70
\mathnet{http://mi.mathnet.ru/pdma582}
\crossref{https://doi.org/10.17223/2226308X/15/17}
Linking options:
  • https://www.mathnet.ru/eng/pdma582
  • https://www.mathnet.ru/eng/pdma/y2022/i15/p67
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Prikladnaya Diskretnaya Matematika. Supplement
    Statistics & downloads:
    Abstract page:80
    Full-text PDF :22
    References:19
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024