---
OA_place: repository
OA_type: green
_id: '20846'
abstract:
- lang: eng
  text: "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.\r\nWe 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.\r\nWe 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).\r\nWe 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+.\r\nLast,
    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."
acknowledgement: "We thank Jonas Steinbach and Gertjan De Mulder for helpful discussions
  on BIP 32, Dennis Hofheinz and Julia Kastner for helpful discussions on early prototypes
  of our CVRF, and Klaus Kraßnitzer for running pairing benchmarks on his MacBook
  Pro.\r\nChristoph U. Günther: This research was funded in whole or in part by the
  Austrian Science Fund (FWF) 10.55776/F85. For open access purposes, the author has
  applied a CC BY public copyright license to any author-accepted manuscript version
  arising from this submission."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicholas
  full_name: Brandt, Nicholas
  last_name: Brandt
- first_name: Miguel
  full_name: Cueto Noval, Miguel
  id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
  last_name: Cueto Noval
  orcid: 0000-0002-2505-4246
- first_name: Christoph Ullrich
  full_name: Günther, Christoph Ullrich
  id: ec98511c-eb8e-11eb-b029-edd25d7271a1
  last_name: Günther
- first_name: Akin
  full_name: Ünal, Akin
  id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
  last_name: Ünal
  orcid: 0000-0002-8929-0221
- first_name: Stella
  full_name: Wohnig, Stella
  last_name: Wohnig
citation:
  ama: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. Constrained verifiable
    random functions without obfuscation and friends. In: <i>23rd International Conference
    on Theory of Cryptography</i>. Vol 16271. Springer Nature; 2025:478-511. doi:<a
    href="https://doi.org/10.1007/978-3-032-12290-2_16">10.1007/978-3-032-12290-2_16</a>'
  apa: 'Brandt, N., Cueto Noval, M., Günther, C. U., Ünal, A., &#38; Wohnig, S. (2025).
    Constrained verifiable random functions without obfuscation and friends. In <i>23rd
    International Conference on Theory of Cryptography</i> (Vol. 16271, pp. 478–511).
    Aarhus, Denmark: Springer Nature. <a href="https://doi.org/10.1007/978-3-032-12290-2_16">https://doi.org/10.1007/978-3-032-12290-2_16</a>'
  chicago: Brandt, Nicholas, Miguel Cueto Noval, Christoph Ullrich Günther, Akin Ünal,
    and Stella Wohnig. “Constrained Verifiable Random Functions without Obfuscation
    and Friends.” In <i>23rd International Conference on Theory of Cryptography</i>,
    16271:478–511. Springer Nature, 2025. <a href="https://doi.org/10.1007/978-3-032-12290-2_16">https://doi.org/10.1007/978-3-032-12290-2_16</a>.
  ieee: N. Brandt, M. Cueto Noval, C. U. Günther, A. Ünal, and S. Wohnig, “Constrained
    verifiable random functions without obfuscation and friends,” in <i>23rd International
    Conference on Theory of Cryptography</i>, Aarhus, Denmark, 2025, vol. 16271, pp.
    478–511.
  ista: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. 2025. Constrained
    verifiable random functions without obfuscation and friends. 23rd International
    Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol.
    16271, 478–511.'
  mla: Brandt, Nicholas, et al. “Constrained Verifiable Random Functions without Obfuscation
    and Friends.” <i>23rd International Conference on Theory of Cryptography</i>,
    vol. 16271, Springer Nature, 2025, pp. 478–511, doi:<a href="https://doi.org/10.1007/978-3-032-12290-2_16">10.1007/978-3-032-12290-2_16</a>.
  short: N. Brandt, M. Cueto Noval, C.U. Günther, A. Ünal, S. Wohnig, in:, 23rd International
    Conference on Theory of Cryptography, Springer Nature, 2025, pp. 478–511.
conference:
  end_date: 2025-12-05
  location: Aarhus, Denmark
  name: 'TCC: Theory of Cryptography'
  start_date: 2025-12-01
