American Institute of Mathematical Sciences

doi: 10.3934/amc.2021029
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

On the number of factorizations of $t$ mod $N$ and the probability distribution of Diffie-Hellman secret keys for many users

 Institute of Cybernetics, Tallinn University of Technology, Estonia

Received  December 2020 Revised  June 2021 Early access August 2021

We study the number
 $R_n(t,N)$
of tuplets
 $(x_1,\ldots, x_n)$
of congruence classes modulo
 $N$
such that
 $\begin{equation*} x_1\cdots x_n \equiv t \pmod{N}. \end{equation*}$
As a result, we derive a recurrence for
 $R_n(t,N)$
and prove some multiplicative properties of
 $R_n(t,N)$
. Furthermore, we apply the result to study the probability distribution of Diffie-Hellman keys used in multiparty communication. We show that this probability distribution is not uniform.
Citation: Alar Leibak. On the number of factorizations of $t$ mod $N$ and the probability distribution of Diffie-Hellman secret keys for many users. Advances in Mathematics of Communications, doi: 10.3934/amc.2021029
References:
 [1] J. B. Friedlander, Uniform distribution, exponential sums, and cryptography, Equidistributions in Number Theory, An Introduction, Nato Science Series Ⅱ. Mathematics, Physics and Chemistry, Vol. 237, Springer, Dordrecht, 2007, 29–57. doi: 10.1007/978-1-4020-5404-4_3. [2] P. H. van der Kamp, On the Fourier transform of the greatest common divisor, INTEGERS, 13 (2013), 1-16. [3] D. Neuenschwander, Probabilistic and Statistical Methods in Cryptology: An Introduction by Selected Topics, Lecture Notes in Computer Science, Vol. 3028, Springer-Verlag, Berlin, 2004. doi: 10.1007/b97045. [4] R. W. K. Odoni, V. Varadharajan and P. W. Sanders, Public key distribution in matrix rings, Electronic Letters, 20 (1984), 386-387.  doi: 10.1049/el:19840267. [5] H. E. Rose, A Course in Number Theory, 2 edition, Oxford University Press, New York, 1994. [6] J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math., 6 (1962), 64-94. [7] I. Shparlinski, Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness, Progress in Computer Science and Applied Logic, 2003. doi: 10.1007/978-3-0348-8037-4. [8] C. P. Waldvogel and J. L. Massey, The probability distribution of the Diffie-Hellmann key, Advances in Cryptology-AUSCRYPT '92, Lecture Notes in Comp. Sci., Vol. 718, Springer, Berlin, 1993,492–504. doi: 10.1007/3-540-57220-1_87.

show all references

