TY - GEN
T1 - Learning Burnside Homomorphisms with Rounding and Pseudorandom Function
AU - Pandey, Dhiraj K.
AU - Nicolosi, Antonio R.
N1 - Publisher Copyright:
© 2024, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2024
Y1 - 2024
N2 - The use of pseudorandom function (PRF) and weak PRF as foundational primitives is common in a variety of cryptographic applications, including encryption, authentication, and identification. In this paper, we present a new PRF construction derived from a weak PRF family. Specifically, we propose a derandomization technique from a post-quantum hardness assumption known as learning Burnside homomorphisms with noise (Bn -LHN). Through the derandomization, a new hardness assumption arises, which we refer to as learning Burnside homomorphisms with rounding (Bn -LHR). We establish the security of the derandomization by demonstrating that the Bn -LHR problem is at least as hard as the Bn -LHN problem. In the work by Naor and Reingold (NR), a PRF construction is introduced based on a weak PRF family, utilizing a novel cryptographic primitive called a pseudorandom synthesizer (PRS). However, this approach necessitates an excessively large key size to design a PRF family. To overcome this issue and produce a more efficient PRF construction, we design a length-doubling pseudorandom generator (PRG) from a weak PRF. Here, the PRG is defined using the secret-key components of a PRF. Notably, in our PRF construction, the length-doubling PRG exhibits efficiency primarily when employed as an intermediate function. We also provide insight into the Bn -LHR problem by discussing the details of the concatenation operation and error distribution in the Burnside group.
AB - The use of pseudorandom function (PRF) and weak PRF as foundational primitives is common in a variety of cryptographic applications, including encryption, authentication, and identification. In this paper, we present a new PRF construction derived from a weak PRF family. Specifically, we propose a derandomization technique from a post-quantum hardness assumption known as learning Burnside homomorphisms with noise (Bn -LHN). Through the derandomization, a new hardness assumption arises, which we refer to as learning Burnside homomorphisms with rounding (Bn -LHR). We establish the security of the derandomization by demonstrating that the Bn -LHR problem is at least as hard as the Bn -LHN problem. In the work by Naor and Reingold (NR), a PRF construction is introduced based on a weak PRF family, utilizing a novel cryptographic primitive called a pseudorandom synthesizer (PRS). However, this approach necessitates an excessively large key size to design a PRF family. To overcome this issue and produce a more efficient PRF construction, we design a length-doubling pseudorandom generator (PRG) from a weak PRF. Here, the PRG is defined using the secret-key components of a PRF. Notably, in our PRF construction, the length-doubling PRG exhibits efficiency primarily when employed as an intermediate function. We also provide insight into the Bn -LHR problem by discussing the details of the concatenation operation and error distribution in the Burnside group.
KW - (Weak) Pseudorandom Function
KW - Burnside Group
KW - Derandomization
KW - Learning Homomorphisms with Noise/Rounding
KW - Post Quantum Cryptography
UR - http://www.scopus.com/inward/record.url?scp=85184280262&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85184280262&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-52947-4_13
DO - 10.1007/978-3-031-52947-4_13
M3 - Conference contribution
AN - SCOPUS:85184280262
SN - 9783031529467
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 178
EP - 196
BT - Innovative Security Solutions for Information Technology and Communications - 16th International Conference, SecITC 2023, Revised Selected Papers
A2 - Manulis, Mark
A2 - Maimuţ, Diana
A2 - Teşeleanu, George
T2 - 16th International Conference on Innovative Security Solutions for Information Technology and Communications, SecITC 2023
Y2 - 23 November 2023 through 24 November 2023
ER -