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, ), the weak unpredictability assumption (Alamati et al. (2020) [1]) requires that, given random xi’s in X, no probabilistic polynomial time algorithm can compute, on input {(xi, gxi)}i=1,...,Q and y, the set element gy. 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
Representations of group actions and their applications in cryptography / D'Alconzo, Giuseppe; Di Scala, Antonio J.. - In: FINITE FIELDS AND THEIR APPLICATIONS. - ISSN 1071-5797. - 99:(2024), pp. 1-25. [10.1016/j.ffa.2024.102476]
Representations of group actions and their applications in cryptography
Giuseppe D'Alconzo;Antonio J. Di Scala
2024
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, ), the weak unpredictability assumption (Alamati et al. (2020) [1]) requires that, given random xi’s in X, no probabilistic polynomial time algorithm can compute, on input {(xi, gxi)}i=1,...,Q and y, the set element gy. 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 dimensionFile | Dimensione | Formato | |
---|---|---|---|
1-s2.0-S1071579724001151-main.pdf
accesso aperto
Descrizione: versione editoriale
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Creative commons
Dimensione
461.47 kB
Formato
Adobe PDF
|
461.47 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2991416