Pith. sign in

REVIEW 3 major objections 3 minor 67 references

On One-Shot Signatures, Quantum vs Classical Binding, and Obfuscating Permutations

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper constructs the first one-shot signature schemes with provable security in the standard model, resolving an open problem left by a retracted construction.

desk verdict Major paper that likely resolves the OSS open problem and introduces a genuinely new iO technique, but the current draft has a load-bearing gap around the sparse trigger and omits the formal proofs. read the letter →

arxiv 2507.12456 v1 pith:MJAWQPZH submitted 2025-07-16 cs.CR quant-ph

Omri Shmueli , Mark Zhandry This is my paper · ORCID
classification cs.CRquant-ph MSC 94A6068Q1281P94
keywords one-shotsignaturesquantumcryptographyindistinguishabilityobfuscationpermutablepseudorandompermutationsnon-collapsinghashfunctionscollapse-bindingcommitmentstrapdoorone-waylearningwitherrors
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

One-shot signatures let a signer authenticate exactly one message: producing the signature provably destroys the signing key, so a second signature is impossible even for the signer. Classically such schemes cannot exist, and the only known quantum candidate rested on a security proof that later turned out to contain a fatal bug, leaving the question open for a decade. This paper establishes that secure one-shot signatures do exist relative to a classical oracle, with unconditional security, and—as the main result—in the standard model under subexponential indistinguishability obfuscation, subexponential one-way functions, and polynomial-time LWE with subexponential noise-modulus ratio. The same construction yields the first standard-model separation between classical binding and the stronger collapse-binding notion for post-quantum commitments and hashing, along with full-domain trapdoor one-way permutations from iO as a byproduct. This matters because one-shot signatures are the missing ingredient for schemes such as decentralized currency without a blockchain and quantum money sent over purely classical channels.

What carries the argument

The load-bearing object is the permutable pseudorandom permutation (permutable PRP): a PRP family for which, given a key $k$ and a known permutation $\Gamma$, one can produce a permuted key $k_\Gamma$ that evaluates $\Gamma(\Pi(k,\cdot))$ and its inverse, while the key hides which permutation was applied. This supplies the permutation analogue of puncturable programming, so obfuscating a permutable PRP translates oracle proofs that use a random permutation into obfuscation-based proofs. The construction starts from the recursive merge-based permutation of [GP07], randomizes the merge choices with a puncturable PRF, and realizes a single neighbor swap by puncturing the PRF at the two swapped leaves and their paths to the root; arbitrary decomposable permutations are reached one neighbor swap at a time through an exponential hybrid. The other half of the machinery is the reduction chain for the hash: random self-reducibility re-randomizes instances, dual-bloating (subspace hiding) hides the hidden subspace inside a random superspace, the dual oracle is simulated and eliminated, and collision-finding is finally reduced to the known quantum lower bound for random 2-to-1 functions [AS04, Zha15].

What would settle it

Three concrete checks would settle the central claims. For the oracle theorem, give a quantum adversary superposition access to the paper's hash, inverse, and dual-subspace oracles and see whether it finds a collision: any such algorithm falsifies Theorem 1. For the standard-model theorem, instantiate the LWE-based 2-to-1 trapdoor hash and measure the fraction of inputs on which it is one-to-one; if that fraction is polynomially large rather than exponentially small, the sparse-trigger hybrid in the proof of Theorem 3 fails. At the primitive level, test permutable-PRP security directly: a distinguisher that receives obfuscations of $\Pi(k,\cdot)$ and of the neighbor-swap-composed $\Gamma(\Pi(k,\cdot))$ for a single adjacent transposition $\Gamma$ and tells them apart with non-negligible advantage would falsify the security that Theorems 5 and 6 rest on.

Watch

Extended reading notes

Core claim

The central claim is that one-shot signatures exist, both unconditionally relative to a classical oracle and in the standard model from subexponential indistinguishability obfuscation, subexponential one-way functions, and LWE with a subexponential noise-modulus ratio. The route is to build, under the same conditions, a hash function that is collision-resistant against quantum adversaries yet non-collapsing: a quantum state that passes the hash-based verification necessarily collapses onto a single output, and a non-collapsing collision-resistant hash yields a one-shot signature by using the preimage superposition as the signing key. For the oracle construction the proof is a chain of reductions driven by random self-reducibility: the full set of oracles (hash, inverse, and dual-subspace membership) is re-randomized into fresh instances, the dual oracle is bloated to a random superspace and then simulated away, and the remaining collision problem is shown to be exactly as hard as collision-finding in a random 2-to-1 function. For the standard model the random permutation is replaced by the paper's new primitive, the permutable PRP, whose permuted keys let an obfuscated program evaluate any decomposable permutation composed with the PRP without revealing it; the random 2-to-1 function is replaced by an LWE-based trapdoor hash that is 2-to-1 except on a sparse set of bad points, which the proof handles by inserting a sparse trigger into the obfuscated program.

