Pith. sign in

REVIEW 3 major objections 5 minor 92 references

Quantum preprocessing for information-theoretic security in two-party computation

T0 review · 3 major / 5 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 The paper claims that two parties can replace a trusted initializer by running abort-checked quantum preprocessing protocols, so that the generated one-time tables leak asymptotically vanishing information about private inputs when at…

desk verdict A genuinely new protocol stack for replacing a trusted initializer with checked quantum preprocessing, but the central security claim rests on an asserted multi-copy tradeoff that needs a real proof before it is load-bearing. read the letter →

arxiv 1908.05584 v6 pith:IT52NSMM submitted 2019-08-15 quant-ph cs.CR

Li Yu This is my paper · ORCID
classification quant-phcs.CR PACS 03.67.Dd03.67.Lx
keywords quantumpreprocessingone-timetablestwo-partycomputationinformation-theoreticsecurityhomomorphicencryptionoblivioustransferno-signalingcorrelationsforced
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

Two-party cryptographic tasks normally need either computational assumptions or a trusted initializer who pre-distributes correlated random bits, the one-time tables. This paper argues that the two parties themselves can generate those tables by short quantum protocols that allow aborts: any detected cheating causes the batch to be rejected before it touches real data. With at least one party 'conservative'—willing to sacrifice the chance of learning the other's input by actually performing the checks—the leakage is asymptotically vanishing in the noiseless case and controllable in the noisy case. Because the security is forced by verification, the probability that some useful tables are produced can approach one even though the protocols may abort. If right, the scheme supplies nontrivial information-theoretic security for generic two-party classical and quantum computation, including interactive quantum homomorphic encryption.

What carries the argument

The load-bearing object is the one-time table produced by Protocol 1: a two-message quantum procedure that takes random bits x and y and returns (x·y)⊕r to Alice and r to Bob, with the CNOT gate's basis-switching property ensuring the distributed AND. Around it, the checking Protocols 3, 4, and 6 impose verification: Bob (or both parties) randomly select instances, demand that the revealed inputs and outputs satisfy $a_j b_j = e_j \oplus f_j$, and abort when failures exceed a threshold. The security argument rests on information-tradeoff inequalities such as $I^M_y + I^M_r \le 1$ and $I^M_y + I^M_{y\oplus r} \le 1$, together with Holevo-bound versions $\chi_y + \max(\chi_r, \chi_{y\oplus r}) \le 1 + f(\epsilon)$, which say that a cheating Alice who must pass Bob's checks can learn almost nothing about y; analogous inequalities protect Alice in Protocol 4. This is 'forced security': useful tables exist only if the checks pass, so the data-independent preprocessing stage can abort safely without leaking meaningful data.

What would settle it

Search the space of Bob's received two-qubit states—modelled as pure states on four qubits via Schmidt decomposition—for a violation of the Holevo tradeoff $\chi_y + \max(\chi_r, \chi_{y\oplus r}) \le c$ with c near the claimed bound; any state with max near 1 while $\chi_y$ remains bounded away from 0 falsifies Theorem 1, and an experimental implementation of Protocol 1 where Bob's checks are passed with high probability while Alice's accessible information about y exceeds the predicted $\epsilon$-dependent bound would do the same.

Watch

Extended reading notes

Core claim

The central discovery is that the ideal resource of one-time tables—random bits x and y on the two sides together with (x·y)⊕r and r—need not be assumed from a trusted party: Protocols 1 and 11 realize the underlying nonlocal AND gate with partial privacy, and Protocols 3 through 6 verify those raw instances so that a cheating party who wants the generated tables to be correct and usable must give up almost all information about the other party's input. The security statements are asymptotic: Protocol 3 makes Bob's input asymptotically secure against a cheating Alice, Protocol 4 gives both parties asymptotic security when both sides check, Protocol 5 makes Alice's leakage exponentially small by combining tables, and Protocol 6 suppresses output error while keeping security comparable to Protocol 4. In the ideal noiseless case, the abort-based checks force the cheater's average cheating rate to be arbitrarily small, so with weak cooperation and a conservative checker, useful tables are generated with probability approaching one.

Load-bearing premise

The protocols' security collapses if no party is conservative: someone must actually run the prescribed checks and abort on failures, prizing their own privacy over the chance to learn the other's input, because the checks are what force a cheating counterpart to give up information.

Editorial extensions

If this is right

  • Generic two-party boolean circuits with private inputs can be evaluated with asymptotically vanishing leakage in the noiseless case; the main computation needs about circuit-depth rounds and only XOR/AND decompositions.
  • Interactive quantum homomorphic encryption becomes possible with quantum preprocessing: the number of one-time tables is O(n²+R²) for n input qubits and R T gates, giving almost-optimal information-theoretic data and circuit privacy.
  • A constant-round QHE scheme exists at exponential cost, and interpolating between the two schemes trades rounds against table count.
  • Check-based implementations of PR-box-type and more general no-signaling correlations can be built with inert classical communication, and 1-out-of-2 oblivious transfer and bit commitment follow under the conservative-party assumption.
  • Physical noise makes leakage in Protocols 3 and 4 linear in the noise level, while Protocol 5 keeps Alice's privacy exponentially good at polynomial overhead; Protocol 6 reduces output error to polynomially small at polynomial cost.

