@inproceedings{20846,
  abstract     = {CVRFs are PRFs that unify the properties of verifiable and constrained PRFs. Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy in 2014, it has been an open problem to construct CVRFs without using heavy machinery such as multilinear maps, obfuscation or functional encryption.
We solve this problem by constructing a prefix-constrained verifiable PRF that does not rely on the aforementioned assumptions. Essentially, our construction is a verifiable version of the Goldreich-Goldwasser-Micali PRF. To achieve verifiability we leverage degree-2 algebraic PRGs and bilinear groups. In short, proofs consist of intermediate values of the Goldreich-Goldwasser-Micali PRF raised to the exponents of group elements. These outputs can be verified using pairings since the underlying PRG is of degree 2.
We prove the selective security of our construction under the Decisional Square Diffie-Hellman (DSDH) assumption and a new assumption, which we dub recursive Decisional Diffie-Hellman (recursive DDH).
We prove the soundness of recursive DDH in the generic group model assuming the hardness of the Multivariate Quadratic (MQ) problem and a new variant thereof, which we call MQ+.
Last, in terms of applications, we observe that our CVRF is also an exponent (C)VRF in the plain model. Exponent VRFs were recently introduced by Boneh et al. (Eurocrypt’25) with various applications to threshold cryptography in mind. In addition to that, we give further applications for prefix-CVRFs in the blockchain setting, namely, stake-pooling and compressible randomness beacons.},
  author       = {Brandt, Nicholas and Cueto Noval, Miguel and Günther, Christoph Ullrich and Ünal, Akin and Wohnig, Stella},
  booktitle    = {23rd International Conference on Theory of Cryptography},
  isbn         = {9783032122896},
  issn         = {1611-3349},
  location     = {Aarhus, Denmark},
  pages        = {478--511},
  publisher    = {Springer Nature},
  title        = {{Constrained verifiable random functions without obfuscation and friends}},
  doi          = {10.1007/978-3-032-12290-2_16},
  volume       = {16271},
  year         = {2025},
}

@inproceedings{20587,
  abstract     = {The blocks in the Bitcoin blockchain "record" the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF).
In this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks.
We completely classify such functions in an idealized "continuous" model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the "timed" resources V and W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) = W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia).
Our classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂. Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g., √{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these are much better choices.},
  author       = {Baig, Mirza Ahad and Günther, Christoph Ullrich and Pietrzak, Krzysztof Z},
  booktitle    = {7th Conference on Advances in Financial Technologies},
  isbn         = {9783959774000},
  issn         = {1868-8969},
  location     = {Pittsburgh, PA, United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Nakamoto consensus from multiple resources}},
  doi          = {10.4230/LIPIcs.AFT.2025.16},
  volume       = {354},
  year         = {2025},
}

@inproceedings{20844,
  abstract     = {We introduce and construct a new proof system called Non-interactive Arguments of Knowledge or Space (NArKoS), where a space-bounded prover can convince a verifier they know a secret, while having access to sufficient space allows one to forge indistinguishable proofs without the secret.
An application of NArKoS are space-deniable proofs, which are proofs of knowledge (say for authentication in access control) that are sound when executed by a lightweight device like a smart-card or an RFID chip that cannot have much storage, but are deniable (in the strong sense of online deniability) as the verifier, like a card reader, can efficiently forge such proofs.
We construct NArKoS in the random oracle model using an OR-proof combining a sigma protocol (for the proof of knowledge of the secret) with a new proof system called simulatable Proof of Transient Space (simPoTS). We give two different constructions of simPoTS, one based on labelling graphs with high pebbling complexity, a technique used in the construction of memory-hard functions and proofs of space, and a more practical construction based on the verifiable space-hard functions from TCC’24 where a prover must compute a root of a sparse polynomial. In both cases, the main challenge is making the proofs efficiently simulatable.},
  author       = {Dujmovic, Jesko and Günther, Christoph Ullrich and Pietrzak, Krzysztof Z},
  booktitle    = {23rd International Conference on Theory of Cryptography},
  isbn         = {9783032122896},
  issn         = {1611-3349},
  location     = {Aarhus, Denmark},
  pages        = {171--202},
  publisher    = {Springer Nature},
  title        = {{Space-deniable proofs}},
  doi          = {10.1007/978-3-032-12290-2_6},
  volume       = {16271},
  year         = {2025},
}