Load-bearing premise

The standard-model proof assumes a lattice-based collision-resistant hash that is exactly two-to-one except on a negligible fraction of inputs and whose internal stages each behave as a reversible permutation; if no such hash exists, or the set of exceptional points is not sparse enough, the obfuscation-based reduction that embeds the coset function breaks and the standard-model one-shot signature collapses.

Editorial extensions

If this is right

  • One-shot signatures now have a provable standard-model instantiation, the first such scheme whose security rests on widely studied assumptions (subexponential iO, subexponential one-way functions, LWE) rather than on new bespoke hardness assumptions.
  • Classical binding and quantum collision resistance provably do not imply collapse-binding for post-quantum hashing and commitments without relativization, settling a separation question that has been open since collapse-binding was introduced.
  • Full-domain trapdoor one-way permutations exist from subexponential iO and one-way functions, giving the first provably secure obfuscation of a pseudorandom permutation; plugging them into an existing proof-of-quantumness template yields the first proof of quantumness from iO.
  • The classical-oracle theorems give the first unconditionally secure quantum lightning, one-shot signatures, and classical-versus-collapse-binding separation relative to a classical oracle, upgrading what was previously only plausible.
  • Permutable PRPs are the first provable PRP analogue of puncturable pseudorandom functions, giving iO-based proofs a replacement for random permutations of the kind the oracle construction had used for free.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If permutable PRPs prove as reusable as puncturable PRFs have been, other oracle-to-standard-model translations that stall on random permutations—such as public-key quantum money constructions—may now go through; the paper itself only points at this possibility for future work.
  • The paper's Efficient Permutation Decomposition question doubles as a stress test for the technique: any efficiently computable permutation family that provably resists decomposition with small partial circuits would mark the exact boundary of what this permutable-PRP construction can obfuscate.
  • A testable extension is to swap the LWE-based trapdoor hash for other two-to-one trapdoor candidates, such as group-action or isogeny constructions; the paper notes the trigger step needs the exceptional one-to-one points to be exponentially sparse, so any such replacement must engineer that sparsity before the proof transfers.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The manuscript claims the first standard-model one-shot signature scheme, along with oracle-model constructions and a new notion of permutable pseudorandom permutations. The oracle construction hashes through a secret random permutation with coset/dual structure, and the proof is outlined as a sequence of random self-reductions that ultimately reduces collision-finding to the known lower bound for 2-to-1 random functions. The standard-model construction replaces the random permutation with a permutable PRP and embeds an LWE-based trapdoor 2-to-1 hash, using a sparse-trigger lemma to repair the hash's 1-to-1 points. The version under review contains the introduction, a detailed technical overview, and the cryptographic tools in Section 3, but Sections 4-6 are present only as section and subsection headings.

Significance. If the omitted proofs are completed and correct, Theorem 3 would resolve the long-standing open problem of standard-model one-shot signatures under iO and LWE, and Theorem 6 would give the first full-domain trapdoor one-way permutation from iO and one-way functions, with a proof of quantumness as a corollary. The paper's oracle proof strategy is a genuine conceptual advance: it avoids the known AGKZ20 inner-product adversary bug by reducing to the established collision lower bound for 2-to-1 functions, and the random self-reduction ideas are promising. The permutable PRP notion is a natural and potentially useful analogue of puncturable PRFs. These strengths are significant, but they cannot be converted into verified results from the text provided, because the formal proof sections are missing and because the sparse-trigger step that is load-bearing for the standard-model theorem is not established for the actual LWE bad set.

major comments (3)
  1. [Sections 4-6] In the text made available for review, Sections 4, 5, and 6 consist of theorem statements and subsection headings only; the proof bodies are absent. Theorems 1, 2, 3, 4, 5, and 6 therefore cannot be checked from the provided material. This is not a presentation issue but the central content of the paper. The authors should supply the full proofs in these sections, or state clearly that they are available in a complete version, before the central claims can be evaluated.
  2. [Section 2.4, Lemma 43] The proof of Theorem 3 depends on a sparse-trigger step whose hypotheses are not shown to hold for the actual bad set of the LWE-based hash. The text says that the LWE function L is 2-to-1 except on a sparse set and that a trigger is added at all sparse 'bad' 1-to-1 points, then refers to Lemma 43 for interval triggers 'with some other technical conditions' and says the extension requires 'a bit more work'. No argument is given that the bad set of an LWE syndrome map is an interval, or a polynomial union of intervals, in the encoding on which the permutable PRPs act. If that condition fails, the two programs in the iO hybrid are not functionally equivalent on every input, and the proof of Theorem 3 collapses at this step. Please state Lemma 43 precisely and prove that the LWE construction's bad set satisfies its hypotheses.
  3. [Section 2.4, Section 6.3] The standard-model construction requires a post-quantum collision-resistant 2-to-1 hash L that has a trapdoor, is 2-to-1 on all but a sparse set, and whose evaluation can be split into decomposable permutation stages. The overview says this follows 'following a similar approach' to claw-free trapdoor functions from LWE, but gives no construction and no proof of these properties. These properties are load-bearing: they are needed to hard-code an implicit permutation with a small circuit into the obfuscated program in the hybrid argument, and to invoke permutable-PRP security on the individual stages. The construction and its verifiable properties should be provided in full.