Reading between the lines

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

  • If the conservative-party assumption is acceptable in client-server settings, interactive quantum homomorphic encryption could be built with information-theoretic security and polynomial resources, avoiding the computational assumptions of standard fully homomorphic encryption.
  • Because Protocol 5 makes one party's leakage almost noise-independent, a hybrid deployment could use Protocol 5 for high-sensitivity inputs and Protocol 6 for low-noise correctness, a trade-off the paper does not quantify.
  • The check-based PR-box implementation with inert communication suggests an experimental route: certify no-signaling correlations by timing and message-content checks rather than spacelike separation; one could test whether the correlation parameter E can be device-independently estimated from the check statistics.
  • The information-tradeoff inequalities likely generalize to qudits and multipartite tables; a concrete next step would be to derive the analogue of Eq. (5) for d-dimensional inputs and see whether the 1+f(ε) bound persists.
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.

Referee Report

3 major / 5 minor

Summary. The paper proposes replacing a trusted initializer in two-party computation by bipartite quantum preprocessing with aborts. Protocol 1 implements a distributed AND gate with partial privacy, and Protocols 3-6 add checking and combining steps to generate one-time tables with claimed asymptotically vanishing leakage, under the assumptions that one party is "conservative" and the other is weakly cooperating. Applications are given to classical two-party computation, 1-out-of-2 oblivious transfer, bit commitment, interactive and constant-round quantum homomorphic encryption, and check-based implementations of no-signaling correlations. The security analysis is built on Propositions 1-2 and Theorems 1-2, with numerical support in Appendix B.

Significance. If the central security claims were established, the paper would be significant: it offers a concrete route to information-theoretic security in generic two-party computation without a trusted initializer, under assumptions weaker than full honesty, and it connects this primitive to quantum homomorphic encryption and no-signaling correlations. The paper is commendably explicit about its assumptions, including the conservative-party requirement, weak cooperation, and abort behavior, and it fully specifies the base protocol. The honest-but-curious analysis and the application sections are useful contributions in their own right. However, because the multi-copy tradeoff that carries the security proofs is asserted rather than proved, the significance is conditional on closing that gap.

major comments (3)
  1. [Sec. III, Theorem 1 proof, paragraph after Eq. (6)] The extension of the single-instance tradeoff Eq. (5) to correlated, jointly entangled cheating over m instances is asserted rather than proved. The text says that the generalization of Eq. (6) "should hold" and that other instances "serve as auxiliary systems," but accessible information is not subadditive, and a joint final measurement over m systems can in principle extract more than the one-copy Holevo tradeoff curve. The one-bit communication bound in Prop. 1 is a single-round bound on classical mutual information with a fixed measurement M, so it does not control the marginal Holevo quantities under joint attacks. The same gap appears in the corresponding step of Theorem 2. Since Protocols 3-6 and all applications inherit this step, the central claim of asymptotically vanishing leakage is not established.
  2. [Appendix B, Eq. (B3), and Eq. (5) in Theorem 1] The quantitative form of the tradeoff is not established analytically. Appendix B reports only that the Holevo sum is at most a constant c "somewhat larger than 1.388" that is "yet to be precisely determined," and gives numerical values f(0.1)≈0.3, f(0.01)≈0.06. Uniform continuity from the extreme point max=1 ⇒ χy=0 yields only existence of some f(ε) with f(0)=0; it does not yield the specific bound χy≤ε+f(ε) used in the proof. Moreover, the argument for the implication (6) invokes Prop. 1, but Prop. 1 bounds single-measurement mutual informations rather than Holevo quantities, so the step "the latter implies χy=0" requires a separate proof. Without Eq. (5), the claimed leakage rate is unsupported.
  3. [Protocol 3, Steps 2-4, and Theorem 1] The random-check sampling argument does not by itself bound leakage on the m−K unchecked tables that are actually used. From K checked instances Bob estimates an average cheating rate ε, and the proof transfers the bound ε+f(ε) to all remaining instances. This transfer presupposes a well-defined per-instance cheating rate and either independence or the unproved multi-copy tradeoff of the first major comment. A cheating Alice can keep checked instances statistically clean while placing information about y in unchecked instances, and the text explicitly acknowledges that Alice can choose different measurements on the remaining instances. The statement that the expected information about y in the remaining instances is arbitrarily small therefore requires a proof; the per-instance checking statistics alone do not imply it.
