TY - JOUR
T1 - A tradeoff paradigm shift in cryptographically-secure pseudorandom number generation based on discrete logarithm
AU - Koshiba, Takeshi
AU - Zolfaghari, Behrouz
AU - Bibak, Khodakhast
N1 - Funding Information:
TK is supported in part by a JSPS Grant-in-Aids for Scientific Research (A) No. 21H04879 , and for Challenging Exploratory Research No. 19K22849 and MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) Grant No. JPMXS0118067285 and JPMXS0120319794 .
Publisher Copyright:
© 2023 Elsevier Ltd
PY - 2023/3
Y1 - 2023/3
N2 - Discrete logarithmic pseudorandom number generators are a prevailing class of cryptographically-secure pseudorandom number generators (CSPRNGs). In generators of this type, the security parameter affects both security and performance. This adds to the design complexity via creating a critical tradeoff between security and performance. This research is an attempt at shifting the security-performance tradeoff paradigm in this realm. To this end, we propose a modification to Gennaro's pseudorandom number generator via replacing word-wise arithmetic operations with bit-wise logical operations in trapdoor and hard-core functions. The security of our generator (like that of Gennaro's) is based on the hardness of a special variant of the discrete logarithm problem. We establish an equivalence between the specific variant of the discrete logarithm problem with the standard problem. Moreover, we demonstrate that in the modified generator, performance will be almost independent of the security parameter as logical operations can be performed in register level without the interference of the Arithmetic-Logic Unit (ALU). This relaxes the security-performance tradeoff and allows designers to maneuver more flexibly in the tradeoff space. We implement and evaluate our proposed generator and prove its security. Our CSPRNG is deemed random by all randomness tests in NIST SP 800-22 suite.
AB - Discrete logarithmic pseudorandom number generators are a prevailing class of cryptographically-secure pseudorandom number generators (CSPRNGs). In generators of this type, the security parameter affects both security and performance. This adds to the design complexity via creating a critical tradeoff between security and performance. This research is an attempt at shifting the security-performance tradeoff paradigm in this realm. To this end, we propose a modification to Gennaro's pseudorandom number generator via replacing word-wise arithmetic operations with bit-wise logical operations in trapdoor and hard-core functions. The security of our generator (like that of Gennaro's) is based on the hardness of a special variant of the discrete logarithm problem. We establish an equivalence between the specific variant of the discrete logarithm problem with the standard problem. Moreover, we demonstrate that in the modified generator, performance will be almost independent of the security parameter as logical operations can be performed in register level without the interference of the Arithmetic-Logic Unit (ALU). This relaxes the security-performance tradeoff and allows designers to maneuver more flexibly in the tradeoff space. We implement and evaluate our proposed generator and prove its security. Our CSPRNG is deemed random by all randomness tests in NIST SP 800-22 suite.
KW - Cryptographically-secure pseudorandom number generator
KW - Discrete logarithm problem
KW - Mersenne primes
KW - Security-performance tradeoff
UR - http://www.scopus.com/inward/record.url?scp=85146417616&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85146417616&partnerID=8YFLogxK
U2 - 10.1016/j.jisa.2023.103430
DO - 10.1016/j.jisa.2023.103430
M3 - Article
AN - SCOPUS:85146417616
SN - 2214-2134
VL - 73
JO - Journal of Information Security and Applications
JF - Journal of Information Security and Applications
M1 - 103430
ER -