Semi-Quantum Money

Or Sattath; Roy Radian

REVIEW 1 major objections 4 minor 1 cited by

Semi-Quantum Money

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read This paper introduces semi-quantum money, the first quantum money whose minting and verification run over classical communication with a classical bank.

desk verdict Semi-quantum money with a classical bank is a genuine new model, and the LWE-based private scheme holds up; the public scheme is honestly conditional and the parallel-repetition step needs a formal proof. read the letter →

arxiv 1908.08889 v6 pith:Q7ZALLOC submitted 2019-08-23 quant-ph cs.CR

Roy Radian , Or Sattath This is my paper · ORCID

classification quant-phcs.CR

keywords semi-quantummoneyquantumclassicalmintingverificationlearningwitherrorsnoisytrapdoorclaw-freefunctionsparallelrepetitionlightning

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

This paper introduces semi-quantum money: quantum banknotes whose minting and verification both run as interactive protocols in which the bank is entirely classical. The money state is generated by the user, who prepares a superposition over a trapdoor function supplied by the bank, measures one register, and reports the result; this classical minting is what removes the need for a quantum bank and for quantum channels. The paper constructs a private, memoryless scheme whose security reduces to the hardness of Learning With Errors for quantum computers (Theorem 2), and a public, memory-dependent scheme based on quantum lightning with bolt-to-certificate (Theorem 1). Its main technical contribution is a perfect parallel repetition theorem for 1-of-2 puzzles, which amplifies a puzzle that a forger can solve with probability $\frac{1}{2}$ into one with negligible forging probability. The paper also proves that no quantum money scheme with classical minting can be information-theoretically secure, so computational assumptions are unavoidable.

What carries the argument

The carrying object is the 1-of-2 puzzle built from a Noisy Trapdoor Claw-Free Function (NTCF) — a two-to-one function family with a trapdoor and an adaptive hardcore bit property — together with a perfect parallel repetition theorem for such puzzles. Minting leaves the user holding a superposition $\frac{1}{\sqrt{2}}(|0\rangle|x_0\rangle + |1\rangle|x_1\rangle)$ over the two preimages of a measured image; verification is a random challenge asking either for a preimage $x_i$ with $f(x_i)=y$, or for a non-zero string $d$ and bit $i$ satisfying $d\cdot(J(x_0)\oplus J(x_1)) = i$, with $d$ in a specified good set. The adaptive hardcore bit property guarantees that any quantum adversary can pass both challenges of a single puzzle with probability at most $\frac{1}{2} + \mathrm{negl}(\lambda)$. Repeating $n$ puzzles in parallel under a single challenge bit preserves this guarantee with the success probability raised to the $n$-th power: the paper's Theorem 15 proves the repetition is perfect, by reducing to the black-box, rewinding-free parallel repetition theorem for weakly verifiable puzzles of [CHS05]. This is the main technical contribution, and it is what makes the money unforgeable: double-spending a note requires solving a 2-of-2 puzzle in at least one coordinate, an event driven to negligible probability.

What would settle it

A concrete refutation would be a quantum algorithm that solves LWE at the dimensions and noise parameters used in the NTCF instantiation of [BCM+18, Theorem 26]; that would let a counterfeiter recover both preimages of a claw and pass two verifications of a single minted note, refuting Theorem 2. For the public scheme, the falsifier is a procedure that outputs two bolts accepted under the same serial number for any candidate quantum lightning scheme, which would refute Theorem 1.

Watch

Extended reading notes

Core claim