minor comments (3)
  1. [Throughout] There are several typos and spacing artifacts, including 'T echnical Overview', 'L WE', 'W arm-up', and 'indisitnguishability' in the Section 5.1 heading; please proofread the text.
  2. [Definition 10] The displayed statistical-distance expression in Definition 10 is typeset in a way that obscures the absolute values; please restore the standard notation so the two probabilities being compared are unambiguous.
  3. [Section 2.3, Figure 5] The entry for 'Permutations with ancillas' says the permutation (x, 0^n) -> (Gamma(x), 0^n) is 'only a partial function that is not specified on the rest of the domain', but the surrounding text says the permutable PRP domain is the entire space including ancillas; please clarify how the partial specification is completed to a total permutation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the standard-model OSS derivation chains to external assumptions (iO, OWFs, LWE) and prior independent lemmas; the flagged sparse-trigger step is a proof gap, not a circular reduction.

full rationale

The paper's claimed derivation chain is a sequence of reductions and constructions: OSS is obtained from a collision-resistant always-non-collapsing hash (using the known implication of [AGKZ20, DS23]); that hash is built from a coset-partition function; in the standard model the random permutation is replaced by permutable PRPs, which are constructed from puncturable PRFs and the [GP07] tree-based permutation under sub-exponential iO and OWFs; the final ingredient is an LWE-based trapdoor 2-to-1 hash. Each load-bearing step either invokes external results with explicitly stated assumptions or is proved in the text. The strengthening of Lemma 5.1 from [Shm22b] (Lemma 26) is not imported by citation alone: the paper gives the proof of the strengthened statement. Lemma 23 from [Zha19] is used as a forward-cited theorem with stated iO/OWF assumptions and does not itself contain the OSS conclusion, so it is independent evidence rather than a circular premise. The most serious flagged issue is in Section 2.4: the 'sparse bad points' of the LWE hash are repaired by adding a trigger, and the text says this works 'as long as the fixed trigger is sandwiched between two permutable PRPs ... and meets some other technical conditions' and then invokes Lemma 43. The paper does not verify that the actual bad set of the LWE hash satisfies the interval condition or the 'other technical conditions'. That is a real correctness risk and an omitted-support gap, but it is not circularity: the construction does not define the LWE hash, the trigger, or the obfuscated programs in terms of the OSS security claim, and no parameter is fitted to the target result. The absence of the formal Sections 4-6 in the review text is also a completeness gap, not evidence that the derivation reduces to its own inputs. No equation or theorem in the available text is equivalent to its input by construction, no fitted value is renamed as a prediction, and no uniqueness or ansatz is imported solely from the authors' prior work as a substitute for proof.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

The central claim rests on the stated sub-exponential assumptions (iO, OWFs, LWE) and on several known cryptographic theorems (puncturable PRFs, injective OWFs from iO, collision lower bounds). Permutable PRPs are a new primitive, but they come with their own reduction, not an unexplained postulate.

assumptions (6)
  • domain assumption Existence of sub-exponentially secure indistinguishability obfuscation (iO).
    Theorems 3-6 assume sub-exponentially-secure iO; no construction of iO from weaker assumptions is known.
  • domain assumption Existence of sub-exponentially secure one-way functions.
    Needed for puncturable PRFs, injective OWFs from iO, and the permutable PRP construction.
  • domain assumption Polynomially-secure LWE with sub-exponential noise-modulus ratio.
    Used to build the trapdoor 2-to-1 collision-resistant hash Q required by the standard-model OSS proof.
  • standard math Known collision lower bound for random 2-to-1 functions (AS04, Zha15).
    Oracle-model security ultimately reduces to this bound; the paper does not prove it.
  • standard math Puncturable PRFs exist from one-way functions (KPTZ13, BW13, BGI14).
    Used to generate tally-tree randomness and for punctured programming steps.
  • standard math Injective one-way functions can be built from iO and OWFs (BPW16).
    Invoked in Lemmas 17 and 23 to justify sparse random triggers and subspace-hiding.
