## Foundations of CryptographyThis line of work studies new assumptions and approaches for constructing basic cryptographic primitives (e.g., pseudorandom functions) as well as the limitations (i.e., lower bounds) of using such primitives to construct more advanced cryptographic functionalities. ## Exploring Crypto Dark Matter: New Simple PRF Candidates and Their Applications
Abstract:
Pseudorandom functions (PRFs) are one of the fundamental building blocks in cryptography. We explore a new space of plausible PRF candidates that are obtained by mixing linear functions over different small moduli. Our candidates are motivated by the goals of maximizing simplicity and minimizing complexity measures that are relevant to cryptographic applications such as secure multiparty computation. We present several concrete new PRF candidates that follow the above approach.
Our main candidate is a The advantage of our approach is twofold. On the theoretical side, the
simplicity of our candidates enables us to draw natural connections between
their hardness and questions in complexity theory or learning theory (e.g.,
learnability of depth-2 ACC Finally, we introduce a new primitive we call an
**Paper:**[PDF], [ePrint Version]
BibTeX:
@inproceedings{BIPSW18, author = {Dan Boneh and Yuval Ishai and Alain Passel{\`{e}}gue and Amit Sahai and David J. Wu}, title = {Exploring Crypto Dark Matter: New Simple {PRF} Candidates and Their Applications}, booktitle = {{TCC}}, year = {2018} } ## Can Verifiable Delay Functions be Based on Random Oracles?
Abstract:
Boneh, Bonneau, Bünz, and Fisch (CRYPTO 2018) recently introduced the notion
of a In this work, we study whether VDFs can be constructed from ideal hash
functions in a black-box way, as modeled in the random oracle model (ROM). In
the ROM, we measure the running time by the number of oracle queries and the
sequentiality by the number of We show that VDFs satisfying *perfect*uniqueness (i.e., no different convincing solution \( y' \neq y \) exists) cannot be constructed in the ROM. More formally, we give an attacker that finds the solution \( y \) in \( \approx t \)*rounds*of queries, asking only \( \text{poly}(T) \) queries in total.
We also rule out *tight*VDFs in the ROM. Tight VDFs were recently studied by Döttling, Garg, Malavolta, and Vasudevan (ePrint Report 2019) and require sequentiality \( \sigma \approx T-T^\rho \) for some constant \( 0 \lt \rho \lt 1 \). More generally, our lower bound also applies to proofs of sequential work (i.e., VDFs without the uniqueness property), even in the private verification setting, and sequentiality \( \sigma \gt T- T / (2t) \) for a concrete verification time \( t \).
**Paper:**[PDF], [ePrint Version]
BibTeX:
@inproceedings{MSW20, author = {Mohammad Mahmoody and Caleb Smith and David J. Wu}, title = {Can Verifiable Delay Functions be Based on Random Oracles?}, booktitle = {{ICALP}}, year = {2020} } |