The paper's central discovery is that quantum money can be moved off quantum communication infrastructure: minting and verification can both be classical protocols for the bank, as long as the user holds a quantum computer. It defines semi-quantum money as an interactive scheme in which the bank is classical in both minting and verification, and it gives the first constructions. In the private, memoryless scheme (Theorem 2), the bank sends $n$ functions from a Noisy Trapdoor Claw-Free Function family together with a MAC key; the user prepares superpositions of the form $\frac{1}{\sqrt{2}}(|0\rangle|x_0\rangle + |1\rangle|x_1\rangle)$, measures the function-output registers, and sends the measured values back as signed obligations. Verification is a single classical round in which the bank chooses random pre-image or equation challenges, and passing two verifications of one note forces the adversary to answer both challenges of at least one puzzle, which the perfect parallel repetition theorem makes negligibly likely. In the public, memory-dependent scheme (Theorem 1), the user generates a quantum lightning bolt, the bank signs its serial number, and spending converts the bolt into a classical certificate — checked against a database of spent serial numbers — that proves the bolt was destroyed. The paper further shows this is the natural extreme: a classical user backed by a quantum bank is inherently flawed, and Theorem 31 proves computational assumptions are unavoidable for any classical-minting scheme. The authors flag in Section 1 that the public construction sits on shaky ground: one quantum lightning candidate has been attacked, another relies on a hash function with no known instantiation, and the yet-unbroken knot-based candidate lacks bolt-to-certificate capability.

Load-bearing premise

The private scheme collapses if Learning With Errors is not hard for quantum computers at the specific parameter sets used, both for the NTCF instantiation and for the MAC and encryption building blocks, and the public scheme collapses if no quantum lightning scheme with bolt-to-certificate capability exists, which the authors themselves flag as on shaky ground.

Editorial extensions

If this is right

Semi-quantum money removes the need for a quantum communication infrastructure: banks stay classical, all transactions run over classical channels, and only users need quantum computers.
The private scheme shows that secure quantum money can rest on Learning With Errors hardness alone (together with LWE-based MACs and encryption), placing it on standard post-quantum assumptions.
The public scheme is inherently memory-dependent — the bank must keep a database of spent serial numbers — and whether a memoryless public semi-quantum scheme exists is left open.
The perfect parallel repetition theorem amplifies any $\frac{1}{2}$-hard 1-of-2 puzzle into a strong one with negligible soundness error, giving the NTCF-based tool exponentially small forging probability.
Classical minting marks a boundary: a computationally unbounded adversary can always double-spend a note, so any semi-quantum money scheme must rely on computational assumptions (Theorem 31).

Reading between the lines

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

Because the parallel-repetition reduction is black-box and rewinding-free, the same amplification should transfer to other quantum protocols with 1-of-2 structure; the certifiable-randomness protocol built on the same NTCF tests could plausibly be compressed from a linear number of rounds to a constant.
The user-side minting pattern — a classical issuer supplies trapdoor functions, the user prepares a superposition and reports a measurement — is a general template that could mint other unforgeable quantum credentials, such as tickets, coupons, or access tokens, from a classical issuer.
If LWE were ever solved by a quantum algorithm, the private scheme would degrade to the security of a classical serial-number database; semi-quantum money is therefore a bet on post-quantum computational hardness in a way that information-theoretically secure private money is not.
The two theorems together point to the private LWE-based scheme as the practical route; a memoryless public scheme will require a new primitive, most plausibly a lattice-based quantum lightning candidate that is unbroken and equipped with bolt-to-certificate.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Bottom line: this is the paper that makes quantum money usable with a classical bank and classical communication, and the private construction is a real result. The authors define semi-quantum money via classical minting plus Gavinsky-style classical verification, then give two constructions. The private scheme from NTCF/LWE is the substantive part: 1-of-2 puzzles from NTCF, perfect parallel repetition, mini-scheme, then full scheme with MAC and encryption. The reduction chain is honest, each step is stated as conditional on LWE, and the sequence-of-games proofs in Section 5 are careful. The public scheme is a clean composition of quantum lightning with bolt-to-certificate and a PQ signature, but it rests on an uninstantiated primitive; the authors say so openly in Section 1, so the paper is not overselling.

The genuinely new technical item is the perfect parallel repetition theorem for NTCF-based 1-of-2 puzzles. It is presented honestly as an application of CHS05 via equivalence to weakly verifiable puzzles. The only real rigor gap I see is that the CHS05 proof is black-box and rewind-free, so it should carry over to QPT solvers, but the paper gives a sketch (Section 4.3 and Appendix F) rather than a full formal proof. If that extension failed, Corollary 21 would collapse, and with it the private scheme. I have no counterexample or obstruction; the argument looks right. It just deserves a formal write-up.