corr_author: '1'
date_created: 2025-12-21T23:01:34Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:11:29Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_16
fulldoi: https://doi.org/10.1007/978-3-032-12290-2_16
intvolume: '     16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2025/1045
month: '12'
oa: 1
oa_version: Preprint
page: 478-511
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
  grant_number: F8509
  name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783032122896'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constrained verifiable random functions without obfuscation and friends
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20844'
abstract:
- lang: eng
  text: "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.\r\nAn 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.\r\nWe
    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."
acknowledgement: "Jesko Dujmovic: Funded by the European Union (ERC, LACONIC, 101041207).
  Views and opinions expressed are however those of the author(s) only and do not
  necessarily reflect those of the European Union or the European Research Council.
  Neither the European Union nor the granting authority can be held responsible for
  them.\r\nChristoph U. Günther and Krzysztof Pietrzak: This research was funded in
  whole or in part by the Austrian Science Fund (FWF) 10.55776/F85. For open access
  purposes, the author has applied a CC BY public copyright license to any author-accepted
  manuscript version arising from this submission."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Jesko
  full_name: Dujmovic, Jesko
  last_name: Dujmovic
- first_name: Christoph Ullrich
  full_name: Günther, Christoph Ullrich
  id: ec98511c-eb8e-11eb-b029-edd25d7271a1
  last_name: Günther
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Dujmovic J, Günther CU, Pietrzak KZ. Space-deniable proofs. In: <i>23rd International
    Conference on Theory of Cryptography</i>. Vol 16271. Springer Nature; 2025:171-202.
    doi:<a href="https://doi.org/10.1007/978-3-032-12290-2_6">10.1007/978-3-032-12290-2_6</a>'
  apa: 'Dujmovic, J., Günther, C. U., &#38; Pietrzak, K. Z. (2025). Space-deniable
    proofs. In <i>23rd International Conference on Theory of Cryptography</i> (Vol.
    16271, pp. 171–202). Aarhus, Denmark: Springer Nature. <a href="https://doi.org/10.1007/978-3-032-12290-2_6">https://doi.org/10.1007/978-3-032-12290-2_6</a>'
  chicago: Dujmovic, Jesko, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Space-Deniable
    Proofs.” In <i>23rd International Conference on Theory of Cryptography</i>, 16271:171–202.
    Springer Nature, 2025. <a href="https://doi.org/10.1007/978-3-032-12290-2_6">https://doi.org/10.1007/978-3-032-12290-2_6</a>.
  ieee: J. Dujmovic, C. U. Günther, and K. Z. Pietrzak, “Space-deniable proofs,” in
    <i>23rd International Conference on Theory of Cryptography</i>, Aarhus, Denmark,
    2025, vol. 16271, pp. 171–202.
  ista: 'Dujmovic J, Günther CU, Pietrzak KZ. 2025. Space-deniable proofs. 23rd International
    Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol.
    16271, 171–202.'
  mla: Dujmovic, Jesko, et al. “Space-Deniable Proofs.” <i>23rd International Conference
    on Theory of Cryptography</i>, vol. 16271, Springer Nature, 2025, pp. 171–202,
    doi:<a href="https://doi.org/10.1007/978-3-032-12290-2_6">10.1007/978-3-032-12290-2_6</a>.
  short: J. Dujmovic, C.U. Günther, K.Z. Pietrzak, in:, 23rd International Conference
    on Theory of Cryptography, Springer Nature, 2025, pp. 171–202.
conference:
  end_date: 2025-12-05
  location: Aarhus, Denmark
  name: 'TCC: Theory of Cryptography'
  start_date: 2025-12-01
corr_author: '1'
cryptoeprintid: 1
das_tickbox: '1'
date_created: 2025-12-21T23:01:33Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2026-07-21T09:17:38Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_6
external_id:
  cryptoeprintid:
  - 2025/1723
fulldoi: https://doi.org/10.1007/978-3-032-12290-2_6
intvolume: '     16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2025/1723
month: '12'
oa: 1
oa_version: Preprint
page: 171-202
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
  grant_number: F8509
  name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783032122896'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Space-deniable proofs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...