Randomness properties of $\mathbb{Z}_v$ ElGamal sequences

Abstract: In 2020 Boppré et al. investigated the randomness properties of the ElGamal function considered as a permutation $x \to g^x$ on $\mathbb{Z}_{p}^*$. They prove that the graph of this map is equidistributed and demonstrate experimentally that this map behaves like a random permutation with respect to the number of cycles and the number of $k$-cycles. These randomness properties imply that cryptographic systems based on ElGamal are resistant to certain attacks and they call for investigation of other randomness properties. We investigate the randomness properties of $\mathbb{Z}_v$ sequences derived from ElGamal. We prove that the period and number of occurrences of runs and tuples match sequences from random permutations closely. We describe extensive experiments which probe these similarities further.

combinatorics

Audience: researchers in the topic

( slides | video )

---

Carleton Combinatorics Meeting 2021

Series comments: See the external webpage for more details: people.math.carleton.ca/~dthomson/CCM2021

To contact, please use CCM2021@math.carleton.ca and prefix your subject with "[CCM2021-request]"

---