References:
 [1] J. B. Friedlander, Uniform distribution, exponential sums, and cryptography, Equidistributions in Number Theory, An Introduction, Nato Science Series Ⅱ. Mathematics, Physics and Chemistry, Vol. 237, Springer, Dordrecht, 2007, 29–57. doi: 10.1007/978-1-4020-5404-4_3. [2] P. H. van der Kamp, On the Fourier transform of the greatest common divisor, INTEGERS, 13 (2013), 1-16. [3] D. Neuenschwander, Probabilistic and Statistical Methods in Cryptology: An Introduction by Selected Topics, Lecture Notes in Computer Science, Vol. 3028, Springer-Verlag, Berlin, 2004. doi: 10.1007/b97045. [4] R. W. K. Odoni, V. Varadharajan and P. W. Sanders, Public key distribution in matrix rings, Electronic Letters, 20 (1984), 386-387.  doi: 10.1049/el:19840267. [5] H. E. Rose, A Course in Number Theory, 2 edition, Oxford University Press, New York, 1994. [6] J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math., 6 (1962), 64-94. [7] I. Shparlinski, Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness, Progress in Computer Science and Applied Logic, 2003. doi: 10.1007/978-3-0348-8037-4. [8] C. P. Waldvogel and J. L. Massey, The probability distribution of the Diffie-Hellmann key, Advances in Cryptology-AUSCRYPT '92, Lecture Notes in Comp. Sci., Vol. 718, Springer, Berlin, 1993,492–504. doi: 10.1007/3-540-57220-1_87.
 [1] Yvo Desmedt, Niels Duif, Henk van Tilborg, Huaxiong Wang. Bounds and constructions for key distribution schemes. Advances in Mathematics of Communications, 2009, 3 (3) : 273-293. doi: 10.3934/amc.2009.3.273 [2] Felix Fontein. Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures. Advances in Mathematics of Communications, 2008, 2 (3) : 293-307. doi: 10.3934/amc.2008.2.293 [3] Rainer Steinwandt, Adriana Suárez Corona. Attribute-based group key establishment. Advances in Mathematics of Communications, 2010, 4 (3) : 381-398. doi: 10.3934/amc.2010.4.381 [4] Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052 [5] Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022031 [6] Gerardo Vega, Jesús E. Cuén-Ramos. The weight distribution of families of reducible cyclic codes through the weight distribution of some irreducible cyclic codes. Advances in Mathematics of Communications, 2020, 14 (3) : 525-533. doi: 10.3934/amc.2020059 [7] Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002 [8] Lanqiang Li, Shixin Zhu, Li Liu. The weight distribution of a class of p-ary cyclic codes and their applications. Advances in Mathematics of Communications, 2019, 13 (1) : 137-156. doi: 10.3934/amc.2019008 [9] Kalikinkar Mandal, Guang Gong. On ideal $t$-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125 [10] Riccardo Aragona, Marco Calderini, Roberto Civino. Some group-theoretical results on Feistel Networks in a long-key scenario. Advances in Mathematics of Communications, 2020, 14 (4) : 727-743. doi: 10.3934/amc.2020093 [11] Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215 [12] R. V. Gurjar, Mariusz Koras and Peter Russell. Two dimensional quotients of $CC^n$ by a reductive group. Electronic Research Announcements, 2008, 15: 62-64. doi: 10.3934/era.2008.15.62 [13] Duanzhi Zhang. $P$-cyclic symmetric closed characteristics on compact convex $P$-cyclic symmetric hypersurface in R2n. Discrete and Continuous Dynamical Systems, 2013, 33 (2) : 947-964. doi: 10.3934/dcds.2013.33.947 [14] Xing Huang, Michael Röckner, Feng-Yu Wang. Nonlinear Fokker–Planck equations for probability measures on path space and path-distribution dependent SDEs. Discrete and Continuous Dynamical Systems, 2019, 39 (6) : 3017-3035. doi: 10.3934/dcds.2019125 [15] Yun Gao, Shilin Yang, Fang-Wei Fu. Some optimal cyclic $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2021, 15 (3) : 387-396. doi: 10.3934/amc.2020072 [16] Pankaj Kumar, Monika Sangwan, Suresh Kumar Arora. The weight distributions of some irreducible cyclic codes of length $p^n$ and $2p^n$. Advances in Mathematics of Communications, 2015, 9 (3) : 277-289. doi: 10.3934/amc.2015.9.277 [17] Anatole Katok, Federico Rodriguez Hertz. Rigidity of real-analytic actions of $SL(n,\Z)$ on $\T^n$: A case of realization of Zimmer program. Discrete and Continuous Dynamical Systems, 2010, 27 (2) : 609-615. doi: 10.3934/dcds.2010.27.609 [18] Raz Kupferman, Asaf Shachar. On strain measures and the geodesic distance to $SO_n$ in the general linear group. Journal of Geometric Mechanics, 2016, 8 (4) : 437-460. doi: 10.3934/jgm.2016015 [19] Anderson Silva, C. Polcino Milies. Cyclic codes of length $2p^n$ over finite chain rings. Advances in Mathematics of Communications, 2020, 14 (2) : 233-245. doi: 10.3934/amc.2020017 [20] Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the symmetry group of extended perfect binary codes of length $n+1$ and rank $n-\log(n+1)+2$. Advances in Mathematics of Communications, 2012, 6 (2) : 121-130. doi: 10.3934/amc.2012.6.121

2020 Impact Factor: 0.935