minor comments (5)
  1. [Protocol 1, Step 3] Bob's output bit is introduced as h = h1⊕h2, but the protocol specification and all later text use r; please use a single symbol throughout.
  2. [Appendix A, last paragraph] The sentence "The Protocol 2 is quite resistent to such attack" contains a typo: "resistent" should be "resistant".
  3. [Sec. III, after Protocol 4] The claim that it "suffices to assume either one of the parties is conservative" is argued informally; since applications depend on this assumption, a formal statement of which party must be conservative in each protocol and application would be helpful.
  4. [Sec. VII.3] Statements such as "the allowed circuit depth is a constant" are qualitative; please make them quantitative or asymptotic, since the noise model and the security parameter are not formally specified.
  5. [Protocol 11, Appendix A] The EPR-pair testing procedure is described only in prose; please specify the test and explain how its abort behavior composes with the checks used in Protocol 4.

Circularity Check

0 steps flagged · score 0.0 of 10

No construction-level circularity: the security analysis is derived from in-paper one-bit communication inequalities; the self-citation to [27] supplies the base protocol but is not load-bearing.

full rationale

The derivation chain is self-contained at the level where its security claims are argued. Proposition 1 is proved in-paper from the observation that the Bob-to-Alice communication in Protocol 1 is effectively one classical bit, and Proposition 2 is the corresponding statement for the reverse direction. Theorem 1 then builds on the in-paper Holevo tradeoff claim (Eq. (5)) and a sampling argument over Bob's checked instances; Theorem 2 is explicitly parallel. No security quantity is defined in terms of the security conclusion, and no fitted numerical value from Appendix B is fed into the proof: the appendix is supporting numerics, not an input. The base Protocol 1 is credited to the author's earlier work [27] but is fully specified in this paper, so that self-citation is attribution rather than a load-bearing uniqueness or ansatz claim. The one serious gap is the extension to correlated cheating in the proof of Theorem 1, where the paper states that the generalization of Eq. (5) 'should hold approximately' and that other instances 'serve as auxiliary systems'; this is an unproved assertion and a genuine rigor concern, but it is not a circular reduction, because the inequality is not assumed as the definition of security and the paper does not rename a fitted parameter as a prediction. Accordingly, no circular step meeting the quoted-evidence standard is established.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The new protocols rely on: (i) the behavioral assumptions that one party is conservative and the other weakly cooperating; (ii) standard quantum information facts (bounded ancilla dimension, uniform continuity of Holevo quantities, non-occurrence of locking); and (iii) an unproven generalization of the tradeoff inequality to correlated attacks (Theorem 1 proof). No new physical entities are postulated. Protocol thresholds such as K/m and failure limits are user-chosen parameters, not fitted to data.

free parameters (1)
  • Holevo tradeoff constant c in Eq. (B3) = approximately 1.388 (lower bound, undetermined)
    Obtained from numerical search over 500000 random two-qubit mixed states in Appendix B; cited as evidence for the tradeoff curve, but not used in the formal proof of Theorem 1.
assumptions (5)
  • domain assumption At least one party is conservative: values the privacy of his/her own data higher than the possibility of learning the other party's data, and therefore performs the prescribed checks and aborts on failures.
    Stated in Sec. III ('In the following we assume that Bob is conservative...') and Sec. IV; all security guarantees of Protocols 3-6 and their applications rest on this.
  • domain assumption The other party is weakly cooperating, i.e., does not cheat in some batch of instances of Protocol 1, so that some one-time tables pass the tests.
    Stated in Sec. III before Protocol 3 ('We require Alice to be weakly cooperating...'); without it, the protocol always aborts and no tables are produced.
  • ad hoc to paper The one-copy tradeoff inequality (5) and its extreme-point implication (6) extend to the case where Alice's operations are correlated across instances of Protocol 1.
    Asserted in the proof of Theorem 1 (Sec. III): 'the generalization ... should hold, due to the similar reason as that after Eq. (6)'; not proven.
  • standard math The locking of classical correlations does not occur in Protocol 1, so the effective one-bit communication bound used in Props. 1 and 2 applies.
    Invoked in the proof of Prop. 1 in Sec. III, with reference to DiVincenzo et al. (locking) [29].
  • standard math Holevo quantities are uniformly continuous on the relevant bounded-dimensional state space, so Eq. (5) follows from the extreme point (6) up to a continuous error f(epsilon).
    Used in the proof of Theorem 1 (Sec. III); standard property of Holevo information for finite-dimensional states.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum preprocessing for information-theoretic security in two-party computation." pith.science (2026). https://pith.science/paper/IT52NSMM

@misc{pith2026190805584,
  author       = {Pith},
  title        = {Pith review of: Quantum preprocessing for information-theoretic security in two-party computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IT52NSMM}},
  note         = {Machine review of arXiv:1908.05584}
}
abstract

In classical two-party computation, a trusted initializer who prepares certain initial correlations, known as one-time tables, can help make the inputs of both parties information-theoretically secure. We propose some bipartite quantum protocols with possible aborts for approximately generating such bipartite classical correlations with varying degrees of privacy, without introducing a third party. Under some weak requirements for the parties, the security level is nontrivial for use in bipartite computation. We show that the security is sometimes dependent on the noise level, but we propose a method for dealing with noise. The security is "forced security", which implies that the probability that some useful one-time tables are generated can approach $1$ in the noiseless case under quite weak assumptions about the parties, although the protocols allow aborts. We show how to use the generated one-time tables to achieve nontrivial information-theoretic security in generic two-party classical or quantum computation tasks, including (interactive) quantum homomorphic encryption. Our methods provide check-based implementations of some no-signaling correlations, including the PR-box type, with the help of communication which carry no information about the inputs in the generated correlations.

