Past REU Projects

Classifying Rational Functions over Finite Fields

Mentor: Xiang-Dong Hou
Participants: Siyu Peng (MIT), Yongyu Qiang (Georgia Tech)

Finite fields are central objects in modern cryptography and coding theory. In this project, students studied functions \( f : \mathbb{F}_q \rightarrow \mathbb{F}_q \) and how their properties behave under algebraic transformations.

A key quantity in cryptography is the differential uniformity \[ \delta(f) = \max_{a,b \in \mathbb{F}_q,\, a\neq 0} \left|\{x \in \mathbb{F}_q : f(x+a)-f(x)=b\}\right|. \] Functions with small values of \( \delta(f) \) are resistant to differential cryptanalysis and appear in the design of secure block ciphers.

The project explored the classification of low-degree rational functions under transformations of the projective linear group \( \mathrm{PGL}(2,\mathbb{F}_q) \), with the goal of identifying canonical representatives of each equivalence class and studying their cryptographic properties.

Climbing the Clifford Hierarchy

Mentor: Tefjol Pllaha
Participants: Samuel Glandon (University of Tennessee Chattanooga), Madison Stewart (University of Texas Austin)

Fault-tolerant quantum computation relies on a special family of quantum gates known as the Clifford hierarchy. These gates determine which operations can be implemented reliably on quantum computers protected by error-correcting codes. In this project, students studied the structure of this hierarchy and investigated when certain quantum gates can be lifted to higher levels by taking square roots.

The hierarchy is defined recursively: the first level is the Pauli group and higher levels contain unitaries that conjugate Pauli operators to lower levels, \[ C^{(1)}_n = \mathcal{P}_n, \qquad C^{(k)}_n = \{\, U \mid U P U^\dagger \in C^{(k-1)}_n \ \text{for all } P \in \mathcal{P}_n \,\}. \] Understanding the structure of these levels is central to the theory of fault-tolerant quantum computation.

The students analyzed when taking square roots of Clifford gates allows one to “climb” the hierarchy and proved new structural results characterizing when this phenomenon occurs. Their work combines algebraic methods, symplectic geometry, and quantum circuit theory, and culminated in a research paper on the structure of the Clifford hierarchy and its implications for implementing quantum gates in fault-tolerant architectures.

Group-Based Cryptography and Automaton Groups

Mentor: Dmytro Savchuk
Participants: Fahran Bajaj (University of Maryland College Park), Winona Wherley (Grove City College)

This project explored cryptographic constructions based on non-abelian groups. While many classical cryptographic protocols such as Diffie–Hellman rely on commutative algebraic structures, group-based cryptography investigates protocols whose security depends on difficult computational problems in non-commutative groups.

The students studied groups generated by automata acting on rooted trees, a class of objects arising in geometric group theory and dynamical systems. In particular, they investigated contracting self-similar groups, where elements admit recursive descriptions through their actions on subtrees.

The project analyzed a heuristic attack against the simultaneous conjugacy search problem: find an element \( r \in G \) such that \( r^{-1} a_i r = b_i \) for all \( i \). The attack reconstructs the hidden conjugator by recovering its action level-by-level on the underlying rooted tree.

The resulting work combines ideas from combinatorial group theory, automaton groups, and computational experimentation using the GAP computer algebra system.

Quantum Secret Sharing and Quantum Multi-Party Computation

Mentor: Kwan-Cheng Chen
Participants: Andrew Del Real (Carthage College), Alexander Nwanganga (Andrews University)

This project explored the foundations of quantum cryptography, focusing on protocols that allow multiple parties to securely share and process information using quantum communication.

The students studied quantum secret sharing, a quantum analogue of classical secret sharing schemes that distribute a secret among multiple participants so that only authorized subsets can reconstruct it. These protocols build on ideas from quantum key distribution (QKD) and are closely related to broader questions in secure multi-party computation.

A central focus of the project was the study of quantum garbled circuits, a recent framework extending Yao’s classical garbled circuit technique to the quantum setting. The project investigated how these tools can enable robust quantum secret-sharing protocols and secure distributed quantum computation.

Through this work, the students explored connections between quantum information theory, cryptographic protocol design, and emerging quantum communication networks.

Fourier Analysis of Vectorial Boolean Functions

Mentor: Lukas Koelsch
Participants: Sophie Bénéteau (University of Florida), Nicolas Goluboff (University of Massachusetts Amherst)

