Cryptanalysis of the Legendre PRF

This repository contains research and implementations of cryptanalysis techniques for the Legendre Pseudorandom Function (PRF) and its generalizations. The work primarily follows the 2019 paper by Beullens et al.

Directory Structure

• src/: Core primitives and PRF implementations.
  • math_utils.py: Legendre and Jacobi symbol implementations.
  • prfs.py: Linear and higher-degree Legendre PRF constructions.
  • sequences.py: Arithmetic and geometric L-sequence generation.
• attacks/: Implementation of cryptanalytic attacks.
  • baselines.py: Brute-force and simple birthday attacks.
  • beullens_2019.py: Table-based collision search (Section 3).
• experiments/: Verification scripts and statistical analysis.
  • weil_bound.py: Study of the distribution of Legendre symbols.
• papers/: Reference documentation and research papers.

Current State

• Implementation of Legendre and Jacobi symbols.
• Linear and higher-degree Legendre PRF keystream generation.
• Basic table-based collision attack for the linear case.
• Statistical verification of the Weil bound.

Future Work

• Implement Section 3.4 optimizations (Consecutive values of c).
• Extend the table-based collision attack to the higher-degree case (Section 4).
• Analyze weak keys in the higher-degree variant via polynomial factorization (Section 5).
• Implement Jacobi and Power Residue PRF analysis (Sections 6 and 7).