Comparing balanced ℤ_v-sequences obtained from ElGamal function to random balanced sequences

2021/12/22 by Panario, Daniel, Perin, Lucas Pandolfo, Stevens, Brett
#11B50 #11K45 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.3 #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2112.12032

Abstract

In this paper, we investigate the randomness properties of sequences in ℤ_v derived from permutations in ℤ_p^* using the remainder function modulo v, where p is a prime integer. Motivated by earlier studies with a cryptographic focus we compare sequences constructed from the ElGamal function x → g^x for x∈ℤ_>0 and g a primitive element of ℤ_p^*, to sequences constructed from random permutations of ℤ_p^*. We prove that sequences obtained from ElGamal have maximal period and behave similarly to random permutations with respect to the balance and run properties of Golomb's postulates for pseudo-random sequences. Additionally we show that they behave similarly to random permutations for the tuple balance property. This requires some significant work determining properties of random balanced periodic sequences. In general, for these properties and excepting for very unlikely events, the ElGamal sequences behave the same as random balanced sequences.

Related

• Sidon sets and statistics of the ElGamal function
• A Class of Random Sequences for Key Generation
• Random Sequences Based on the Divisor Pairs Function
• On Randomness of Goldbach Sequences
• Balance and pattern distribution of sequences derived from pseudorandom subsets of ℤ_q