Vectorial Boolean functions play a central role in modern symmetric cryptography, serving as nonlinear building blocks in block ciphers. To resist differential and linear cryptanalysis, such functions must exhibit strong nonlinear behavior.

In this project, the students investigated how tools from discrete Fourier analysis can reveal hidden structure in these functions. Given a mapping \(F : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m\), the Walsh transform

\( W_F(b,a) = \sum_{x \in \mathbb{F}_2^n} (-1)^{\langle b,F(x)\rangle + \langle a,x\rangle} \)

measures correlations between the function and linear mappings. These spectral properties determine important cryptographic parameters such as linearity and differential resistance.

The project focused on almost perfect nonlinear (APN) functions, which are optimal against differential attacks. By studying the Walsh spectra of quadratic APN functions, the students discovered new structural connections between spectral amplitudes, vector space partitions, and geometric objects such as blocking sets in projective space.

Their work led to new theoretical results on the amplitude distribution of Walsh spectra and culminated in a research preprint produced during the REU program.

Quantum Dynamics and Logical Operations with Qubits

Mentor: Razvan Teodorescu
Participants: Diba Imran (Bard College), Gregory Wickham (Harvey Mudd College)

Quantum computing relies on the manipulation of qubits, the fundamental two–state quantum systems that encode quantum information. In this project, students studied mathematical models describing the dynamics and logical operations of two–level quantum systems.

The project focused on the Hamiltonian model of a qubit,

\( H(\lambda,\Delta,\epsilon) = \lambda I + \begin{pmatrix} \epsilon & \Delta \\ \Delta & -\epsilon \end{pmatrix} \)

which governs the time evolution of the quantum state through the unitary operator \(U(t)=e^{itH}\). By analyzing this evolution, the students explored how qubits evolve over time and how measurements depend on the interaction between the system and its environment.

A second component of the project examined how logical operations on qubits can be represented algebraically using the groups \(U(2)\) and \(SU(2)\). The students studied how quantum gates correspond to unitary transformations, investigated representations of logical operations within these groups, and analyzed how external perturbations can lead to decoherence and loss of quantum information.

Algorithms for the Code Equivalence Problem

Mentor: Jean-François Biasse
Participants: Drisana Bhatia (University of California Berkeley), Medha Durisheti (Virginia Tech), Lucas LaBuff (University of Maryland College Park)

The code equivalence problem asks whether two linear error-correcting codes are the same up to a symmetry of the ambient space. More precisely, given two codes \(C_1, C_2 \subseteq \mathbb{F}_q^n\), the goal is to determine whether there exists an isometry \(\tau\) such that

\( C_2 = \tau(C_1). \)

This problem lies at the intersection of coding theory, computational complexity, and cryptography. It is closely related to the Graph Isomorphism problem and plays an important role in the security of several post-quantum cryptographic constructions.

In this project, the students studied new provable algorithms for the Linear Code Equivalence (LCE) and Permutation Code Equivalence (PCE) problems. Building on recent advances in algorithmic group theory and graph isomorphism techniques, they analyzed algorithms whose running times are in \(O(2^{n})\) (deterministic), \(O(2^{n/2})\) (probabilistic) and \(O(2^{n/3})\) (quantum).

These algorithms significantly improve the theoretical understanding of the complexity of code equivalence on arbitrary linear codes over finite fields. The project combined ideas from coding theory, combinatorics, and algorithm design and resulted in a research paper produced during the REU program.

Locally Recoverable Codes with High Availability

Mentor: Giacomo Micheli
Participants: Abhi Shukul (University of Michigan Ann Arbor), Noah Smith (Occidental College)

Modern cloud storage systems distribute data across large networks of servers. To ensure reliability when nodes fail or become temporarily unavailable, storage systems rely on error-correcting codes that allow data to be reconstructed efficiently. A particularly important class of such codes are Locally Recoverable Codes (LRCs), which enable the recovery of a lost symbol by accessing only a small number of other symbols.

In this project, the students studied LRCs with availability, a property that guarantees multiple independent ways to recover the same erased symbol. Formally, a linear code \(C\) has locality \(r\) and availability \(t\) if every coordinate can be reconstructed from \(t\) disjoint subsets of at most \(r\) other coordinates. These parameters are constrained by the generalized Singleton bound

\( d \le n - k - \left\lceil \frac{k}{r} \right\rceil + 2. \)

The project explored new constructions of locally recoverable codes with large availability using algebraic techniques over finite fields. In particular, the students analyzed families of codes arising from polynomial constructions and investigated how their parameters (locality, availability, and minimum distance) behave asymptotically.