The impossibility result (Theorem 31) is straightforward but worth having, and the discussion of memory-dependence versus memoryless is sensible. The related work is thorough, and the reuse of BS16a and CS20 is legitimate prior work, not hidden circularity.

Bottom line: private semi-quantum money from LWE is a solid conditional result, and the model is likely to be used by others. The public scheme is more speculative by design. This deserves serious peer review; the main request should be a fully formal treatment of the quantum parallel repetition step.

Referee Report

1 major / 4 minor

Summary. The paper introduces semi-quantum money, defined as quantum money in which both minting and verification are interactive protocols between a quantum user and a classical bank, with classical communication only. The central claim is that this is the first quantum money model allowing transactions with completely classical communication and an entirely classical bank. Two constructions are given: a public memory-dependent scheme (Theorem 1) built from quantum lightning with bolt-to-certificate and a post-quantum EU-CMA digital signature scheme, and a private memoryless scheme (Theorem 2) built from LWE via NTCF, 1-of-2 puzzles, a perfect parallel repetition theorem, and a mini-scheme-to-full-scheme lifting. The main technical contribution is a perfect parallel repetition theorem for 1-of-2 puzzles (Theorem 15), proved via a reduction to the CHS05 weakly verifiable puzzles theorem. The paper also proves that no classical-minting quantum money scheme can be information-theoretically secure (Theorem 31).

Significance. The significance is high if the claims hold. The paper identifies a meaningful new point in the design space of quantum money and provides a concrete conditional instantiation from LWE. The assumption handling is honest: the public scheme is explicitly based on an uninstantiated primitive and the authors flag the shaky status of quantum lightning candidates. The private-scheme proof chain is detailed and modular, with explicit reductions and sequence-of-games arguments, and the parallel repetition theorem is a potentially reusable tool. The impossibility result for information-theoretic security sharpens the boundary of the model. I see no circularity or hidden assumptions beyond those stated.

major comments (1)

[Section 4.3 (Theorem 15 and Corollary 21)] The soundness proof of Theorem 15 applies the Canetti-Halevi-Steiner parallel repetition theorem, [CHS05, Theorem 1], to quantum polynomial-time solvers, but the original theorem is stated for classical PPT solvers. The text argues that the CHS05 reduction is black-box and rewind-free, and Appendix F provides a sketch; this is plausible, but it is the one load-bearing step in the private-scheme chain (leading to Theorem 2) that is not a complete formal proof. I request a formal lemma for the QPT version, with a precise adversary model and a proof that repeated fresh runs of a quantum solver on the same classical input can be used to estimate the conditional probabilities required by the CHS05 argument; alternatively, a published theorem covering QPT solvers should be cited.

minor comments (4)

[Section 4.3, Definition 14] The symbol Vn is used both for the n-fold repetition algorithm and for the verification algorithm of the base puzzle; please use a different name for one of them to avoid confusion.
[Algorithm 2, OZ description] In line 3 of OZ, 'obtain an o ∈ Y' should read 'obtain a value o ∈ Y'.
[Proposition 10 proof] The expression 'Pr[QL.qverifypk(|ψ⟩) = 0]' should refer to the scheme $P's qverify rather than to QL directly.
[Theorem 31] The proof relies on the adversary replaying the original minting transcript, but the theorem statement only gives A the money state |$⟩; the statement should clarify that A, as the user in the mint protocol, may retain the classical transcript and measurement records.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the private scheme is a conditional reduction to LWE/NTCF/CHS05, and the public scheme is an explicit reduction to quantum lightning assumptions plus signatures.

full rationale

