On the one quasigroup based format preserving encryption algorithm

K. D. Tsaregorodtsev

Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 102-104.

Résumé

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)$.

Détail

Mots-clés : FPE, quasigroup
Keywords: proper family.

Bibliographie

[1] Bellare M., Ristenpart T., Rogaway P., and Stegers T., “Format-preserving encryption”, LNCS, 5867, 2009, 295–312 | Zbl

[2] Lee J.-K., Koo B., Roh D., et al., “Format-preserving encryption algorithms using families of tweakable blockciphers”, LNCS, 8949, 2014, 132–159 | MR

[3] Dworkin M., Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption, NIST Special Publication 800-38G, 2016 | Zbl

[4] Hoang V. T., Tessaro S., and Trieu N., “The curse of small domains: New attacks on format-preserving encryption”, LNCS, 10991, 2018, 221–251 | MR | Zbl

[5] Amon O., Dunkelman O., Keller N., et al., “Three third generation attacks on the format preserving encryption scheme FF3”, LNCS, 12697, 2021, 127–154 | MR | Zbl

[6] Markov V. T., Mikhalev A. B., Nechaev A. A., “Neassotsiativnye algebraicheskie struktury v kriptografii i kodirovanii”, Fundament. i prikl. matem., 21:4 (2016), 99–124

[7] Markovski S. and Bakeva V., “Quasigroup string processing: Part 4”, Contributions. Sec. Natural Math. Biotechn. Sci., 27:1–2 (2006) http://csnmbs.manu.edu.mk/index.php/csnmbs/article/view/5

[8] Shcherbacov V., Elements of Quasigroup Theory and Applications, Chapman and Hall/CRC, N.Y., 2017, 598 pp. | MR

[9] Artamonov V. A., “Kvazigruppy i ikh prilozheniya”, Chebyshevskii sbornik, 19:2 (2018), 111–122 | DOI | MR | Zbl

[10] Gligoroski D., Ødegărd R. S., Mihova M., et al., “Cryptographic hash function Edon-R'.”, Proc. 1st Intern. Workshop on Security and Communication Networks (Trondheim, Norway, 2009), 1–9

[11] Tsaregorodtsev K., “Format-preserving encryption: a survey”, Matematicheskie voprosy kriptografii, 13:2 (2022), 133–153 | DOI | MR | Zbl

[12] Yashunskii A. D., “O skorosti skhodimosti kvazigruppovykh svertok veroyatnostnykh raspredelenii”, Diskretnaya matematika, 34:3 (2022), 160–171 | DOI

[13] Liskov M., Rivest R., and Wagner D., “Tweakable block ciphers”, J. Cryptology, 24:3 (2011), 588–613 | DOI | MR | Zbl

[14] Nosov V. A., Pankratev A. E., “O funktsionalnom zadanii latinskikh kvadratov”, Intellektualnye sistemy. Teoriya i prilozheniya, 12:1–4 (2008), 317–332 | MR