Their work contributed to the development of new infinite families of locally recoverable codes with large availability, with applications to reliable distributed storage systems. The results led to a research publication.

Heuristic Attacks on the Simultaneous Conjugacy Search Problem

Mentor: Dmytro Savchuk
Participants: Luciana Scuderi (Truman State University), Kerry Seekamp (Smith College)

Several cryptographic proposals rely on computational problems arising in non-commutative algebraic structures. One important example is the Simultaneous Conjugacy Search Problem (SCSP): given elements \(g_1,\ldots,g_n\) and \(h_1,\ldots,h_n\) in a group \(G\) such that

\(h_i = r^{-1} g_i r\)

for some unknown element \(r \in G\), the goal is to recover the conjugator \(r\). This problem underlies several group-based cryptographic protocols such as the Anshel–Anshel–Goldfeld and Ko–Lee key exchange schemes.

In this project, the students investigated the SCSP in contracting self-similar groups acting on rooted trees. These groups admit compact representations of elements through nucleus portraits, which encode group elements as labeled trees. Using this structure, the team developed and implemented a portrait-based heuristic attack that reconstructs the secret conjugator level-by-level from the portraits of conjugate elements.

The project combined computational experimentation in the GAP computer algebra system with theoretical analysis of the algorithm’s complexity and effectiveness across several classes of automaton groups. The work resulted in a research preprint produced during the REU program.

Automorphism Groups of Rank-Metric Codes

Mentor: Lukas Koelsch
Participants: Alexandra Levinshteyn (University of Illinois Urbana–Champaign), Milan Tenn (Swarthmore College)

Rank-metric codes are linear spaces of matrices where the distance between two codewords is measured by the rank of their difference. These codes play an increasingly important role in modern coding theory and cryptography, with applications ranging from network coding to post-quantum cryptography. One of the key structural questions about such codes is understanding their automorphism group, which captures the symmetries of the code.

In this project, the students investigated the automorphism groups of certain optimal rank-metric codes arising from finite semifields. These objects can be represented as sets of matrices \(C \subseteq M_{n\times n}(\mathbb{F}_p)\) satisfying the optimal Singleton bound for the rank metric. Their automorphism group is defined by

\(\mathrm{Aut}(C) = \{(X,Y) \in GL(n,p)\times GL(n,p) \;:\; XCY = C\}.\)

The team combined computational experiments with theoretical analysis to determine the full automorphism group for a large family of rank-metric codes arising from recently constructed commutative semifields. Their work established that all automorphisms are semilinear transformations over a degree-two subfield and that the resulting automorphism groups are always solvable.

The results of this project led to a research paper produced during the REU program.

Sum-Free Boolean Functions and Cryptographic Applications

Mentor: Xiang-Dong Hou
Participants: Alyssa Ebeling (Wisconsin Lutheran College), Ashley Rydell (Sonoma State University)

Boolean functions \(f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n}\) play a central role in modern cryptography, where they are used as nonlinear components (S-boxes) in block ciphers. To resist classical attacks such as linear and differential cryptanalysis, these functions must satisfy strong algebraic properties including high nonlinearity and low differential uniformity. In particular, functions with optimal resistance to differential attacks are known as almost perfect nonlinear (APN) functions.

This project investigated a recent generalization of APN functions known as sum-free functions. A function \(f : \mathbb{F}_{2^n} \to \mathbb{F}_{2^n}\) is called kth-order sum-free if the sum of its values over every \(k\)-dimensional affine subspace \(A \subseteq \mathbb{F}_{2^n}\) satisfies

\(\sum_{x \in A} f(x) \neq 0.\)

The project focused on a conjecture concerning the multiplicative inverse function \(f_{\mathrm{inv}}(x) = x^{-1}\) (with \(f_{\mathrm{inv}}(0)=0\)), which is widely used in cryptographic constructions. The team analyzed when this function can be sum-free of higher order, combining tools from finite field theory, algebraic geometry, and computational experimentation.

Their work established new results confirming the conjecture in several important cases and explored extensions of the problem to more general finite fields. The project resulted in a research paper produced during the REU program.

Breaking a Post-Quantum Digital Signature Scheme

Mentor: Dmytro Savchuk
Participant: Kianna Cabral (Northeastern University)

As quantum computers threaten traditional public-key cryptography, researchers worldwide are searching for new post-quantum cryptographic systems. However, designing secure schemes is extremely difficult: many promising candidates are later shown to contain subtle mathematical weaknesses.

