Average Hardness of SIVP for Module Lattices of Fixed Rank

The problem of finding short vectors in Euclidean lattices is a central hard problem in complexity theory. The case of module lattices i.e., lattices which are also modules over a number ring is of particular interest for cryptography and computational number theory. The hardness of finding short...

Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond

One-way functions OWFs form the foundation of modern cryptography, yet their unconditional existence remains a major open question. In this work, we study this question by exploring its relation to lossy reductions, i.e., reductions$R$ for which it holds that $IX;RX \ll n$ for all distributions$X...

The Planted Orthogonal Vectors Problem

In the $k$-Orthogonal Vectors $k$-OV problem we are given $k$ sets, each containing $n$ binary vectors of dimension $d=n^o1$, and our goal is to pick one vector from each set so that at each coordinate at least one vector has a zero. It is a central problem in fine-grained complexity, conjectured...