The paper's central claims are conditional reductions to external assumptions. The private scheme (Theorem 2) follows the chain: LWE hardness (external, from Brakerski et al.) implies an NTCF family; Theorem 13 gives a reduction from NTCF's adaptive hardcore bit property to a weak 1-of-2 puzzle; Theorem 15 and Corollary 21 use the Canetti-Halevi-Steiner parallel repetition theorem for weakly verifiable puzzles to amplify hardness to a strong 1-of-2 puzzle; Propositions 26-28 and Theorem 30 provide game-based reductions from strong 1-of-2 puzzles plus MAC/encryption to a full private semi-quantum money scheme. Each step is an explicit adversary reduction with clear security games, and no parameter is fitted to data or renamed as a prediction. The NTCF hardness property and the 1-of-2 puzzle hardness are not identical; Algorithm 3 gives the actual reduction between them. The parallel repetition theorem is explicitly attributed to CHS05 and the paper supplies a proof sketch, so the contribution is an application rather than an unverified import. The public scheme (Theorem 1) is a direct reduction to quantum lightning with bolt-to-certificate and a post-quantum signature scheme; the security proof in Theorem 11 constructs forgers for the underlying primitives from any counterfeiter. The sabotage aspect relies on Coladangelo-Sattath (CS20), a separate published work, and the authors themselves flag the quantum lightning candidates as on shaky ground; this is a disclosed assumption, not circularity. Self-citations to CS20 and Ben-David-Sattath (BS16a) are used for definitions and proof ideas, but the load-bearing arguments are either supplied in the paper or are genuinely external published results. No self-definitional, fitted-input, or uniqueness-imported circularity is present.

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

No parameters are fitted to data; the constructions are conditional on standard post-quantum assumptions and one stronger primitive, quantum lightning with bolt-to-certificate, which is not yet instantiated. The only potentially self-referential element is that definitions from CS20, co-authored by Sattath, are used verbatim, but the security proofs reduce to external hardness assumptions, so this does not create circular reasoning.

assumptions (6)

domain assumption Learning With Errors is hard for BQP with the parameter sets required by Brakerski et al. and by Boneh-Zhandry and Gagliardoni et al.
Used in Theorem 2 to instantiate NTCF, PQ-EU-CMA MAC, and PQ-IND-CPA encryption; no private scheme exists without it.
domain assumption An NTCF family satisfies the adaptive hardcore bit property.
Theorem 13 transfers this property to 1-of-2 puzzle hardness; it is the core of the private scheme's security.
standard math The Canetti-Halevi-Steiner parallel repetition theorem for weakly verifiable puzzles extends to quantum solvers.
Section 4.3 and Appendix F rely on this; the paper argues the reduction is black-box with no rewinding.
domain assumption A secure quantum lightning scheme with bolt-to-certificate capability exists.
Assumed in Theorem 1 and Algorithm 1; the paper notes no fully satisfactory candidate is known.
domain assumption A post-quantum EU-CMA digital signature scheme exists.
Used in the public scheme to sign serial numbers so users cannot mint their own notes.
standard math Standard quantum mechanics, including no-cloning and measurement collapse, holds.
Basis for quantum money states being unforgeable and for verification destroying or preserving notes as claimed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Semi-Quantum Money." pith.science (2026). https://pith.science/paper/Q7ZALLOC

@misc{pith2026190808889,
  author       = {Pith},
  title        = {Pith review of: Semi-Quantum Money},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q7ZALLOC}},
  note         = {Machine review of arXiv:1908.08889}
}

read the original abstract

Quantum money allows a bank to mint quantum money states that can later be verified and cannot be forged. Usually, this requires a quantum communication infrastructure to transfer quantum states between the user and the bank. Gavinsky (CCC 2012) introduced the notion of classically verifiable quantum money, which allows verification through classical communication. In this work we introduce the notion of classical minting, and combine it with classical verification to introduce semi-quantum money. Semi-quantum money is the first type of quantum money to allow transactions with completely classical communication and an entirely classical bank. This work features constructions for both a public memory-dependent semi-quantum money scheme and a private memoryless semi-quantum money scheme. The public construction is based on the works of Zhandry and Coladangelo, and the private construction is based on the notion of Noisy Trapdoor Claw Free Functions (NTCF) introduced by Brakerski et al. (FOCS 2018). In terms of technique, our main contribution is a perfect parallel repetition theorem for NTCF.

