[{"title":"Space-deniable proofs","article_processing_charge":"No","oa_version":"Preprint","author":[{"last_name":"Dujmovic","full_name":"Dujmovic, Jesko","first_name":"Jesko"},{"id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","last_name":"Günther","full_name":"Günther, Christoph Ullrich","first_name":"Christoph Ullrich"},{"last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"}],"year":"2025","OA_place":"repository","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.","date_created":"2025-12-21T23:01:33Z","status":"public","project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509"}],"publication_status":"published","publisher":"Springer Nature","date_published":"2025-12-05T00:00:00Z","language":[{"iso":"eng"}],"scopus_import":"1","day":"05","page":"171-202","type":"conference","conference":{"start_date":"2025-12-01","end_date":"2025-12-05","name":"TCC: Theory of Cryptography","location":"Aarhus, Denmark"},"OA_type":"green","quality_controlled":"1","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>","short":"J. Dujmovic, C.U. Günther, K.Z. Pietrzak, in:, 23rd International Conference on Theory of Cryptography, Springer Nature, 2025, pp. 171–202.","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.","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>","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>.","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>."},"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/1723"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9783032122896"],"issn":["0302-9743"],"eissn":["1611-3349"]},"doi":"10.1007/978-3-032-12290-2_6","corr_author":"1","oa":1,"date_updated":"2025-12-29T11:44:16Z","alternative_title":["LNCS"],"volume":16271,"publication":"23rd International Conference on Theory of Cryptography","department":[{"_id":"KrPi"}],"abstract":[{"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.","lang":"eng"}],"_id":"20844","intvolume":"     16271","month":"12"},{"date_published":"2025-12-05T00:00:00Z","page":"478-511","day":"05","type":"conference","language":[{"iso":"eng"}],"scopus_import":"1","author":[{"last_name":"Brandt","first_name":"Nicholas","full_name":"Brandt, Nicholas"},{"full_name":"Cueto Noval, Miguel","first_name":"Miguel","last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","orcid":"0000-0002-2505-4246"},{"last_name":"Günther","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich"},{"full_name":"Ünal, Akin","first_name":"Akin","last_name":"Ünal","id":"f6b56fb6-dc63-11ee-9dbf-f6780863a85a","orcid":"0000-0002-8929-0221"},{"last_name":"Wohnig","full_name":"Wohnig, Stella","first_name":"Stella"}],"year":"2025","OA_place":"repository","article_processing_charge":"No","title":"Constrained verifiable random functions without obfuscation and friends","oa_version":"Preprint","publication_status":"published","publisher":"Springer Nature","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.","date_created":"2025-12-21T23:01:34Z","status":"public","project":[{"name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1"}],"date_updated":"2025-12-29T11:11:29Z","alternative_title":["LNCS"],"oa":1,"corr_author":"1","_id":"20846","intvolume":"     16271","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."}],"month":"12","volume":16271,"publication":"23rd International Conference on Theory of Cryptography","department":[{"_id":"KrPi"}],"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>","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.","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.","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>","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>.","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>."},"main_file_link":[{"url":"https://eprint.iacr.org/2025/1045","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"green","conference":{"location":"Aarhus, Denmark","name":"TCC: Theory of Cryptography","end_date":"2025-12-05","start_date":"2025-12-01"},"quality_controlled":"1","doi":"10.1007/978-3-032-12290-2_16","publication_identifier":{"isbn":["9783032122896"],"issn":["0302-9743"],"eissn":["1611-3349"]}}]