Learning Burnside Homomorphisms with Rounding and Pseudorandom Function

Dhiraj K. Pandey, Antonio R. Nicolosi

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationInnovative Security Solutions for Information Technology and Communications - 16th International Conference, SecITC 2023, Revised Selected Papers
EditorsMark Manulis, Diana Maimuţ, George Teşeleanu
Pages178-196
Number of pages19
DOIs
StatePublished - 2024
Event16th International Conference on Innovative Security Solutions for Information Technology and Communications, SecITC 2023 - Bucharest, Romania
Duration: 23 Nov 202324 Nov 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14534
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Innovative Security Solutions for Information Technology and Communications, SecITC 2023
Country/TerritoryRomania
CityBucharest
Period23/11/2324/11/23

Keywords

  • (Weak) Pseudorandom Function
  • Burnside Group
  • Derandomization
  • Learning Homomorphisms with Noise/Rounding
  • Post Quantum Cryptography

Fingerprint

Dive into the research topics of 'Learning Burnside Homomorphisms with Rounding and Pseudorandom Function'. Together they form a unique fingerprint.

Cite this