Content area
Abstract
Learning homomorphisms with noise (LHN) is a group-theoretic learning problem generalizing quantum-safe computational assumptions like learning parity with noise (LPN) and well-established learning with errors (LWE). The LHN problem associated with Burnside groups of exponent three is referred to as learning Burnside homomorphisms with noise (Bn-LHN). In a nutshell, the Bn-LHN problem focuses on recovering a secret homomorphism between Burnside groups, given polynomially many “noisy” samples. Previous work assessed important combinatorial properties and basic cryptographic applications of the Bn-LHN problem, but did not address efficient constructions of a fundamental cryptographic primitive known as pseudorandom function (PRF).
This dissertation presents a derandomization technique for the Bn-LHN problem that results in a novel computational assumption, referred to as learning Burnside homomorphisms with rounding (Bn-LHR), that does not rely on an underlying noise distribution. It then establishes its security by exhibiting a complexity reduction from the Bn-LHN problem. Overall, this enables the application of standard cryptographic constructions that do not easily accommodate the presence of noise, while still achieving security guarantees comparable to the original Bn-LHN assumption.
This work then introduces three novel PRF constructions based on the decisional Bn-LHR assumption. The first construction relies on pseudorandom synthesizers (PRSs) and entails a very large PRF secret-key. The second construction attains better key-size parameters by first deriving a length-doubling pseudorandom generator (PRG) from a weak PRF family, and then employing said PRG as an intermediate function in the seminal PRG-to-PRF construction of Goldreich, Goldwasser, and Micali (GGM). Finally, the third construction enhances the PRF design by introducing a PRG with associated public parameters.
As a second direction, this dissertation outlines the design of three progressively refined PRF constructions grounded in the original Bn-LHN assumption. All the designs capitalize on the low entropy of noise elements within the Burnside group and hold promise for even more efficient Burnside-based PRF constructions. Finally, to maximize the efficiency of these PRF constructions, this work also investigates approaches to improve computations over Burnside groups. In particular, it explores optimizations of its group operation and carries out an in-depth analysis of the Burnside noise distribution. This latter analysis contributes valuable insights into establishing the hardness connection between the Bn-LHN and the Bn-LHR problems.