invented entities (2)
  • Permutable PRP
    purpose: A PRP whose key can be permuted to compute Gamma composed with Pi while hiding the applied permutation; it replaces puncturable PRFs for PRPs and enables iO proofs with permutations.
    New primitive introduced in Section 5. It is a defined game with a concrete construction, not an unexplained postulate, but its only evidence is the security proof within this paper.
  • Tally tree
    purpose: Data structure for evaluating the GP-style merge operation in permutable PRPs and for sampling random permutations with small keys.
    Internal algorithmic tool; no external falsifiable prediction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On One-Shot Signatures, Quantum vs Classical Binding, and Obfuscating Permutations." pith.science (2026). https://pith.science/paper/MJAWQPZH

@misc{pith2026250712456,
  author       = {Pith},
  title        = {Pith review of: On One-Shot Signatures, Quantum vs Classical Binding, and Obfuscating Permutations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MJAWQPZH}},
  note         = {Machine review of arXiv:2507.12456}
}
read the original abstract

One-shot signatures (OSS) were defined by Amos, Georgiou, Kiayias, and Zhandry (STOC'20). These allow for signing exactly one message, after which the signing key self-destructs, preventing a second message from ever being signed. While such an object is impossible classically, Amos et al observe that OSS may be possible using quantum signing keys by leveraging the no-cloning principle. OSS has since become an important conceptual tool with many applications in decentralized settings and for quantum cryptography with classical communication. OSS are also closely related to separations between classical-binding and collapse-binding for post-quantum hashing and commitments. Unfortunately, the only known OSS construction due to Amos et al. was only justified in a classical oracle model, and moreover their justification was ultimately found to contain a fatal bug. Thus, the existence of OSS, even in a classical idealized model, has remained open. We give the first standard-model OSS, with provable security assuming (sub-exponential) indistinguishability obfuscation (iO) and LWE. This also gives the first standard-model separation between classical and collapse-binding post-quantum commitments/hashing, solving a decade-old open problem. Along the way, we also give the first construction with unconditional security relative to a classical oracle. To achieve our standard-model construction, we develop a notion of permutable pseudorandom permutations (permutable PRPs), and show how they are useful for translating oracle proofs involving random permutations into obfuscation-based proofs. In particular, obfuscating permutable PRPs gives a trapdoor one-way permutation that is \emph{full-domain}, solving another decade-old-problem of constructing this object from (sub-exponential) iO and one-way functions.

Figures

Figures reproduced from arXiv: 2507.12456 by the authors.

Figure 1
Figure 1. The PRP construction Π(k, ·) of [GP07]. There are 2n input nodes on the bottom, one per input, and 2n output nodes. The left and right halves correspond to inputs starting with 0 and 1 respectively. Here, k0, k1, k2 are keys pseudorandomly derived from k. Then M (k2, ·) is a pseudorandom object we call a Merge which preserves the order of each half but otherwise pseudorandomly scrambles them. Π (k0, ·) and Π (k1, ·)… view at source ↗
Figure 2
Figure 2. A merge M and the associated tally tree T, for the case N0 = N1 = 8, N = 16. permutation uniquely corresponds to a triple containing a merge (determining the interleaving) and two recursive permutations. Thus this process perfectly simulates a random permutation. See [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Our permuting algorithm. Here, k (z z+1),c means the permuted key, where c = 0 means no swapping occurs, and c = 1 means z and z + 1 are swapped. Red squares indicate the points z, z + 1, red solid arrows indicate the original permutation (c = 0), and blue dashed lines indicate the permuted permutation (c = 1). Let y0, y1 be the pre-images of z, z + 1 in the Merge.Left: The case where y0, y1 lie in different halves,… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Left: The tally tree for a permuted merge key [PITH_FULL_IMAGE:figures/full_fig_p022_4.png]
Figure 5
Figure 5. Figure 5: A non-exhaustive list of decomposable permutations. Note that for conju [PITH_FULL_IMAGE:figures/full_fig_p023_5.png]
Figure 6
Figure 6. Figure 6: The program P that gets obfuscated to give the program P. The programs P −1 , D are defined accordingly. Here, Π, Π−1 is a permutable PRP, and F is a punc￾turable pseudorandom function. The output of H is r bits, z is n − r bits, and y is d bits. There are, however, tw…
Figure 7
Figure 7. Figure 7: The original program P (top) and triggered program P ′ (bottom). Here, P0, P1, P′ 1 , P2 are arbitrary programs as long as they are independent of the keys k0, k1. Our indistinguishability result shows that for the case where R(x2) tests if x2 (or some component thereo…
Figure 8
Figure 8. Figure 8: The obfuscated program P in Hybrid 0. We simply apply Q to the output w of Π (kin, ·). The output u is set to a pseudorandomly-generated affine function of w. Here, the public key pk for Q is sampled together with a trapdoor td. The change we make to the following hybr…
Figure 9
Figure 9. Figure 9: The obfuscated program P in Hybrid 2. The output w of Π (kin, ·) is still the input to Q. However, instead of generating the output vector u as a function of w, it is a pseudorandomly-generated affine function of z, the last n − r bits of w. Note that in the first dist…
Figure 10
Figure 10. Figure 10: The obfuscated program P in Hybrid 3. We insert the program C instead of the original circuit for Q, which was used in Hybrid 2. There are 4 steps to the computation of C: 1 is the permutation π, 2 is the correction signal, 3 and 4 are the injective functions τ and γ,…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

67 extracted references · 67 canonical work pages

  1. [1]

    Aaronson

    S. Aaronson. Quantum certificate complexity. In 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings. , pages 171--178, 2003

    work page 2003

  2. [2]

    Quantum copy-protection and quantum money

    Scott Aaronson. Quantum copy-protection and quantum money. In Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity , CCC '09, page 229–242, USA, 2009. IEEE Computer Society

    work page 2009

  3. [3]

    Quantum money from hidden subspaces

    Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. In Howard J. Karloff and Toniann Pitassi, editors, 44th Annual ACM Symposium on Theory of Computing , pages 41--60, New York, NY, USA, May 19--22, 2012. ACM Press

    work page 2012

  4. [4]

    One-shot signatures and applications to hybrid quantum/classical authentication

    Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. One-shot signatures and applications to hybrid quantum/classical authentication. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd Annual ACM Symposium on Theory of Computing , pages 255--268, Chicago, IL, USA, June 22--26, 2020. ACM Press

    work page 2020

  5. [5]

    Pseudorandom (function-like) quantum state generators: New definitions and applications

    Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. Pseudorandom (function-like) quantum state generators: New definitions and applications. In Theory of Cryptography Conference , pages 237--265. Springer, 2022

    work page 2022

  6. [6]

    Candidate trapdoor claw-free functions from group actions with applications to quantum protocols

    Navid Alamati, Giulio Malavolta, and Ahmadreza Rahimi. Candidate trapdoor claw-free functions from group actions with applications to quantum protocols. In Theory of Cryptography Conference , pages 266--293. Springer, 2022

    work page 2022

  7. [7]

    Quantum attacks on classical proof systems: The hardness of quantum rewinding

    Andris Ambainis, Ansis Rosmanis, and Dominique Unruh. Quantum attacks on classical proof systems: The hardness of quantum rewinding. In 55th Annual Symposium on Foundations of Computer Science , pages 474--483, Philadelphia, PA, USA, October 18--21, 2014. IEEE Computer Society Press

    work page 2014

  8. [8]

    Quantum lower bounds for the collision and the element distinctness problems

    Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. J. ACM , 51(4):595–605, July 2004

    work page 2004

Show all 67 references
  1. [9]

    Limits on the power of indistinguishability obfuscation and functional encryption

    Gilad Asharov and Gil Segev. Limits on the power of indistinguishability obfuscation and functional encryption. In Venkatesan Guruswami, editor, 56th Annual Symposium on Foundations of Computer Science , pages 191--209, Berkeley, CA, USA, October 17--20, 2015. IEEE Computer So...

    2015

  2. [10]

    On constructing one-way permutations from indistinguishability obfuscation

    Gilad Asharov and Gil Segev. On constructing one-way permutations from indistinguishability obfuscation. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part II , volume 9563 of Lecture Notes in Computer Science , pages 512--541...

    2016

  3. [11]

    Explicit bounds for primality testing and related problems

    Eric Bach. Explicit bounds for primality testing and related problems. Mathematics of Computation , 55:355--380, 1990

    1990

  4. [12]

    Personal communication, and also announced at the ntt research quantum money workshop, 2023

    James Bartusek. Personal communication, and also announced at the ntt research quantum money workshop, 2023

    2023

  5. [13]

    Vazirani, and Thomas Vidick

    Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. In Mikkel Thorup, editor, 59th Annual Symposium on Foundations of Computer Science , pages 320--...

    2018

  6. [14]

    Vadhan, and Ke Yang

    Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Joe Kilian, editor, Advances in Cryptology -- CRYPTO 2001 , volume 2139 of Lecture Notes in Computer Science , pages 1--...

    2001

  7. [15]

    Functional signatures and pseudorandom functions

    Elette Boyle, Shafi Goldwasser, and Ioana Ivan. Functional signatures and pseudorandom functions. In Hugo Krawczyk, editor, PKC 2014: 17th International Conference on Theory and Practice of Public Key Cryptography , volume 8383 of Lecture Notes in Computer Science , pages 501-...

    2014

  8. [16]

    Software with certified deletion

    James Bartusek, Vipul Goyal, Dakshita Khurana, Giulio Malavolta, Justin Raizes, and Bhaskar Roberts. Software with certified deletion. In Marc Joye and Gregor Leander, editors, Advances in Cryptology -- EUROCRYPT 2024, Part IV , volume 14654 of Lecture Notes in Computer Scienc...

    2024

  9. [17]

    Cryptography with certified deletion

    James Bartusek and Dakshita Khurana. Cryptography with certified deletion. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology -- CRYPTO 2023, Part V , volume 14085 of Lecture Notes in Computer Science , pages 192--223, Santa Barbara, CA, USA, August 20--...

    2023

  10. [18]

    Publicly-verifiable deletion via target-collapsing functions

    James Bartusek, Dakshita Khurana, and Alexander Poremba. Publicly-verifiable deletion via target-collapsing functions. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology -- CRYPTO 2023, Part V , volume 14085 of Lecture Notes in Computer Science , pages 9...

    2023

  11. [19]

    Dan Boneh, Sam Kim, and David J. Wu. Constrained keys for invertible pseudorandom functions. In Yael Kalai and Leonid Reyzin, editors, TCC 2017: 15th Theory of Cryptography Conference, Part I , volume 10677 of Lecture Notes in Computer Science , pages 237--263, Baltimore, MD, ...

    2017

  12. [20]

    Worst-case hardness for LPN and cryptographic hashing via code smoothing

    Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, and Daniel Wichs. Worst-case hardness for LPN and cryptographic hashing via code smoothing. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology -- EUROCRYPT 2019, Part III , volume 11478 of Lecture Notes...

    2019

  13. [21]

    Perfect structure on the edge of chaos - trapdoor permutations from indistinguishability obfuscation

    Nir Bitansky, Omer Paneth, and Daniel Wichs. Perfect structure on the edge of chaos - trapdoor permutations from indistinguishability obfuscation. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part I , volume 9562 of Lecture N...

    2016

  14. [22]

    Constrained pseudorandom functions and their applications

    Dan Boneh and Brent Waters. Constrained pseudorandom functions and their applications. In Kazue Sako and Palash Sarkar, editors, Advances in Cryptology -- ASIACRYPT 2013, Part II , volume 8270 of Lecture Notes in Computer Science , pages 280--300, Bengalore, India, December 1-...

    2013

  15. [23]

    Certifying trapdoor permutations, revisited

    Ran Canetti and Amit Lichtenberg. Certifying trapdoor permutations, revisited. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018: 16th Theory of Cryptography Conference, Part I , volume 11239 of Lecture Notes in Computer Science , pages 476--506, Panaji, India, November...

    2018

  16. [24]

    Charles, Kristin E

    Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren. Cryptographic hash functions from expander graphs. Journal of Cryptology , 22(1):93--113, 2009

    2009

  17. [25]

    Obfuscation of probabilistic circuits and applications

    Ran Canetti, Huijia Lin, Stefano Tessaro, and Vinod Vaikuntanathan. Obfuscation of probabilistic circuits and applications. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015: 12th Theory of Cryptography Conference, Part II , volume 9015 of Lecture Notes in Computer ...

    2015

  18. [26]

    A quantum money solution to the blockchain scalability problem

    Andrea Coladangelo and Or Sattath. A quantum money solution to the blockchain scalability problem. Quantum , 4:297, 2020

    2020

  19. [27]

    Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory , 22(6):644--654, 1976

    1976

  20. [28]

    One-shot signatures

    Justin Drake. One-shot signatures. talk given at the programmable cryptography conference progcrypto, 2023. https://www.youtube.com/watch?v=VmqkH3NPG_s

    2023

  21. [29]

    On the Necessity of Collapsing for Post-Quantum and Quantum Commitments

    Marcel Dall'Agnol and Nicholas Spooner. On the Necessity of Collapsing for Post-Quantum and Quantum Commitments . In Omar Fawzi and Michael Walter, editors, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023) , volume 266 of Leibniz ...

    2023

  22. [30]

    Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter W. Shor. Quantum money from knots. In Shafi Goldwasser, editor, ITCS 2012: 3rd Innovations in Theoretical Computer Science , pages 276--289, Cambridge, MA, USA, January 8--10, 2012. Association for Com...

    2012

  23. [31]

    Candidate indistinguishability obfuscation and functional encryption for all circuits

    Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In 54th Annual Symposium on Foundations of Computer Science , pages 40--49, Berkeley, CA, USA, October ...

    2013

  24. [32]

    Perfect block ciphers with small blocks

    Louis Granboulan and Thomas Pornin. Perfect block ciphers with small blocks. In Alex Biryukov, editor, Fast Software Encryption -- FSE 2007 , volume 4593 of Lecture Notes in Computer Science , pages 452--465, Luxembourg, Luxembourg, March 26--28, 2007. Springer Berlin Heidelbe...

    2007

  25. [33]

    Breaking the sub-exponential barrier in obfustopia

    Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan, and Mark Zhandry. Breaking the sub-exponential barrier in obfustopia. In Jean-S \' e bastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology -- EUROCRYPT 2017, Part III , volume 10212 of Lecture Notes in Compute...

    2017

  26. [34]

    Rothblum

    Oded Goldreich and Ron D. Rothblum. Enhancements of trapdoor permutations. Journal of Cryptology , 26(3):484--512, 2013

    2013

  27. [35]

    An enciphering scheme based on a card shuffle

    Viet Tung Hoang, Ben Morris, and Phillip Rogaway. An enciphering scheme based on a card shuffle. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology -- CRYPTO 2012 , volume 7417 of Lecture Notes in Computer Science , pages 1--13, Santa Barbara, CA, USA, A...

    2012

  28. [36]

    Plinko: Single-server PIR with efficient updates via invertible PRFs

    Alexander Hoover, Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. Plinko: Single-server PIR with efficient updates via invertible PRFs . Cryptology ePrint Archive, Report 2024/318, 2024

    2024

  29. [37]

    Publicly verifiable deletion from minimal assumptions

    Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. Publicly verifiable deletion from minimal assumptions. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023: 21st Theory of Cryptography Conference, Part IV , volume 14372 of Lecture Notes in Computer Science , pages 228--...

    2023

  30. [38]

    Delegatable pseudorandom functions and applications

    Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. Delegatable pseudorandom functions and applications. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013: 20th Conference on Computer and Communications Security , pages...

    2013

  31. [39]

    Kane, Shahed Sharif, and Alice Silverberg

    Daniel M. Kane, Shahed Sharif, and Alice Silverberg. Quantum money from quaternion algebras. Mathematical Cryptology , 2(1):60–83, Oct. 2022

    2022

  32. [40]

    Breaking and making quantum money: toward a new quantum cryptographic protocol, 2009

    Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan Kelner, and Peter Shor. Breaking and making quantum money: toward a new quantum cryptographic protocol, 2009

    2009

  33. [41]

    Beating classical impossibility of position verification

    Jiahui Liu, Qipeng Liu, and Luowen Qian. Beating classical impossibility of position verification. In Mark Braverman, editor, ITCS 2022: 13th Innovations in Theoretical Computer Science Conference , volume 215, pages 100:1--100:11, Berkeley, CA, USA, January 31 -- February 3, ...

    2022

  34. [42]

    Another round of breaking and making quantum money: How to not build it from lattices, and more

    Jiahui Liu, Hart Montgomery, and Mark Zhandry. Another round of breaking and making quantum money: How to not build it from lattices, and more. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology -- EUROCRYPT 2023, Part I , volume 14004 of Lecture Notes in Comput...

    2023

  35. [43]

    The mixing time of the Thorp shuffle

    Ben Morris. The mixing time of the Thorp shuffle. In Harold N. Gabow and Ronald Fagin, editors, 37th Annual ACM Symposium on Theory of Computing , pages 403--412, Baltimore, MA, USA, May 22--24, 2005. ACM Press

    2005

  36. [44]

    Sometimes-recurse shuffle - almost-random permutations in logarithmic expected time

    Ben Morris and Phillip Rogaway. Sometimes-recurse shuffle - almost-random permutations in logarithmic expected time. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology -- EUROCRYPT 2014 , volume 8441 of Lecture Notes in Computer Science , pages 311--326, ...

    2014

  37. [45]

    Proofs of quantumness from trapdoor permutations

    Tomoyuki Morimae and Takashi Yamakawa. Proofs of quantumness from trapdoor permutations. In Yael Tauman Kalai, editor, ITCS 2023: 14th Innovations in Theoretical Computer Science Conference , volume 251, pages 87:1--87:14, Cambridge, MA, USA, January 10--13, 2023. Leibniz Inte...

    2023

  38. [46]

    Incremental Offline/Online PIR

    Yiping Ma, Ke Zhong, Tal Rabin, and Sebastian Angel. Incremental Offline/Online PIR . In 31st USENIX Security Symposium (USENIX Security 22) , pages 1741--1758, Boston, MA, August 2022. USENIX Association

    2022

  39. [47]

    NTT Research Quantum Money Workshop , 2023

    2023

  40. [48]

    Generic attacks on Feistel schemes

    Jacques Patarin. Generic attacks on Feistel schemes. In Colin Boyd, editor, Advances in Cryptology -- ASIACRYPT 2001 , volume 2248 of Lecture Notes in Computer Science , pages 222--238, Gold Coast, Australia, December 9--13, 2001. Springer Berlin Heidelberg, Germany

    2001

  41. [49]

    https://informatics.ed.ac.uk/blockchain/events/previous-events/qsig

    QSig Workshop , 2024. https://informatics.ed.ac.uk/blockchain/events/previous-events/qsig

    2024

  42. [50]

    The mix-and-cut shuffle: Small-domain encryption secure against N queries

    Thomas Ristenpart and Scott Yilek. The mix-and-cut shuffle: Small-domain encryption secure against N queries. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology -- CRYPTO 2013, Part I , volume 8042 of Lecture Notes in Computer Science , pages 392--409, Santa Bar...

    2013

  43. [51]

    Elaine Shi, Waqar Aqeel, Balakrishnan Chandrasekaran, and Bruce M. Maggs. Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology -- CRYPTO 2021, Part IV , vol...

    2021

  44. [52]

    Quantum prudent contracts with applications to bitcoin, 2022

    Or Sattath. Quantum prudent contracts with applications to bitcoin, 2022

    2022

  45. [53]

    Public-key quantum money with a classical bank

    Omri Shmueli. Public-key quantum money with a classical bank. In Stefano Leonardi and Anupam Gupta, editors, 54th Annual ACM Symposium on Theory of Computing , pages 790--803, Rome, Italy, June 20--24, 2022. ACM Press

    2022

  46. [54]

    Semi-quantum tokenized signatures

    Omri Shmueli. Semi-quantum tokenized signatures. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology -- CRYPTO 2022, Part I , volume 13507 of Lecture Notes in Computer Science , pages 296--319, Santa Barbara, CA, USA, August 15--18, 2022. Springer, Cham, Sw...

    2022

  47. [55]

    Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science , pages 124--134, Santa Fe, NM, USA, November 20--22, 1994. IEEE Computer Society Press

    1994

  48. [56]

    How to use indistinguishability obfuscation: deniable encryption, and more

    Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In David B. Shmoys, editor, 46th Annual ACM Symposium on Theory of Computing , pages 475--484, New York, NY, USA, May 31 -- June 3, 2014. ACM Press

    2014

  49. [57]

    Collapse-binding quantum commitments without random oracles

    Dominique Unruh. Collapse-binding quantum commitments without random oracles. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology -- ASIACRYPT 2016, Part II , volume 10032 of Lecture Notes in Computer Science , pages 166--195, Hanoi, Vietnam, December 4--8, ...

    2016

  50. [58]

    Computationally binding quantum commitments

    Dominique Unruh. Computationally binding quantum commitments. In Marc Fischlin and Jean-S \' e bastien Coron, editors, Advances in Cryptology -- EUROCRYPT 2016, Part II , volume 9666 of Lecture Notes in Computer Science , pages 497--527, Vienna, Austria, May 8--12, 2016. Sprin...

    2016

  51. [59]

    Conjugate coding

    Stephen Wiesner. Conjugate coding. SIGACT News , 15(1):78–88, January 1983

    1983

  52. [60]

    Theory and applications of trapdoor functions (extended abstract)

    Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science , pages 80--91, Chicago, Illinois, November 3--5, 1982. IEEE Computer Society Press

    1982

  53. [61]

    Collision resistant hashing from sub-exponential learning parity with noise

    Yu Yu, Jiang Zhang, Jian Weng, Chun Guo, and Xiangxue Li. Collision resistant hashing from sub-exponential learning parity with noise. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology -- ASIACRYPT 2019, Part II , volume 11922 of Lecture Notes in Compute...

    2019

  54. [62]

    A note on the quantum collision and set equality problems

    Mark Zhandry. A note on the quantum collision and set equality problems. Quantum Info. Comput. , 15(7–8):557–567, May 2015

    2015

  55. [63]

    A note on quantum-secure prps

    Mark Zhandry. A note on quantum-secure prps. arXiv preprint arXiv:1611.05564 , 2016

    2016 arXiv

  56. [64]

    Quantum lightning never strikes the same state twice

    Mark Zhandry. Quantum lightning never strikes the same state twice. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology -- EUROCRYPT 2019, Part III , volume 11478 of Lecture Notes in Computer Science , pages 408--438, Darmstadt, Germany, May 19--23, 2019. Spring...

    2019

  57. [65]

    How to construct quantum random functions

    Mark Zhandry. How to construct quantum random functions. Journal of the ACM (JACM) , 68(5):1--43, 2021

    2021

  58. [66]

    New constructions of collapsing hashes

    Mark Zhandry. New constructions of collapsing hashes. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology -- CRYPTO 2022, Part III , volume 13509 of Lecture Notes in Computer Science , pages 596--624, Santa Barbara, CA, USA, August 15--18, 2022. Springer, C...

    2022

  59. [67]

    Quantum money from abelian group actions

    Mark Zhandry. Quantum money from abelian group actions. In Venkatesan Guruswami, editor, ITCS 2024: 15th Innovations in Theoretical Computer Science Conference , volume 287, pages 101:1--101:23, Berkeley, CA, USA, January 30 -- February 2, 2024. Leibniz International Proceedin...

    2024

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.