Figures

Figures reproduced from arXiv: 1908.05584 by the authors.

Figure 1
Figure 1. FIG. 1: An illustration of Eq. (B3) by numerical calcula [PITH_FULL_IMAGE:figures/full_fig_p023_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2: A simplified version of a gadget in [11] for applying [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

92 extracted references · 79 canonical work pages

  1. [1]

    Suppose m one-time tables were implemented

    Alice and Bob perform many instances of Protocol 1 to generate some one-time tables, and exchange messages to agree on which instances were successfully implemented experimentally. Suppose m one-time tables were implemented. The one-time tables labeled by j has inputs aj and bj, and outputs ej and fj

  2. [2]

    He tells his choices to Alice

    (The steps 2 to 4 can be done concurrently with the steps 5 to 7.) Bob randomly selects KB integers in {1,··· ,m}, which are labels for which one-time table. He tells his choices to Alice

  3. [3]

    Alice sends the bits aj and ej to Bob for all chosen labels j

  4. [4]

    If the total number of failures is larger than some preset number of Bob’s (e.g

    For any chosen label j, Bob checks whether aj and ej satisfy that aj·bj = ej⊕fj. If the total number of failures is larger than some preset number of Bob’s (e.g. 0, or a small constant times m), he aborts the protocol, or asks Alice to restart the protocol to do testing on a new batch of instances of Protocol 1 if the two parties still want to perform som...

  5. [5]

    The chosen set of integers may overlap with the set chosen by Bob

    Alice randomly chooses KA integers in{1,··· ,m}, and tells Bob her choices. The chosen set of integers may overlap with the set chosen by Bob

  6. [6]

    Bob sends the bits bj and fj to Alice for the chosen labels j

  7. [7]

    If the total number of failures is larger than some preset number of Alice’s, she aborts the protocol, or asks Bob to restart the protocol if needed

    For any chosen label j, Alice checks whether aj·bj =ej⊕fj holds. If the total number of failures is larger than some preset number of Alice’s, she aborts the protocol, or asks Bob to restart the protocol if needed

  8. [8]

    restarts

    The remaining one-time tables are regarded as having passed the checking and will be used later in the two-party computing task. They may repeat the steps above to prepare more one-time tables on demand. bounded by 1 bit. And since the bits x and x⊕r′ are independent, we have that the inequality (8) holds. The inequalities (7) and (8) together imply (9). ...

Show all 92 references
  1. [9]

    Suppose the instance labeled by j has inputs aj and bj, and outputs ej and fj

    Alice and Bob perform Protocol 3 or Protocol 4 to obtain some one-time tables after checking. Suppose the instance labeled by j has inputs aj and bj, and outputs ej and fj

  2. [10]

    Each new instance corresponds to a set S of old instances which satisfy that Bob’s input bits are equal (denoted as b0)

    Bob determines which remaining one-time tables are to be combined into one new instance of one-time table, and tells Alice his decision. Each new instance corresponds to a set S of old instances which satisfy that Bob’s input bits are equal (denoted as b0). A new instance has ...

  3. [11]

    Alice and Bob perform many instances of Protocol 1 to generate some one-time tables, and exchange messages to agree on which instances were successfully implemented experimentally

  4. [12]

    They use more instances and a higher ratio of checking by Bob, for better privacy of Bob

    Alice and Bob uses the method in Protocol 4 to check the instances. They use more instances and a higher ratio of checking by Bob, for better privacy of Bob

  5. [13]

    auxiliary

    Bob chooses a target instance of a one-time table with inputs a0 andb0 and outputse0 andf0. He also randomly chooses other q instances (called “auxiliary” one-time tables) for helping detecting errors in the following step

  6. [14]

    Bob asks Alice to send a0⊕aj ande0⊕ej to him

    Suppose the auxiliary one-time table labeled by j has inputs aj andbj, and outputs ej andfj, for j = 1,...,q . Bob asks Alice to send a0⊕aj ande0⊕ej to him. For those j withbj =b0, Bob checks whether (a0⊕aj)·b0 =e0⊕ej⊕f0⊕fj. If there is an error, Bob rejects such target instan...

  7. [15]

    conservative

    The one-time tables which passed the checking will be used later in the two-party computing task. Alice and Bob repeat the steps starting from Step 3 to prepare more one-time tables. bj are equal to redesign her attacks in Steps 1 or 2, since the choice of which of them are eq...

  8. [16]

    Alice and Bob perform Protocol 3 or 4 or 5 or 6 to obtain n one-time tables

  9. [17]

    II, with the output being distributed

    For evaluating the linear polynomial z = (c + ∑n j=1ajbj) mod 2, Alice and Bob perform the evaluation of the nonlocal AND gate for aj and bj using the procedure in Sec. II, with the output being distributed. They locally calculate the XOR of all bits from the outputs, and Bob ...

  10. [18]

    Any nonlocal AND gate in the original circuit is a special case of the linear polynomial

    Alice and Bob decompose the two-party circuit to be evaluated into some local circuits with AND, XOR gates, and some linear polynomials with bipartite input, while adding possible ancillary bits with fixed initial value 1 (for implementing the NOT gates with the help of XOR). A...

  11. [19]

    one or both input bits are the XOR of two remote bits

    For each AND gate not in the initial stage, the inputs may be distributed, i.e. one or both input bits are the XOR of two remote bits. In the case that both input bits are distributed, Alice and Bob decompose such gate into the XOR of the outputs of two local AND gates and two...

  12. [20]

    The linear polynomials are evaluated using Protocol 7 with distributed output

    They perform the gates in the resulting circuit in pre-arranged order. The linear polynomials are evaluated using Protocol 7 with distributed output

  13. [21]

    data on average is better (e.g

    At the end of the circuit, one party sends some bits to the other party so that the distributed bits for the output are recombined to form the correct output; if there are output on two parties, both parties need to send messages. data on average is better (e.g. when they disc...

  14. [22]

    with only one variable and no constant term), where a =m0⊕m1, and b is Bob’s input bit

    Alice and Bob run an instance of Protocol 7 with the polynomial of the form z =a·b (i.e. with only one variable and no constant term), where a =m0⊕m1, and b is Bob’s input bit. Suppose the output bit on Alice’s side is g, then the output on Bob’s side must be h =z⊕g

  15. [23]

    Bob’s output bit is m0⊕g⊕h

    Alice sends m0⊕g to Bob. Bob’s output bit is m0⊕g⊕h. protocols. In the Protocol 10 we propose a bit commit- ment protocol inspired by a computationally-secure con- struction based on quantum one-way permutations [35]. Here, instead of using the quantum one-way permuta- tions, ...

  16. [24]

    They decide on a large integer m related to the intended security of the current bit commitment protocol

    Alice and Bob perform Protocol 5 to obtain some one- time tables with the degree of security dependent on re- source usage. They decide on a large integer m related to the intended security of the current bit commitment protocol

  17. [25]

    She asks Bob to together calculate m nonlocal AND gates using the method in Sec

    Suppose Alice wants to commit a bit b. She asks Bob to together calculate m nonlocal AND gates using the method in Sec. II, with her input bits being always b, but Bob’s inputs are random bits chosen by himself. They obtain some distributed bits as the outcomes. This completes...

  18. [26]

    outcome strings

    (Reveal phase) Alice sends Bob her output in the in- stances of the nonlocal AND gates in the previous step. Bob takes the XOR for the corresponding pairs of bits to recover the results of the nonlocal AND gates. From these results, Bob finds out b, or decides that Alice has ch...

  19. [27]

    The coefficient- update rules for the variables under the T gate can be obtained from the relations TZ = ZT, TX =e−πi/4PXZT

    = (Xa 1Zb⊕d 1 ⊗ Xa⊕c 2 Zd 2)CNOT12, (12) where the ⊕ is addition modulo 2, and in the gate CNOT12, the qubit 1 is the control. The coefficient- update rules for the variables under the T gate can be obtained from the relations TZ = ZT, TX =e−πi/4PXZT. (13) The coefficient-update r...

  20. [28]

    Alice and Bob produce a large number of one-time tables

  21. [29]

    The 2 n bits indicating the Pauli corrections are part of the vari- ables in the polynomials to be evaluated

    Alice teleports her n input data qubits to Bob with- out telling him any Pauli corrections. The 2 n bits indicating the Pauli corrections are part of the vari- ables in the polynomials to be evaluated

  22. [30]

    Alice and Bob each does their own part of opera- tions in Protocol 7 to evaluate the current linear polynomial, which has 2n variables

    For each stage of the circuit consisting of some Clif- ford gates and a T gate, the two parties do the fol- lowing: Bob calculates the coefficients (including the constant term) in the linear polynomial to be used for deciding the P† correction after the T gate. Alice and Bob ea...

  23. [31]

    He does his part in evalu- ating those polynomials, while Alice also does her part

    After the last T gate, Bob performs the last Clif- ford gates in the desired circuit, and calculates his coefficients in the last polynomials for calculating the final Pauli masks. He does his part in evalu- ating those polynomials, while Alice also does her part. This includes e...

  24. [32]

    The resulting state is the final quantum output

    Alice corrects the received state from teleportation with the corresponding Pauli operators, which are determined from Bob’s message as well as her part of the output of the last polynomials. The resulting state is the final quantum output. The following is an estimate of the r...

  25. [33]

    (The positions of the T gates in the circuit is known to both parties.) They produce a sufficient number of one-time tables

    Alice and Bob each calculates the (nonlinear) poly- nomials locally according to the circuit to be com- puted. (The positions of the T gates in the circuit is known to both parties.) They produce a sufficient number of one-time tables

  26. [34]

    Bob calculates the XOR of each coefficient in the (nonlinear) polynomials with his input in a unique precomputed one-time table, and sends the result- ing bits, and the labels for the corresponding one- time tables to Alice

  27. [35]

    The 2 n bits indicating the Pauli corrections are part of the vari- ables in the polynomials to be evaluated

    Alice teleports her n input data qubits to Bob with- out telling him any Pauli corrections. The 2 n bits indicating the Pauli corrections are part of the vari- ables in the polynomials to be evaluated. With the received message, Alice computes her part of the output of the (no...

  28. [36]

    The Bob part of the output of the first polynomial decides which measurements he should do in the first garden-hose gadget

    Bob receives Alice’s message and calculates his out- put for the first polynomial (which is linear) using Protocol 7. The Bob part of the output of the first polynomial decides which measurements he should do in the first garden-hose gadget. He performs the Clifford gates and the ...

  29. [37]

    The resulting state is the final quantum output

    Alice corrects the received state from teleportation using the corresponding Pauli gates, which are de- termined from Bob’s message as well as her part of the output of the last polynomials. The resulting state is the final quantum output. We analyze the resource cost of Scheme...

  30. [38]

    instantaneous

    + 1]× 2 + 2 whenk >1, so when k =R, the number of terms is O(n· 3R). There are R polynomials (one for each T gate, for evaluating the X correction before the T gate) which follow the induction rule above. But the last 2n polynomials do not follow the rule, and they do not incr...

  31. [39]

    This is inspired by the classical case in [4]

    Extensions of protocols The qubit-based quantum protocols in this work can be generalized to work for qudits in principle. This is inspired by the classical case in [4]. This requires some changes in the classical usage of the generated correla- tions. The methods in this work...

  32. [40]

    Physical implementations of Protocol 1 The Protocol 11 is an entanglement-based version of Protocol 1. The shared entanglement in Protocol 11 could be prepared by a fixed entanglement-generating device, allowing for failures in preparation (although we allow failures in the who...

  33. [41]

    first party

    Effects of noise and errors If direct sending of photons is used in Protocol 1, we suggest using the known methods such as decoherence- free subspaces or quantum codes, to reduce or prevent the errors in the transmission. We leave the details for future work. In the following, ...

  34. [42]

    Fully homomorphic encryption using ideal lattices

    Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing , STOC ’09, pages 169–178, New York, NY, USA, 2009. ACM

    2009

  35. [43]

    Brakerski and V

    Z. Brakerski and V. Vaikuntanathan. Efficient fully ho- momorphic encryption from (standard) LWE. In 2011 IEEE 52nd Annual Symposium on Foundations of Com- puter Science, pages 97–106, Oct 2011

    2011

  36. [44]

    A. C. Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science, pages 162–167, Oct 1986

    1986

  37. [45]

    One-time tables for two-party compu- tation

    Donald Beaver. One-time tables for two-party compu- tation. In Wen-Lian Hsu and Ming-Yang Kao, editors, Computing and Combinatorics , pages 361–370, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg

    1998

  38. [46]

    Rohde, Joseph F

    Peter P. Rohde, Joseph F. Fitzsimons, and Alexei Gilchrist. Quantum walks with encrypted data. Phys. Rev. Lett., 109:150501, 2012

    2012

  39. [47]

    Symmetric quantum fully homomorphic en- cryption with perfect security

    Min Liang. Symmetric quantum fully homomorphic en- cryption with perfect security. Quantum Inf. Process. , 12:3675–3687, 2013

    2013

  40. [48]

    P´ erez-Delgado, and Joseph F

    Li Yu, Carlos A. P´ erez-Delgado, and Joseph F. Fitzsi- mons. Limitations on information-theoretically-secure quantum homomorphic encryption. Phys. Rev. A , 90:050303(R), Nov 2014

    2014

  41. [49]

    S.-H. Tan, J. A. Kettlewell, Y. Ouyang, L. Chen, and J. F. Fitzsimons. A quantum approach to homomorphic encryption. Sci. Rep., 6:33467, 2016

    2016

  42. [50]

    Ouyang, S.-H

    Y. Ouyang, S.-H. Tan, and J. Fitzsimons. Quantum ho- momorphic encryption from quantum codes. Phys. Rev. A, 98:042334, 2018

    2018

  43. [51]

    Quantum homo- morphic encryption for circuits of low T-gate complexity

    Anne Broadbent and Stacey Jeffery. Quantum homo- morphic encryption for circuits of low T-gate complexity. In Proceedings of Advances in Cryptology — CRYPTO 2015, pages 609–629, 2015

    2015

  44. [52]

    Quantum homomorphic encryption for polynomial-sized circuits

    Yfke Dulek, Christian Schaffner, and Florian Speelman. Quantum homomorphic encryption for polynomial-sized circuits. CRYPTO 2016: Advances in Cryptology - CRYPTO 2016, pages 3–32, 2016

    2016

  45. [53]

    Newman and Y

    M. Newman and Y. Shi. Limitations on Transversal Computation through Quantum Homomorphic Encryp- tion. Quantum Information and Computation , 18:927– 21 948, 2018

    2018

  46. [54]

    Lai and K.-M

    C.-Y. Lai and K.-M. Chung. On Statistically-Secure Quantum Homomorphic Encryption. Quantum Informa- tion and Computation , 18:785–794, 2018

    2018

  47. [55]

    U. Mahadev. Classical homomorphic encryption for quantum circuits. In 2018 IEEE 59th Annual Sym- posium on Foundations of Computer Science (FOCS) , pages 332–338, Oct 2018

    2018

  48. [56]

    Quantum fully homomorphic encryption with verification

    Gorjan Alagic, Yfke Dulek, Christian Schaffner, and Flo- rian Speelman. Quantum fully homomorphic encryption with verification. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017 , pages 438–467, Cham, 2017. Springer International Pub- lishing

    2017

  49. [57]

    M. Newman. Further Limitations on Information- Theoretically Secure Quantum Homomorphic Encryp- tion. http://arxiv.org/abs/1809.08719, September 2018

    2018 arXiv

  50. [58]

    Si-Hui Tan, Yingkai Ouyang, and Peter P. Rohde. Prac- tical somewhat-secure quantum somewhat-homomorphic encryption with coherent states.Phys. Rev. A, 97:042308, Apr 2018

    2018

  51. [59]

    Secure assisted quantum computation

    Andrew Childs. Secure assisted quantum computation. Quantum Information and Computation , 5(6):456, 2005

    2005

  52. [60]

    Fisher, A

    K. Fisher, A. Broadbent, L.K. Shalm, Z. Yan, J. Lavoie, R. Prevedel, T. Jennewein, and K.J. Resch. Quantum computing on encrypted data. Nat. Commun. , 5:3074, 2014

    2014

  53. [61]

    Fitzsimons

    Yingkai Ouyang, Si-Hui Tan, Liming Zhao, and Joseph F. Fitzsimons. Computing on quantum shared secrets. Phys. Rev. A , 96:052333, Nov 2017

    2017

  54. [62]

    Yingkai Ouyang, Si-Hui Tan, Joseph Fitzsimons, and Pe- ter P. Rohde. Homomorphic encryption of linear optics quantum computation on almost arbitrary states of light with asymptotically perfect security.http://arxiv.org/ abs/1902.10972, Feb 2019

    1902 arXiv

  55. [63]

    C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers, Sys- tems and Signal Processing , volume 175, page 8. New York, 1984

    1984

  56. [64]

    Insecurity of quantum secure computa- tions

    Hoi-Kwong Lo. Insecurity of quantum secure computa- tions. Phys. Rev. A , 56:1154–1162, Aug 1997

    1997

  57. [65]

    Complete insecurity of quantum protocols for classical two-party computation

    Harry Buhrman, Matthias Christandl, and Christian Schaffner. Complete insecurity of quantum protocols for classical two-party computation. Phys. Rev. Lett. , 109:160501, Oct 2012

    2012

  58. [66]

    Impossibility of secure two-party classical computation

    Roger Colbeck. Impossibility of secure two-party classical computation. Phys. Rev. A , 76:062308, Dec 2007

    2007

  59. [67]

    Cheat sensitive quantum bit commitment

    Lucien Hardy and Adrian Kent. Cheat sensitive quantum bit commitment. Phys. Rev. Lett., 92:157901, Apr 2004

    2004

  60. [68]

    A quantum homomorphic encryption scheme for polynomial-sized circuits

    Li Yu. A quantum homomorphic encryption scheme for polynomial-sized circuits. http://arxiv.org/abs/1810. 01166, October 2018

    2018

  61. [69]

    C. H. Bennett, G. Brassard, C. Cr´ epeau, R. Jozsa, A. Peres, and W. K. Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky- Rosen channels. Phys. Rev. Lett. , 70:1895–1899, Mar 1993

    1993

  62. [70]

    D. P. DiVincenzo, M. Horodecki, D. W. Leung, J. A. Smolin, and B. M. Terhal. Locking classical correlations in quantum states. Phys. Rev. Lett., 92:067902, Feb 2004

    2004

  63. [71]

    Equivalence between two flavours of oblivious transfers

    Claude Cr´ epeau. Equivalence between two flavours of oblivious transfers. In Carl Pomerance, editor, Advances in Cryptology — CRYPTO ’87 , pages 350–354, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg

    1988

  64. [72]

    Founding cryptography on oblivious transfer

    Joe Kilian. Founding cryptography on oblivious transfer. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing , STOC ’88, pages 20–31, New York, NY, USA, 1988. ACM

    1988

  65. [73]

    Wolf and J

    S. Wolf and J. Wullschleger. Oblivious transfer and quan- tum non-locality. In Proceedings. International Sympo- sium on Information Theory, 2005. ISIT 2005. , pages 1745–1748, Sep. 2005

    2005

  66. [74]

    Hoi-Kwong Lo and H. F. Chau. Is quantum bit commit- ment really possible? Phys. Rev. Lett. , 78:3410–3413, Apr 1997

    1997

  67. [75]

    Unconditionally secure quantum bit commitment is impossible

    Dominic Mayers. Unconditionally secure quantum bit commitment is impossible. Phys. Rev. Lett. , 78:3414– 3417, Apr 1997

    1997

  68. [76]

    Per- fectly concealing quantum bit commitment from any quantum one-way permutation

    Paul Dumais, Dominic Mayers, and Louis Salvail. Per- fectly concealing quantum bit commitment from any quantum one-way permutation. In Bart Preneel, editor, Advances in Cryptology — EUROCRYPT 2000 , pages 300–315, Berlin, Heidelberg, 2000. Springer Berlin Hei- delberg

    2000

  69. [77]

    LEGO for two- party secure computation

    Jesper Buus Nielsen and Claudio Orlandi. LEGO for two- party secure computation. In Proceedings of the 6th The- ory of Cryptography Conference on Theory of Cryptogra- phy, TCC ’09, page 368–386, Berlin, Heidelberg, 2009. Springer-Verlag

    2009

  70. [78]

    Large family of quantum weak coin- flipping protocols

    Carlos Mochon. Large family of quantum weak coin- flipping protocols. Phys. Rev. A , 72:022341, Aug 2005

    2005

  71. [79]

    Quantum bit com- mitment and coin tossing protocols

    Gilles Brassard and Claude Cr´ epeau. Quantum bit com- mitment and coin tossing protocols. In Proceedings of the 10th Annual International Cryptology Conference on Ad- vances in Cryptology, CRYPTO ’90, page 49–61, Berlin, Heidelberg, 1990. Springer-Verlag

    1990

  72. [80]

    Quantum nonlocal- ity as an axiom

    Sandu Popescu and Daniel Rohrlich. Quantum nonlocal- ity as an axiom. Foundations of Physics , 24(3):379–385, Mar 1994

    1994

  73. [81]

    Information causality as a physical principle

    Marcin Pawlowski, Tomasz Paterek, Dagomir Kasz- likowski, Valerio Scarani, Andreas Winter, and Marek ˙Zukowski. Information causality as a physical principle. Nature, 461:1101–1104, 2009

    2009

  74. [82]

    Masanes, A

    Ll. Masanes, A. Acin, and N. Gisin. General properties of nonsignaling theories. Phys. Rev. A , 73:012112, Jan 2006

    2006

  75. [83]

    More efficient oblivious transfer exten- sions

    Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. More efficient oblivious transfer exten- sions. Journal of Cryptology , 30(3):805–858, Jul 2017

    2017

  76. [84]

    Cr´ epeau and J

    C. Cr´ epeau and J. Kilian. Achieving oblivious trans- fer using weakened security assumptions. In [Proceedings 1988] 29th Annual Symposium on Foundations of Com- puter Science, pages 42–52, Oct 1988

    1988

  77. [85]

    Quantum bit commitment from a phys- ical assumption

    Louis Salvail. Quantum bit commitment from a phys- ical assumption. In Hugo Krawczyk, editor, Advances in Cryptology — CRYPTO ’98 , pages 338–353, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg

    1998

  78. [86]

    Artur K. Ekert. Quantum cryptography based on Bell’s theorem. Phys. Rev. Lett., 67:661–663, Aug 1991. 22 Appendix A: An entanglement-based version of Protocol 1 In this appendix we introduce Protocol 11 which is a variant of Protocol 1 based on initial entanglement. It contain...

    1991

  79. [87]

    Bob generates and distributes the entanglement

    After some procedure of generating EPR states and testing them, the two parties share four tested EPR pairs. Bob generates and distributes the entanglement. The testing procedure, which may contain aborts on failure of passing the tests, is discussed in the text

  80. [88]

    (The steps 3 and 4 performed by Bob can be done concurrently with the Step 2 performed by Alice.) Alice generates a random bit s. If s = 0, she measures the four qubits in her part of the EPR pairs in the Z basis, and records the measurement outcome on the first qubit as x; if ...

  81. [89]

    If y = 0, Bob does a CNOT gate on his first two qubits, with the first qubit being the control qubit

  82. [90]

    Bob teleports his first two qubits to Alice, using the later two EPR pairs, while withholding part of the information about the measurement outcomes: he calculates the XOR of the four correction bits, and sends the resulting bit w to Alice. Bob calculates the XOR of the two bit...

  83. [91]

    decomposition

    Alice calculates her output bit: g⊕ (s·w). decomposition. The calculations assume projective mea- surements by Alice after she receives the message from Bob, although POVM measurements may give rise to a larger sum on the left-hand-side, and such weakness is remedied by the ca...

  84. [92]

    in”, and ends up in a qubit which is initially maxi- mally entangled with Bob’s qubit labeled “E

    for correcting an unwanted P gate due to a T gate in the circuit with certain prior Pauli corrections. In the figure, the input qubit starts from the position “in”, and ends up in a qubit which is initially maxi- mally entangled with Bob’s qubit labeled “E” [in the state 1√ 2(|...

Pith tools

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