Lower Bounds on Black-Box Constructions of Pseudorandom Functions

A Complexity-Theoretic Approach to Proofs of Space

It is shown that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits, and (b) collision-resistant hash functions, and (c) SNARGs for $\mathsf{P}$.

RAA Codes

Bachelor’s Thesis Computing Science

Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

We make progress on the question of constructing explicit evaluation places for leakage-resilient Shamir's secret sharing, over composite order fields. Previously, Maji et al. (EUROCRYPT 2024) showed that random evaluation places yield Shamir's secret sharing over the composite order field $\mathbb{F}_{p^d}$ that is statistically secure against physical-bit leakage. Later, Nguyen (EUROCRYPT 2025) established a dichotomy that linear code-based secret-sharing scheme over the field $\mathbb{F}_{p^d}$ is either statistically secure or completely insecure against such leakage. Building upon Nguyen's dichotomy, we present a partial derandomization of evaluation places, improving upon the Maji et al. result for a restricted regime of parameters. We replace the random choice of $n$ independent evaluation places by the iterates $x_j = \Phi^j(x_0)$ of a simple fixed rational function $\Phi$, where the initial point $x_0 \in \mathbb{F}_{p^d}^*$ is randomly chosen. The randomness in the evaluation places thus drops from $nd \log p$ bits to $d\log p$ bits. Our construction is valid for the regime $n = O(d/\log_p d)$, and any reconstruction threshold $k \ge 2$; in fact, the scheme attains perfect security (statistical distance exactly zero) against single-block leakage. Our technique is a partial fraction nondegeneracy argument that exploits the distinct poles of the rational iterates.

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$, Generically)

We present a new generic transformation from weak PRFs computable in depth $d(n) = \Omega(\log n)$ to strong PRFs computable in depth $O(d(n))$. This construction refines the classical tree-based paradigm of GGM by {tapering} the internal state so the per-level depth decreases geometrically. We complement the above with new depth-efficient weak PRF constructions based on various standard assumptions. As a corollary, we obtain new $\mathsf{NC}^1$-computable PRFs from various classical assumptions, resolving several long-standing open problems. Concretely, for the first time, we obtain $\mathsf{NC}^1$-computable PRFs: (1) from the \textbf{Learning With Errors (LWE)} assumption with a polynomial modulus-to-noise ratio, improving upon prior low-depth constructions that required Ring-LWE with super-polynomial ratios [Banerjee-Peikert-Rosen, EUROCRYPT 2012]; (2)from the standard \textbf{Learning Parity with Noise (LPN)} assumption, removing the need for structured LPN variants [Boyle et al., FOCS 2020], [Ding-Jain-Komargodski, STOC 2025]; (3) from the \textbf{Computational Diffie-Hellman (CDH)} assumption; prior works relied on the stronger Decisional Diffie-Hellman (DDH) or generalized Diffie-Hellman (GDH) assumptions [Naor-Reingold, FOCS'97, J. ACM'04].

Cryptanalysis of 7-Round AES via the Algebraic Structure of its S-box