Figures

Figures reproduced from arXiv: 1908.08889 by the authors.

**Figure 2.** Regular (non-quantum) money direct transaction. The communi [PITH_FULL_IMAGE:figures/full_fig_p068_2.png] view at source ↗

**Figure 3.** Regular (non-quantum) money bank transaction. Though it is [PITH_FULL_IMAGE:figures/full_fig_p069_3.png] view at source ↗

Figures from the paper (12 more)

**Figure 4.** Figure 4: Private standard direct transaction. 70 [PITH_FULL_IMAGE:figures/full_fig_p070_4.png]

**Figure 5.** Figure 5: Standard bank transaction. 71 [PITH_FULL_IMAGE:figures/full_fig_p071_5.png]

**Figure 6.** Figure 6: Private classically verifiable direct transaction. In step (b), re [PITH_FULL_IMAGE:figures/full_fig_p072_6.png]

**Figure 7.** Figure 7: Classically verifiable bank transaction. [PITH_FULL_IMAGE:figures/full_fig_p073_7.png]

**Figure 8.** Figure 8: Private classically verifiable direct transaction for a scheme which [PITH_FULL_IMAGE:figures/full_fig_p074_8.png]

**Figure 9.** Figure 9: Private classically verifiable bank transaction for a scheme which [PITH_FULL_IMAGE:figures/full_fig_p075_9.png]

**Figure 10.** Figure 10: Private classical minting direct transaction. [PITH_FULL_IMAGE:figures/full_fig_p076_10.png]

**Figure 11.** Figure 11: Classical minting bank transaction. 77 [PITH_FULL_IMAGE:figures/full_fig_p077_11.png]

**Figure 12.** Figure 12: Private semi-quantum direct transaction. In step (b), receiver [PITH_FULL_IMAGE:figures/full_fig_p078_12.png]

**Figure 13.** Figure 13: Semi-quantum bank transaction. 79 [PITH_FULL_IMAGE:figures/full_fig_p079_13.png]

**Figure 14.** Figure 14: Public quantum money direct transaction. [PITH_FULL_IMAGE:figures/full_fig_p080_14.png]

