Paper 2023/1247

Representations of Group Actions and their Applications in Cryptography

Giuseppe D'Alconzo, Polytechnic University of Turin
Antonio J. Di Scala, Polytechnic University of Turin
Abstract

Cryptographic group actions provide a flexible framework that allows the instantiation of several primitives, ranging from key exchange protocols to PRFs and digital signatures. The security of such constructions is based on the intractability of some computational problems. For example, given the group action $(G,X,\star)$, the weak unpredictability assumption (Alamati et al., Asiacrypt 2020) requires that, given random $x_i$'s in $X$, no probabilistic polynomial time algorithm can compute, on input $\{(x_i,g\star x_i)\}_{i=1,\dots,Q}$ and $y$, the set element $g\star y$. In this work, we study such assumptions, aided by the definition of group action representations and a new metric, the $q$-linear dimension, that estimates the "linearity'' of a group action, or in other words, how much it is far from being linear. We show that under some hypotheses on the group action representation, and if the $q$-linear dimension is polynomial in the security parameter, then the weak unpredictability and other related assumptions cannot hold. This technique is applied to some actions from cryptography, like the ones arising from the equivalence of linear codes, as a result, we obtain the impossibility of using such actions for the instantiation of certain primitives. As an additional result, some bounds on the $q$-linear dimension are given for classical groups, such as $\mathcal{S}_n$, $\mathrm{GL}(\mathbb{F}^n)$ and the cyclic group $\mathbb{Z}_n$ acting on itself.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Finite Fields and Their Applications
DOI
10.1016/j.ffa.2024.102476
Keywords
One-way group actionsweakly pseudorandomweakly unpredictablerepresentations
Contact author(s)
giuseppe dalconzo @ polito it
antonio discala @ polito it
History
2024-08-02: last of 3 revisions
2023-08-17: received
See all versions
Short URL
https://ia.cr/2023/1247
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1247,
      author = {Giuseppe D'Alconzo and Antonio J. Di Scala},
      title = {Representations of Group Actions and their Applications in Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1247},
      year = {2023},
      doi = {10.1016/j.ffa.2024.102476},
      url = {https://eprint.iacr.org/2023/1247}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.