Mathematical Methods of Cryptography

On the one quasigroup based format preserving encryption algorithm

K. D. Tsaregorodtsev<sup>ab

a</sup> Lomonosov Moscow State University
^b АО «НПК "Криптонит"», г. Москва

Abstract: One of the possible approaches to the construction of “medium-sized” format preserving encryption (FPE) schemes is analyzed, which can be described as follows. Let us assume that there is a quasigroup $(M, \circ)$, where $M$ is a “medium-sized” set (i.e., $\lvert M \rvert = 2^{15}$ and above), and we want to construct a tweakable encryption scheme $E_k^{\tau} \colon M \to M$. Then with the help of $k$ and $\tau$ one can generate (using some pseudorandom function) a series of pseudorandom elements $k_i \in M$. To encrypt $m \in M$, one then applies a series of left shifts, i.e., $c \gets k_1 \circ \left( \ldots \left( k_{\ell} \circ m \right) \ldots \right) \in M$. The security of this method depends on the security of a pseudorandom function and the security of distinguishing a series of left shifts from the random permutation on $M$. We show that if one uses functional representation of a quasigroup operation using the proper families of discrete functions over the product of Abelian groups $H^n$, then left (right) shift, as well as its inverse, can be specified using proper families representation of an operation. A family of functions $F \colon M^n \to M^n$ is called proper iff for any $x, y \in M^n$ there exists $i$ such that $x_i \ne y_i$, but $F_i(x_1, \ldots, x_n) = F_i(y_1, \ldots, y_n)$. If $M = H^n$, where $(H, +)$ is a group, then one can define the following map: $\pi_F = \left( x_1 + F_1(x_1, \ldots, x_n), \ldots, x_n + F_n(x_1, \ldots, x_n) \right)$, which is a permutation in case of a proper family $F$. Then we can define a quasigroup operation $x \circ y = \pi_F(x) + \pi_G(y)$, where $F$ and $G$ are two proper families. The following theorem is proven: if $F$ is a proper family over $H^n$, then the family $\widetilde{F}(x) = (-x) + \pi^{-1}_F(x)$, where $\pi_F(x) = x + F(x)$, $x \in H^n$, is also proper. This theorem allows us to invert the $\circ$ operation using the functional representation: $x = \pi_{\widetilde{F}} \left( (x \circ y) - \pi_G(y) \right)$.

Keywords: FPE, quasigroup, proper family.

UDC: 512.548.7+004.056.55

DOI: 10.17223/2226308X/16/26