**Figure 15.** Figure 15: One-shot signature direct transaction. 81 [PITH_FULL_IMAGE:figures/full_fig_p081_15.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Practically feasible robust quantum money with classical verification
quant-ph 2019-08 reject novelty 5.0 of 10

A new private quantum money scheme based on Sampling Matching claims 21.4% noise tolerance with a fixed linear-optics verifier, but the security proof is incomplete.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · cited by 1 Pith paper

[1]

The randomized key-generation algorithm key-gen takes as input 1λ and outputs a keyk←key-gen(1λ). 57

work page
[2]

The (possibly randomized) encryption algorithmencrypt takes as input a keyk and a plaintext messagem∈{0, 1}∗, and outputs a ciphertext c←encryptk(m)

work page
[3]

The deterministic decryption algorithmdecrypt takes as input a keyk and a ciphertextc, and outputs a messagem :=Deck(c). A private-key encryption system is required to haveperfect completeness, meaning that for everyλ, every k output by key-gen(1λ), and every m∈ {0, 1}∗, it holds thatdecryptk(encryptk(m)) =m. Deﬁnition 33(PQ-IND-CPA, adapted from [KL14, D...

work page
[4]

D continues to have oracle access toencryptk(·) and outputs a bitb′

work page
[6]

The distinguisherD is given input 1λand classical oracle access to encryptk(·), and outputs a pair of messagesm0,m 1 of the same length

work page
[7]

A uniform bit b ∈R {0, 1}is chosen, and then a ciphertext c ← encryptk(mb) is computed and given toD

work page
[9]

In the former case, we say thatD succeeds

The output of the game is deﬁned to be1 if b′= b, and 0 otherwise. In the former case, we say thatD succeeds. Deﬁnition 34(Message authentication code [KL14, Deﬁnition 4.1]). A message authentication code (MAC) consists of 3 PPT algorithmskey-gen, mac and verify satisfying:

work page
[10]

key-gen takes as input the security parameter1λand outputs a keyk

work page

Show all 30 references

[11]

mac takes as input a keyk and a messagem∈{0, 1}∗and outputs a tag t←mack(m)
[12]

It outputs a bit b := verifyk(m,t ), with b = 1 meaning valid and b = 0 meaning invalid

verify takes as input a keyk, a messagem, and a tagt. It outputs a bit b := verifyk(m,t ), with b = 1 meaning valid and b = 0 meaning invalid. A MAC is required to have perfect completeness, i.e., for everyλ, every key k←key-gen(1λ) and everym∈{0, 1}∗, it holds thatverifyk(m, ...
[13]

A keyk is generated by runningkey-gen(1λ)
[14]

The forger eventually outputs(m,t )

The forgerF is given input1λ, classical oracle access tomack(·) and classical oracle access toverifyk(·) (note that the forger cannot query the oracles in superposition). The forger eventually outputs(m,t ). Let Q denote the set of all queries thatF asked its signing oracle
[15]

In that case the output of the game is deﬁned to be1

F succeeds if and only if (1)verifyk(m,t ) = 1 and (2)m /∈Q. In that case the output of the game is deﬁned to be1. Deﬁnition 36(Digital signature scheme [KL14, Deﬁnition 12.1]). A digital signature scheme consists of three PPT algorithmskey-gen, sign and verify such that:
[16]

These are called the public key and the private key, respectively

The key-generation algorithmkey-gen takes as input a security param- eter 1λand outputs a pair of keys(pk,sk ). These are called the public key and the private key, respectively. We assume thatpk and sk each has length of at leastλ, and thatλcan be determined from either
[17]

It outputs a signatureσ←signsk(m)

The signing algorithmsign takes as input a private keysk and a mes- sage m. It outputs a signatureσ←signsk(m)
[18]

It outputs a bit b ← verifysk(m,σ), withb = 1 meaning valid and b = 0 meaning invalid

The deterministic veriﬁcation algorithmverify takes as input a pub- lic key pk, a message m and a signature σ. It outputs a bit b ← verifysk(m,σ), withb = 1 meaning valid and b = 0 meaning invalid. A digital signature scheme is required to haveperfect completeness, meaning tha...
[19]

key-gen is run to generate to obtain keys(pk,sk ). 59
[20]

The forger than outputs(m,σ)

ForgerF is given pk and access to a signing oracle signsk(·). The forger than outputs(m,σ). LetQ denote the set of all queries thatF asked its oracle
[21]

bolt” and tos as a “serial number

F succeeds iﬀverifypk(m,σ) = 1 and m /∈Q. In this case the output of the experiment is deﬁned to be 1 (and otherwise 0). Lemma 38 (Diﬀerence Lemma [Sho04, Lemma 1]). Let A,B,F be events deﬁned in some probability distribution, and suppose thatA∧¬F ⇐⇒ B∧¬F. Then|Pr[A]−Pr[B]|≤Pr...
[22]

The challenger runs (gen-bolt, verify-bolt)←QL.setup(1λ) and sends (gen-bolt, verify-bolt) toL. 60
[23]

L produces a pair|Ψ 12⟩∈H⊗2 $ ,s∈{0, 1}λ
[24]

accept” (1) or “reject

The challenger runs verify-bolt(·,s ) on each half of|Ψ 12⟩. The output of the game is 1 if both outcomes are “accept” (and otherwise 0). Deﬁnition 41(Bolt-to-certiﬁcate). For a quantum lightning scheme QL to have bolt-to-certiﬁcate capability, we change the procedureQL.setup(...
[25]

The challenger runs (gen-bolt, verify-bolt, gen-certiﬁcate, verify-certiﬁcate)←QL.setup(1λ), and sends the quadruple toC
[26]

C returnsc∈{0, 1}l(λ) and (|ψ⟩,s )
[27]

61 D Trapdoor Claw-Free Families Most of this section is taken verbatim from Brakerski et al

The challenger runs verify-certiﬁcate(s,c ) and verify-bolt(|ψ⟩,s ), and outputs 1 if they both accept (otherwise outputs 0). 61 D Trapdoor Claw-Free Families Most of this section is taken verbatim from Brakerski et al. [BCM+18]. Let λbe a security parameter, and letX andY be ...
[28]

There exists an eﬃcient proba- bilistic algorithm key-genF which generates a key k ∈ KF together with a trapdoortk: (k,tk)←key-genF(1λ)

Eﬃcient Function Generation. There exists an eﬃcient proba- bilistic algorithm key-genF which generates a key k ∈ KF together with a trapdoortk: (k,tk)←key-genF(1λ)
[29]

For all keysk∈KF the following con- ditions hold

Trapdoor Injective Pair. For all keysk∈KF the following con- ditions hold. (a) Trapdoor: For allb∈{0, 1}and x⁄= x′∈X, Supp(fk,b(x))\ Supp(fk,b(x′)) =∅. Moreover, there exists an eﬃcient determin- istic algorithm INVF such that for all b∈ {0, 1}, x∈ Xand y∈Supp(fk,b(x)), INVF(t...
[30]

Eﬃcient Range Superposition.28 There exists an eﬃcient proce- dure SAMPF that on inputk andb∈{0, 1}prepares a state|ψ′⟩which has a negligible trace distance to the state |ψ⟩= 1√ |X| ∑ x∈X,y∈Y ∑ (fk,b(x))(y)|x⟩|y⟩
[31]

For all keysk∈KF the following condi- tions hold, for some integerw that is a polynomially bounded function of λ

Adaptive Hardcore Bit. For all keysk∈KF the following condi- tions hold, for some integerw that is a polynomially bounded function of λ. (a) For allb∈{0, 1}and x∈X, there exists a setGk,b,x⊆{0, 1}w such thatPrd←U{0,1}w[d /∈Gk,b,x] is negligible, and moreover there exists an eﬃ...
[268]

[AMR20] G

ACM, 2020. [AMR20] G. Alagic, C. Majenz, and A. Russell. Eﬃcient Simulation of Random States and Random Unitaries. In A. Canteaut and Y.Ishai, editors,Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Appli- cations of Cryptograph...

2020 arXiv

Pith tools

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

[1] [1]

The randomized key-generation algorithm key-gen takes as input 1λ and outputs a keyk←key-gen(1λ). 57

work page

[2] [2]

The (possibly randomized) encryption algorithmencrypt takes as input a keyk and a plaintext messagem∈{0, 1}∗, and outputs a ciphertext c←encryptk(m)

work page

[3] [3]

The deterministic decryption algorithmdecrypt takes as input a keyk and a ciphertextc, and outputs a messagem :=Deck(c). A private-key encryption system is required to haveperfect completeness, meaning that for everyλ, every k output by key-gen(1λ), and every m∈ {0, 1}∗, it holds thatdecryptk(encryptk(m)) =m. Deﬁnition 33(PQ-IND-CPA, adapted from [KL14, D...

work page

[4] [4]

D continues to have oracle access toencryptk(·) and outputs a bitb′

work page

[5] [6]

The distinguisherD is given input 1λand classical oracle access to encryptk(·), and outputs a pair of messagesm0,m 1 of the same length

work page

[6] [7]

A uniform bit b ∈R {0, 1}is chosen, and then a ciphertext c ← encryptk(mb) is computed and given toD

work page

[7] [9]

In the former case, we say thatD succeeds

The output of the game is deﬁned to be1 if b′= b, and 0 otherwise. In the former case, we say thatD succeeds. Deﬁnition 34(Message authentication code [KL14, Deﬁnition 4.1]). A message authentication code (MAC) consists of 3 PPT algorithmskey-gen, mac and verify satisfying:

work page

[8] [10]

key-gen takes as input the security parameter1λand outputs a keyk

work page