In this project, the student studied the digital signature scheme Xifrat1-Sign.I, a proposed post-quantum system based on algebraic structures called quasigroups. The goal was to analyze the security of the scheme using both statistical experiments and algebraic methods implemented in the computer algebra system GAP.

The investigation revealed structural weaknesses in the mixing functions used by the scheme. In particular, the functions exhibit a cyclic behavior that allows the secret key to be recovered by repeatedly applying the public operation. Concretely, if the public key contains values \(p_1 = \mathrm{DUP}(c,k)\) and \(p_2 = \mathrm{DUP}(k,q)\), then iterating the operation roughly \(480\) times recovers the secret key components \(k\) and \(q\). :contentReference[oaicite:0]{index=0}

This discovery leads to a practical attack that breaks the cryptosystem in seconds. The project combined theoretical cryptanalysis, statistical testing (NIST randomness, avalanche, and collision tests), and computational experiments, resulting in a research paper describing the attack.

A Post-Quantum Verifiable Random Function from Code Equivalence

Mentor: Jean-François Biasse
Participants: Franklin Harding (Oregon State University), Siddarth Sitaraman (Brown University)

Verifiable Random Functions (VRFs) are cryptographic primitives that produce outputs that appear random but whose correctness can be publicly verified. They play an important role in modern distributed systems, including blockchain consensus mechanisms such as Algorand.

In this project, the students explored how to design a post-quantum VRF using the Code Equivalence Problem, a computational problem from coding theory. The goal was to replace classical VRFs based on discrete logarithms—which are vulnerable to quantum attacks—with constructions relying on the hardness of finding transformations between equivalent linear codes.

The project resulted in a proof-of-concept construction of a VRF based on signed permutation equivalence of linear codes, together with a zero-knowledge proof protocol used to verify the correctness of the VRF output.

Interestingly, shortly after the REU concluded, follow-up research identified structural weaknesses in the proof of concept. This led to a refinement of the theoretical framework surrounding group-action-based VRFs and helped clarify which assumptions are necessary for secure post-quantum constructions.

Efficient Implementations of Post-Quantum and Classical Cryptography

Mentor: Mehran Mozaffari Kermani
Participants: Habiba Abouzaid (Polk State College), Tyson Thomas (Bethune-Cookman University)

Modern cryptographic systems must not only be mathematically secure but also efficient and reliable in real-world implementations. This project focused on implementing and optimizing both classical and post-quantum cryptographic algorithms used in secure communications.

The students studied and implemented the CRYSTALS-Kyber key-encapsulation mechanism, one of the algorithms selected in the NIST post-quantum cryptography standardization process. Kyber is based on the hardness of the Learning With Errors (LWE) problem and is designed to remain secure even in the presence of quantum computers.

In addition, the project explored implementations of Elliptic Curve Cryptography (ECC) together with techniques for algorithm-level fault detection, an important countermeasure against hardware fault attacks that attempt to extract secret keys from cryptographic devices.

By combining software implementation, performance analysis, and security considerations, the project gave students hands-on experience with the engineering challenges involved in deploying cryptography in practical systems.

Normal Polynomials and Symmetrization Methods in Finite Fields

Mentor: Xiang-Dong Hou
Participants: Darien Connolly (SUNY Geneseo), Calvin George (Dartmouth College), Adam Madro (Boston College)

Normal bases are fundamental objects in finite field theory and play an important role in applications such as coding theory and cryptography. A polynomial over a finite field is called normal if its roots form a normal basis of the corresponding field extension.

If an irreducible polynomial over \( \mathbb{F}_q \) has roots \( r, r^q, \ldots, r^{q^{n-1}} \), then it is normal precisely when the following circulant determinant is nonzero:

\[ \Delta_n(r,r^q,\ldots,r^{q^{n-1}})= \det \begin{pmatrix} r & r^q & \cdots & r^{q^{n-1}} \\ r^{q^{n-1}} & r & \cdots & r^{q^{n-2}} \\ \vdots & \vdots & \ddots & \vdots \\ r^q & r^{q^2} & \cdots & r \end{pmatrix} \neq 0 . \]

The project studied how to transform this root-based criterion into conditions on the coefficients of the polynomial using symmetrization techniques. This approach leads to practical tests for determining when polynomials over finite fields are normal and resulted in a research article developing new methods for detecting normal polynomials. :contentReference[oaicite:0]{index=0}