@inproceedings{17051,
  abstract     = {Memory-hard functions (MHF) are functions whose evaluation provably requires
a lot of memory. While MHFs are an unkeyed primitive, it is natural to consider the
notion of trapdoor MHFs (TMHFs). A TMHF is like an MHF, but when sampling
the public parameters one also samples a trapdoor which allows evaluating the
function much cheaper.
Biryukov and Perrin (Asiacrypt’17) were the first to consider TMHFs and put
forth a candidate TMHF construction called Diodon that is based on the Scrypt
MHF (Percival, BSDCan’09). To allow for a trapdoor, Scrypt’s initial hash chain
is replaced by a sequence of squares in a group of unknown order where the order of
the group is the trapdoor. For a length n sequence of squares and a group of order
N, Diodon’s cumulative memory complexity (CMC) is O(n2log N) without the
trapdoor and O(n log(n) log(N)2) with knowledge of it.
While Scrypt is proven to be optimally memory-hard in the random oracle
model (Alwen et al., Eurocrypt’17), Diodon’s memory-hardness has not been
proven so far. In this work, we fill this gap by rigorously analyzing a specific
instantiation of Diodon. We show that its CMC is lower bounded by Ω( n2log nlog N)
which almost matches the upper bound. Our proof is based Alwen et al.’s lower
bound on Scrypt’s CMC but requires non-trivial modifications due to the algebraic
structure of Diodon. Most importantly, our analysis involves a more elaborate
compression argument and a solvability criterion for certain systems of Diophantine
equations.},
  author       = {Auerbach, Benedikt and Günther, Christoph Ullrich and Pietrzak, Krzysztof Z},
  booktitle    = {43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques},
  isbn         = {9783031587337},
  issn         = {1611-3349},
  location     = {Zurich, Switzerland},
  pages        = {315--344},
  publisher    = {Springer Nature},
  title        = {{Trapdoor memory-hard functions}},
  doi          = {10.1007/978-3-031-58734-4_11},
  volume       = {14653},
  year         = {2024},
}

@article{18961,
  abstract     = {Automated contact tracing (ACT) emerged as a promising measure to curb the spread of Covid-19. Users enable ACT on their smartphones to automatically record contacts with other users. If a user tests positive for the disease, they report their diagnosis to alert their contacts.
Designing effective ACT protocols is challenging since they need to be efficient and secure while also ensuring users' privacy. As ACT protocols necessarily leak some information by design, defining privacy is difficult. For example, a user cannot deny having met another user. Ideally, however, the user can plausibly deny everything else, in particular, when they met. We call this privacy property contact-time deniability.
While some early works discussed contact-time deniability informally, it has received little attention since then. We investigate deniability from a rigorous, theoretical point of view and arrive at the following impossibility result:
A decentralized protocol with unidirectional communication cannot be contact-time deniable and replay-secure. This holds even if malicious users treat smartphones as black-boxes.
 Unidirectional protocols are usually very efficient and many proposals are unidirectional, e.g., the widely-deployed Google-Apple Exposure Notifications. So the impossibility result considerably constrains the design space of efficient, secure, and private ACT protocols. However, it can also be used as a guide; we discuss several possibilities to achieve contact-time deniability in practice.},
  author       = {Günther, Christoph Ullrich and Pietrzak, Krzysztof Z},
  issn         = {2299-0984},
  journal      = {Proceedings on Privacy Enhancing Technologies},
  location     = {Bristol, UK/Virtual},
  number       = {4},
  pages        = {636--648},
  publisher    = {Privacy Enhancing Technologies Symposium Advisory Board},
  title        = {{Deniability in automated contact tracing: Impossibilities and possibilities}},
  doi          = {10.56553/popets-2024-0134},
  volume       = {2024},
  year         = {2024},
}