7 Search Results for "Spooner, Nicholas"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.56
The Hardness of Learning Quantum Circuits and Its Cryptographic Applications

Authors: Bill Fefferman, Soumik Ghosh, Makrand Sinha, and Henry Yuen

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles. Our random circuit-based constructions provide concrete instantiations of quantum cryptographic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to {NISQ-friendly quantum cryptography}. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against {noiseless} quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting.
Cite as

Bill Fefferman, Soumik Ghosh, Makrand Sinha, and Henry Yuen. The Hardness of Learning Quantum Circuits and Its Cryptographic Applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 56:1-56:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fefferman_et_al:LIPIcs.ITCS.2026.56,
  author =	{Fefferman, Bill and Ghosh, Soumik and Sinha, Makrand and Yuen, Henry},
  title =	{{The Hardness of Learning Quantum Circuits and Its Cryptographic Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{56:1--56:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.56},
  URN =		{urn:nbn:de:0030-drops-253431},
  doi =		{10.4230/LIPIcs.ITCS.2026.56},
  annote =	{Keywords: quantum learning, quantum circuits, cryptographic hardness, one-way state generators}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.116
Decentralized Data Archival: New Definitions and Constructions

Authors: Elaine Shi, Rose Silver, and Changrui Mu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We initiate the study of a new abstraction called incremental decentralized data archival (iDDA). Specifically, imagine that there is an ever-growing, massive database such as a blockchain, a comprehensive human knowledge base like Wikipedia, or the Internet archive. We want to build a decentralized archival system for such datasets to ensure long-term robustness and sustainability. We identify several important properties that an iDDA scheme should satisfy. First, to promote heterogeneity and decentralization, we want to encourage even weak nodes with limited space (e.g., users' home computers) to contribute. The minimum space requirement to contribute should be approximately independent of the data size. Second, if a collection of nodes together receive rewards commensurate with contributing a total of m blocks of space, then we want the following reassurances: 1) if m is at least the database size, we should be able to reconstruct the entire dataset; and 2) these nodes should actually be committing roughly m space in aggregate - specifically, when m is much larger than the data size, these nodes cannot store only one copy of the database, and be able to impersonate arbitrarily many pseudonyms and get unbounded rewards. We propose new definitions that mathematically formalize the aforementioned requirements of an iDDA scheme. We also devise an efficient construction in the random oracle model which satisfies the desired security requirements. Our scheme incurs only Õ(1) audit cost, as well as Õ(1) update cost for both the publisher and each node, where Õ(⋅) hides polylogarithmic factors. Further, the minimum space provisioning required to contribute is as small as polylogarithmic. Our construction exposes several interesting technical challenges. Specifically, we show that a straightforward application of the standard hierarchical data structure fails, since both our security definition and the underlying cryptographic primitives we employ lack the desired compositional guarantees. We devise novel techniques to overcome these compositional issues, resulting in a construction with provable security while still retaining efficiency. Finally, our new definitions also make a conceptual contribution, and lay the theoretical groundwork for the study of iDDA. We raise several interesting open problems along this direction.
Cite as

Elaine Shi, Rose Silver, and Changrui Mu. Decentralized Data Archival: New Definitions and Constructions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 116:1-116:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shi_et_al:LIPIcs.ITCS.2026.116,
  author =	{Shi, Elaine and Silver, Rose and Mu, Changrui},
  title =	{{Decentralized Data Archival: New Definitions and Constructions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{116:1--116:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.116},
  URN =		{urn:nbn:de:0030-drops-254037},
  doi =		{10.4230/LIPIcs.ITCS.2026.116},
  annote =	{Keywords: Decentralized Data Archival}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.1
Cache Timing Leakages in Zero-Knowledge Protocols

Authors: Shibam Mukherjee, Christian Rechberger, and Markus Schofnegger

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
The area of modern zero-knowledge proof systems has seen a significant rise in popularity over the last couple of years, with new techniques and optimized constructions emerging on a regular basis. As the field matures, the aspect of implementation attacks becomes more relevant, however side-channel attacks on zero-knowledge proof systems have seen surprisingly little treatment so far. In this paper, we give an overview of potential attack vectors and show that some of the underlying finite field libraries, and implementations of heavily used components like hash functions using them, are vulnerable w.r.t. cache attacks on CPUs. On the positive side, we demonstrate that the computational overhead to protect against these attacks is relatively small.
Cite as

Shibam Mukherjee, Christian Rechberger, and Markus Schofnegger. Cache Timing Leakages in Zero-Knowledge Protocols. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mukherjee_et_al:LIPIcs.AFT.2025.1,
  author =	{Mukherjee, Shibam and Rechberger, Christian and Schofnegger, Markus},
  title =	{{Cache Timing Leakages in Zero-Knowledge Protocols}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{1:1--1:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.1},
  URN =		{urn:nbn:de:0030-drops-247201},
  doi =		{10.4230/LIPIcs.AFT.2025.1},
  annote =	{Keywords: zero-knowledge, protocol, cache timing, side-channel, leakage}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.31
Trustless Bridges via Random Sampling Light Clients

Authors: Bhargav Nagaraja Bhatt, Fatemeh Shirazi, and Alistair Stewart

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
The increasing number of blockchain projects introduced annually has led to a pressing need for secure and efficient interoperability solutions. Currently, the lack of such solutions forces end-users to rely on centralized intermediaries, contradicting the core principle of decentralization and trust minimization in blockchain technology. We propose a decentralized and efficient interoperability solution (aka Bridge Protocol) that operates without additional trust assumptions, relying solely on the Byzantine Fault Tolerance (BFT) properties of the two chains being connected. In particular, relayers (actors that exchange messages between networks) are permissionless and decentralized, hence eliminating any single point of failure. We introduce Random Sampling, a novel technique for on-chain light clients to efficiently follow the history of PoS blockchains by reducing the signature verifications required. Here, the randomness is drawn on-chain, for example, using Ethereum’s RANDAO. We analyze the security of the bridge from a crypto- economic perspective and provide a framework to derive the security parameters. This includes handling subtle concurrency issues and randomness bias in strawman designs. While the protocol is applicable to various PoS chains, we demonstrate the protocol’s practical feasibility by showcasing an instantiated bridge between Polkadot and Ethereum (currently deployed), and discuss some practical security challenges. Furthermore, we evaluate the efficiency of our on-chain light client verifier (implemented as an Ethereum smart contract) against SNARK-based approaches, demonstrating significantly lower gas costs for signature verification - even for validator sets up to 10⁶.
Cite as

Bhargav Nagaraja Bhatt, Fatemeh Shirazi, and Alistair Stewart. Trustless Bridges via Random Sampling Light Clients. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 31:1-31:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhatt_et_al:LIPIcs.AFT.2025.31,
  author =	{Bhatt, Bhargav Nagaraja and Shirazi, Fatemeh and Stewart, Alistair},
  title =	{{Trustless Bridges via Random Sampling Light Clients}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{31:1--31:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.31},
  URN =		{urn:nbn:de:0030-drops-247503},
  doi =		{10.4230/LIPIcs.AFT.2025.31},
  annote =	{Keywords: PoS Blockchains, Trustless Bridges, Light Clients, Decentralised Relayers, RANDAO Bias}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.23
Accumulation Without Homomorphism

Authors: Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, and William Wang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Accumulation schemes are a simple yet powerful primitive that enable highly efficient constructions of incrementally verifiable computation (IVC). Unfortunately, all prior accumulation schemes rely on homomorphic vector commitments whose security is based on public-key assumptions. It is an interesting open question to construct efficient accumulation schemes that avoid the need for such assumptions. In this paper, we answer this question affirmatively by constructing an accumulation scheme from non-homomorphic vector commitments which can be realized from solely symmetric-key assumptions (e.g., Merkle trees). We overcome the need for homomorphisms by instead performing spot-checks over error-correcting encodings of the committed vectors. Unlike prior accumulation schemes, our scheme only supports a bounded number of accumulation steps. We show that such bounded-depth accumulation still suffices to construct proof-carrying data (a generalization of IVC). We also demonstrate several optimizations to our PCD construction which greatly improve concrete efficiency.
Cite as

Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, and William Wang. Accumulation Without Homomorphism. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 23:1-23:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bunz_et_al:LIPIcs.ITCS.2025.23,
  author =	{B\"{u}nz, Benedikt and Mishra, Pratyush and Nguyen, Wilson and Wang, William},
  title =	{{Accumulation Without Homomorphism}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{23:1--23:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.23},
  URN =		{urn:nbn:de:0030-drops-226510},
  doi =		{10.4230/LIPIcs.ITCS.2025.23},
  annote =	{Keywords: Proof-carrying data, incrementally verifiable computation, accumulation schemes}
}
Document
DOI: 10.4230/LIPIcs.TQC.2023.2
On the Necessity of Collapsing for Post-Quantum and Quantum Commitments

Authors: Marcel Dall'Agnol and Nicholas Spooner

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
Collapse binding and collapsing were proposed by Unruh (Eurocrypt '16) as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the "lifting" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting? In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information. As a consequence, we establish that a variety of "weak" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a "win-win" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt '19) showing that the same object yields quantum lightning.
Cite as

Marcel Dall'Agnol and Nicholas Spooner. On the Necessity of Collapsing for Post-Quantum and Quantum Commitments. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dallagnol_et_al:LIPIcs.TQC.2023.2,
  author =	{Dall'Agnol, Marcel and Spooner, Nicholas},
  title =	{{On the Necessity of Collapsing for Post-Quantum and Quantum Commitments}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.2},
  URN =		{urn:nbn:de:0030-drops-183127},
  doi =		{10.4230/LIPIcs.TQC.2023.2},
  annote =	{Keywords: Quantum cryptography, Commitment schemes, Hash functions, Quantum rewinding}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.40
Interactive Oracle Proofs with Constant Rate and Query Complexity

Authors: Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We study interactive oracle proofs (IOPs) [BCS16,RRR16], which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs or IPs alone. Our main results are: 1. Circuit satisfiability has 3-round IOPs with linear proof length (counted in bits) and constant query complexity. 2. Reed-Solomon codes have 2-round IOPs of proximity with linear proof length and constant query complexity. 3. Tensor product codes have 1-round IOPs of proximity with sublinear proof length and constant query complexity. For all the above, known PCP constructions give quasilinear proof length and constant query complexity [BS08,Din07]. Also, for circuit satisfiability, [BKKMS13] obtain PCPs with linear proof length but sublinear (and super-constant) query complexity. As in [BKKMS13], we rely on algebraic-geometry codes to obtain our first result; but, unlike that work, our use of such codes is much "lighter" because we do not rely on any automorphisms of the code. We obtain our results by proving and combining "IOP-analogues" of tools underlying numerous IPs and PCPs: * Interactive proof composition. Proof composition [AS98] is used to reduce the query complexity of PCP verifiers, at the cost of increasing proof length by an additive factor that is exponential in the verifier's randomness complexity. We prove a composition theorem for IOPs where this additive factor is linear. * Sublinear sumcheck. The sumcheck protocol [LFKN92] is an IP that enables the verifier to check the sum of values of a low-degree multi-variate polynomial on an exponentially-large hypercube, but the verifier's running time depends linearly on the bound on individual degrees. We prove a sumcheck protocol for IOPs where this dependence is sublinear (e.g., polylogarithmic). Our work demonstrates that even constant-round IOPs are more efficient than known PCPs and IPs.
Cite as

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Interactive Oracle Proofs with Constant Rate and Query Complexity. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bensasson_et_al:LIPIcs.ICALP.2017.40,
  author =	{Ben-Sasson, Eli and Chiesa, Alessandro and Gabizon, Ariel and Riabzev, Michael and Spooner, Nicholas},
  title =	{{Interactive Oracle Proofs with Constant Rate and Query Complexity}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.40},
  URN =		{urn:nbn:de:0030-drops-74713},
  doi =		{10.4230/LIPIcs.ICALP.2017.40},
  annote =	{Keywords: probabilistically checkable proofs, interactive proofs, proof composition, sumcheck}
}
  • Refine by Type
  • 7 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 3 2025
  • 1 2023
  • 1 2017

  • Refine by Author
  • 2 Spooner, Nicholas
  • 1 Ben-Sasson, Eli
  • 1 Bhatt, Bhargav Nagaraja
  • 1 Bünz, Benedikt
  • 1 Chiesa, Alessandro
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 1 Security and privacy → Cryptography
  • 1 Security and privacy → Distributed systems security
  • 1 Security and privacy → Domain-specific security and privacy architectures
  • 1 Security and privacy → Mathematical foundations of cryptography
  • 1 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 1 Commitment schemes
  • 1 Decentralised Relayers
  • 1 Decentralized Data Archival
  • 1 Hash functions
  • 1 Light Clients
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact