Efficient Three-party Computation: An Information-theoretic Approach from Cut-and-Choose

Zhili Chen

REVIEW 3 major objections 4 minor 13 references

Efficient Three-party Computation: An Information-theoretic Approach from Cut-and-Choose

T0 review · 3 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 Cut-and-choose, previously confined to computationally secure garbled-circuit protocols, can be adapted to information-theoretically secure three-party computation with cheating probability $2^{-s}$ at near-semi-honest cost.

desk verdict The cut-and-choose-in-IT idea is genuinely new, but the protocol as written has a correctness bug in its input-selection step and the security proof is a sketch, so the main claim is not established. read the letter →

arxiv 1908.03718 v1 pith:MOH34BKN submitted 2019-08-10 cs.CR

Zhili Chen This is my paper · ORCID

classification cs.CR

keywords securemultipartycomputationthree-partyinformation-theoreticsecuritycut-and-choosemaliciousadversariessecretsharingcheatingprobabilitycovert

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 tries to show that cut-and-choose, a technique tied until now to computationally secure garbled-circuit protocols, can be transplanted into the information-theoretic setting for secure three-party computation. It constructs a protocol that runs a semi-honest three-party computation $s$ times in parallel, with a secret-shared cut-and-choose indicator deciding which runs are checked and which runs produce the output. The central claim, Theorem 3, is that the resulting protocol is secure against one malicious party and has cheating probability $2^{-s}$. If this holds, it would be a maliciously secure 3PC protocol whose computation cost is only a small constant above the best semi-honest protocols and whose communication rounds are roughly circuit depth plus a constant, with no cryptographic assumptions.

What carries the argument

The load-bearing object is the input-selection circuit driven by a secret-shared cut-and-choose indicator. The three parties hold XOR shares of an $s$-bit string $c$; each run $j$ is assigned to verification or output according to $c(j)$, but no individual party knows $c$. The circuit combines, in each run, the permuted input pair with the indicator bit through Eq. (8), selecting the true input exactly when $c(j)=0$. This selection is performed with the same XOR and AND operations as the underlying semi-honest protocol, preserving information-theoretic security. Around it sit two supporting tools: XOR secret sharing, which makes the parallel circuit computation linear, and a three-party commitment scheme built from threshold secret sharing, which is perfectly hiding and perfectly binding and lets the parties commit to indicator shares and to every wire share of every run.

What would settle it

A concrete test is to specify a one-party adversarial strategy that behaves honestly in every checked run ($c(j)=1$) but, in output runs ($c(j)=0$), swaps in a different input share or different gate behaviour and then makes all output values agree. If such a strategy passes the protocol's checks with probability greater than $2^{-s}$ over the random choice of $c$, then Theorem 3's bound fails.

Watch

Extended reading notes

Core claim

The central discovery is a compilation of the semi-honest three-party protocol into a maliciously secure one by repeating it $s$ times and using a secretly shared cut-and-choose indicator $c$. Each party prepares a true input and a random input, then makes $s$ permuted pairs of these two versions. An input-selection circuit computes $x_{ij} = (x_i^{\sigma_{ij}} \oplus x_i^{1-\sigma_{ij}})(c(j) \oplus \sigma_{ij}) \oplus x_i^{\sigma_{ij}}$, so that run $j$ uses true inputs when $c(j)=0$ and random inputs when $c(j)=1$, while no party learns $c$. Runs with $c(j)=1$ are opened and checked for correct input and correct circuit computation; runs with $c(j)=0$ are required only to agree on a common output. Because all inputs, indicator shares, and transcripts are committed, the author argues that a cheating party must guess the whole indicator $c$, giving cheating probability $2^{-s}$ as stated in Theorem 3.

Load-bearing premise

The load-bearing premise is that the only way a malicious party can cheat without being detected is to guess the entire $s$-bit cut-and-choose indicator $c$; the proof in Section 4.2 asserts this without building a simulator or analysing strategies that cheat only in output runs, where true inputs are never checked.

Editorial extensions

If this is right

A maliciously secure 3PC protocol would exist with no cryptographic assumptions, achieving cheating probability $2^{-s}$ for any statistical parameter $s$.
Communication rounds would scale with circuit depth plus a constant, whereas VSS-based malicious 3PC protocols typically need several times the circuit depth.
Computation cost would be only a small constant worse than the semi-honest baseline, since the overhead is $s$ parallel runs of the same XOR/AND protocol.
Setting $s=8$ yields a covertly secure protocol that catches at least 99.5% of cheating attempts, a cheap option for practice.
The construction shows a template for applying cut-and-choose inside secret-sharing-based computation, not only inside garbled circuits.

Reading between the lines

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

The proof's missing simulator for output-run cheating suggests the effective security could be weaker than $2^{-s}$; an adversary that modifies only runs later revealed as output runs might evade checks because those runs' input shares are never opened.
The same privately permuted true/random input pairs with a shared selection bit could be adapted to $n$-party honest-majority secret sharing, though the consistency checks would need to scale with the number of parties.
An inexpensive empirical check would be to implement the $s=8$ covert variant with a corrupted party deviating in a single gate across all runs and measure how often the deviation is caught; that rate would test the claimed deterrent against the actual protocol.

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

The genuinely new thing here is the attempt to bring cut-and-choose into the information-theoretic 3PC setting, and the trick of using a secret-shared cut-and-choose indicator to select true vs. random inputs is a real design idea. If the protocol were fixed, the efficiency story—malicious security at close to semi-honest cost—would be worth taking seriously. The paper also engages the right background literature and does not fit parameters or invent entities. So there is a kernel of value.

The problem is that the protocol does not actually implement its own specification. In Fig. 6, the loop over i updates the same secret-shared [c(j)] inside the input-selection step. After processing i=1,2,3, the effective shared selection bit is c(j)⊕σ_1j⊕σ_2j⊕σ_3j, not c(j)⊕σ_ij as Eq. (8) requires. Party 1 gets the intended bit, but party 2 uses c⊕σ_1⊕σ_2 and party 3 uses c⊕σ_1⊕σ_2⊕σ_3. Since the σ_ij are random and private, honest parties will, with high probability, feed random inputs into output runs and true inputs into check runs. The protocol is wrong for honest parties before any adversary even acts. This is not a missing simulator; it is an internal contradiction between Eq. (8) and the pseudocode.

Even if that bug were repaired, the security proof of Theorem 3 is not a proof. It asserts that any successful cheat reduces to guessing c, but it never constructs the output-generation simulator and never gives a reduction bounding the cheating probability. A malicious party could deviate in output runs where inputs are not checked, and the proof does not analyze that case. The internal inconsistency about whether the true input x0_i is committed (Fig. 5 says no, Fig. 6 says yes) is minor by comparison but adds to the impression that the draft was not carefully checked.

Who gets value from this? Researchers working on cut-and-choose or IT MPC might use the high-level idea as a starting point, but they should not cite it as a secure protocol. It deserves a serious referee—the core question is worth examining—but the current version should not be accepted; it needs a corrected input-selection step, a real simulator, and a proper security reduction.

Referee Report

3 major / 4 minor

Summary. The paper proposes an information-theoretically secure three-party computation (3PC) protocol against one malicious party, built on the cut-and-choose paradigm. Each party prepares s copies of its input, each containing a true input and a random input in a privately permuted order, and the parties share a cut-and-choose indicator c that determines, per run, whether true or random inputs are used. The protocol runs s parallel evaluations of the circuit using a semi-honest ITSEC-style protocol, commits to all transcripts, and then verifies the runs indicated by c while using the remaining runs for output. The paper claims perfect binding/hiding from a Shamir-based commitment scheme and claims that the protocol is secure with cheating probability 2^{-s}.

Significance. If correct, the result would be conceptually interesting: it would be the first information-theoretically secure 3PC protocol from cut-and-choose, with communication rounds linear in circuit depth and a small constant factor over semi-honest protocols. The idea of a secret-shared cut-and-choose indicator combined with privately permuted inputs is worth exploring, and the commitment scheme section is straightforward. However, the central protocol as written is not even correct for honest parties because the input-selection step does not implement the intended equation, and the security proof does not provide a simulator or a reduction for the claimed 2^{-s} cheating bound. The paper therefore does not establish its main claim.

major comments (3)

[Section 4.1, Fig. 6 ('Select proper inputs')] The pseudocode does not implement Eq. (8). In Eq. (8), party i's input in run j is selected using the bit c(j) ⊕ σ_{ij}, where σ_{ij} is private to party i. In Fig. 6, however, the loop 'For i ∈ {1,2,3}' updates the same shared value [c(j)] by executing '[c(j)]_k ← [c(j)]_k ⊕ σ_{ij}' when i = k. Thus after processing i = 1, the shared value is c(j) ⊕ σ_{1j}; after i = 2 it is c(j) ⊕ σ_{1j} ⊕ σ_{2j}; and after i = 3 it is c(j) ⊕ σ_{1j} ⊕ σ_{2j} ⊕ σ_{3j}. Consequently, for i = 2 and i = 3 the effective selection bit is not c(j) ⊕ σ_{ij}, and honest executions with c(j) = 0 will generally not select the true inputs x^0_i. Since random inputs are not equal to true inputs, the 'Check random inputs' step will cause honest parties to abort, and even if it did not, the protocol could output the function evaluated on wrong inputs. This is a correctness failure of the protocol for honest parties, independent of adversarial behavior, so Theorem 3 cannot hold for the protocol as written.
[Section 4.2, Theorem 3] The proof of Theorem 3 does not contain a formal simulator for a malicious corrupted party. After the circuit-computation phase, the proof merely asserts that the output-generation phase 'makes sure' that deviations are detected and that a successful cheat 'has to guess the value of c', concluding a cheating probability of 2^{-s}. No reduction is given from a cheating adversary to guessing c, and no analysis is provided for strategies that modify only output runs, where true inputs are not checked and only equality of the reconstructed outputs is verified. The simulation arguments for input sharing and circuit computation treat the honest parties' messages as uniformly random, but they do not address a malicious P1 who sends inconsistent shares, cheats in AND-gate computations, or equivocates at the commitment-opening stage. The claimed 2^{-s} bound is therefore unsupported by the presented proof.
[Section 4.1, Fig. 5 vs Fig. 6] There is an internal inconsistency about whether the true input x^0_i is committed. Figure 5, step 5, states 'Commit to x^1_i and [c]_i', while the protocol text in Fig. 6 states that after input preparation Pi holds 'commitments to [x^0_i], x^1_i, [c]_i'. The surrounding text in Section 4.1 also says only that Pi commits to x^1_i and [c]_i. If x^0_i is not committed, the protocol does not bind a malicious party to its true input in the output runs; if it is committed, the preparation phase in Fig. 5 needs to include it. This discrepancy affects the security argument and must be resolved.

minor comments (4)

[Throughout] There are numerous typos and grammatical errors, including 'comparied', 'yeilding', 'convert adversaries' (should be 'covert adversaries'), 'fuction', and 'mensioned'. A careful proofreading pass is needed.
[Section 2.4, Eq. (3)] The UC security definition states that the distinguishing advantage is exactly 0 for all environments, which is perfect security, but the paper later analyzes statistical cheating probability 2^{-s}. The relationship between the perfect indistinguishability requirement in Eq. (3) and the statistical bound claimed in Theorem 3 should be clarified.
[Section 4.1, Fig. 6] The notation [t_{ij}c(j)]_k is used without defining whether the multiplication is bitwise or field multiplication; given that the protocol uses XOR secret sharing over bit strings, the AND-gate multiplication pattern should be stated consistently for this step.
[Section 1.1] The phrase 'against convert adversaries' appears to be a typo for 'covert adversaries'; if covert security is intended, the formal definition and deterrent parameter should be stated precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the cut-and-choose construction is not equivalent to its inputs, though the security proof has independent gaps.

full rationale

I walked the claimed derivation chain. The malicious 3PC protocol compiles an in-paper semi-honest 3PC protocol (Theorem 1, a variant of ITSEC from [CHC15]) using the standard cut-and-choose paradigm. The citation to the author's prior work is not the load-bearing justification: the semi-honest security is proved in Theorem 1 inside the paper, and the malicious protocol does not assume Theorem 3 in its construction. The input-selection identities in Eqs. (4)-(8) are algebraic manipulations of the definition x_ij = (x^0_i xor x^1_i)c(j) xor x^0_i; they do not sneak the claimed 2^{-s} cheating bound into the protocol. The cheating-probability conclusion in Section 4.2 is asserted rather than derived by a simulator, and the Fig. 6 pseudocode appears inconsistent with Eq. (8) because the same [c(j)] share is updated by each party in turn; however, these are correctness and proof-completeness defects, not circularity. No fitted parameter is renamed as a prediction, no uniqueness theorem from prior self-work is invoked to force a choice, and no known result is repackaged under new coordinates. Self-citation to [CHC15] is prior published work and is supplemented by an in-paper proof, so it does not make the derivation circular. Accordingly, the paper has no significant circularity (score 0), with the caveat that the security theorem's proof is unsupported and the protocol pseudocode may not realize Eq. (8).

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

The protocol relies on standard secret sharing and a self-cited semi-honest base protocol. No fitted constants or invented primitives appear. The main uncharged assumptions are the security of the base ITSEC variant and the implicit reduction of all malicious behavior to guessing c.

assumptions (3)

domain assumption The underlying semi-honest 3PC protocol πsem_3PC, a variant of ITSEC from [CHC15], is information-theoretically secure.
Invoked as the basis for the compilation in Section 3, Theorem 1; the proof is a simulation sketch and the protocol is from the author's own prior work.
standard math Shamir secret sharing with degree 1 provides perfect binding and hiding for the three-party commitment scheme.
Used in Section 4.2, Theorem 2; the scheme requires that any two shares determine the secret, so degree t=1 is implicitly assumed but not stated explicitly in Fig. 4.
domain assumption The computed function is represented exclusively with XOR and AND gates.
Stated in Section 2; the protocol computes gate-by-gate over boolean wires, so non-boolean arithmetic is out of scope.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient Three-party Computation: An Information-theoretic Approach from Cut-and-Choose." pith.science (2026). https://pith.science/paper/MOH34BKN

@misc{pith2026190803718,
  author       = {Pith},
  title        = {Pith review of: Efficient Three-party Computation: An Information-theoretic Approach from Cut-and-Choose},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MOH34BKN}},
  note         = {Machine review of arXiv:1908.03718}
}

abstract

As far as we know, the literature on secure computation from cut-and-choose has focused on achieving computational security against malicious adversaries. It is unclear whether the idea of cut-and-choose can be adapted to secure computation with information-theoretic security. In this work we explore the possibility of using cut-and-choose in information theoretic setting for secure three-party computation (3PC). Previous work on 3PC has mainly focus on the semi-honest case, and is motivated by the observation that real-word deployments of multi-party computation (MPC) seem to involve few parties. We propose a new protocol for information-theoretically secure 3PC tolerating one malicious party with cheating probability $2^{-s}$ using $s$ runs of circuit computation in the cut-and-choose paradigm. The computational cost of our protocol is essentially only a small constant worse than that of state-of-the-art 3PC protocols against a semi-honest corruption, while its communication round is greatly reduced compared to other maliciously secure 3PC protocols in information-theoretic setting.

Figures

Figures reproduced from arXiv: 1908.03718 by the authors.

**Figure 1.** Each party generates s copies of permuted inputs with a privately generated permutation vector. The proper inputs are then computed from these permuted inputs according to a cut-and-choose indicator. In order to address the second challenge, the permutation randomness of the two input versions of each party is privately generated, and unknown to any other party. Thus, the shared inputs cannot be altered, without bei… view at source ↗

**Figure 2.** ITSEC Variant 3PC Protocol P1 P2 P3  1 11 ([ ( )] ,[ ( )] , ) a br  2 22 ([ ( )] ,[ ( )] , ) a br  3 33 ([ ( )] ,[ ( )] , ) a br  3 33 ([ ( )] ,[ ( )] , ) a br  1 11 ([ ( )] ,[ ( )] , ) a br  2 22 ([ ( )] ,[ ( )] , ) a br [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** The Communication Pattern for AND Gate Computation: [δ(a)δ(b)]i = [δ(a)]i[δ(b)]i ⊕ [δ(a)]i[δ(b)]h(i−1) ⊕ [δ(a)]h(i−1)[δ(b)]i ⊕ ri ⊕ rh(i−1) for i ∈ {1, 2, 3}. Note that this communication pattern uses no broadcast channels [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Commitment Scheme based on Shamir’s Secret Sharing The detailed protocol of input preparation is shown in [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

**Figure 5.** Figure 5: Input Preparation of Pi (i ∈ {1, 2, 3}) for each run to select proper inputs using σij , Iij and c with i ∈ {1, 2, 3} and j ∈ {1, · · · , s}. Since for each σij , Iij = (x σij i , x 1−σij i ), we have x 0 i = (x σij i ⊕ x 1−σij i )σij ⊕ x σij i (4) x 1 i = (x σij i ⊕ x…

**Figure 6.** Figure 6: Our 3PC protocol from cut-and-choose in the presence of a malicious adversary corrupting a party If P1 is corrupted, the honest verifiers P2 and P3 will hold two shares of the committed data d, which will uniquely determine d due to Shamir’s secret sharing, and P1 cann…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[3]

CHC15. Z. Chen, L. Huang, and L. Chen. ITSEC: An information-theoretically secure framework for truthful spectrum auctions. In Proc. of INFOCOM , pages 2065–2073,

work page
[6]

Marcel Keller, Peter Scholl, and Nigel P Smart

Lecture Notes in Computer Science: Authors’ Instructions 17 KSS13. Marcel Keller, Peter Scholl, and Nigel P Smart. An architecture for prac- tical actively secure mpc with dishonest majority. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security , pages 549–560. ACM,

work page 2013
[7]

Yehuda Lindell

Lin13. Yehuda Lindell. Fast cut-and-choose based protocols for malicious and covert adversaries. In Advances in Cryptology–CRYPTO 2013 , pages 1–

work page 2013
[9]

Payman Mohassel and Ben Riva

MR13. Payman Mohassel and Ben Riva. Garbled circuits checking garbled cir- cuits: More eﬃcient and secure two-party computation. In Advances in Cryptology–CRYPTO 2013, pages 36–53. Springer,

work page 2013
[11]

Chih-hao Shen et al

S+13. Chih-hao Shen et al. Fast two-party secure computation with minimal assumptions. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security , pages 523–534. ACM,

work page 2013
[1979]

David P Woodruﬀ

Woo07. David P Woodruﬀ. Revisiting the eﬃciency of malicious two-party com- putation. In Advances in Cryptology-EUROCRYPT 2007 , pages 79–96. Springer,

work page 2007
[2007]

Yao86. A. C.-C. Yao. How to generate and exchange secrets. In Proc. FOCS, 1986

work page 1986
[2008]

Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway

BHR12. Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In Proceedings of the 2012 ACM conference on Computer and communications security , pages 784–796. ACM,

work page 2012

Show all 13 references

[2009]

Chih-hao Shen et al

S+11. Chih-hao Shen et al. Two-output secure computation with malicious ad- versaries. In Advances in Cryptology–EUROCRYPT 2011, pages 386–405. Springer,

2011
[2011]

Yan Huang, Jonathan Katz, and David Evans

HKE13. Yan Huang, Jonathan Katz, and David Evans. Eﬃcient secure two-party computation using symmetric cut-and-choose. In Advances in Cryptology– CRYPTO 2013, pages 18–35. Springer,

2013
[2012]

Dan Bogdanov, Sven Laur, and Jan Willemson

BLW08. Dan Bogdanov, Sven Laur, and Jan Willemson. Sharemind: A framework for fast privacy-preserving computations. InComputer Security-ESORICS 2008, pages 192–206. Springer,

2008
[2013]

Yehuda Lindell and Benny Pinkas

LP07. Yehuda Lindell and Benny Pinkas. An eﬃcient protocol for secure two- party computation in the presence of malicious adversaries. In Advances in Cryptology-EUROCRYPT 2007 , pages 52–78. Springer,

2007
[2015]

Seung Geol Choi, Jonathan Katz, Alex J Malozemoﬀ, and Vassilis Zikas

CKMZ14. Seung Geol Choi, Jonathan Katz, Alex J Malozemoﬀ, and Vassilis Zikas. Eﬃcient three-party computation from cut-and-choose. In Advances in Cryptology–CRYPTO 2014, pages 513–530. Springer,

2014

Pith tools

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

[1] [3]

CHC15. Z. Chen, L. Huang, and L. Chen. ITSEC: An information-theoretically secure framework for truthful spectrum auctions. In Proc. of INFOCOM , pages 2065–2073,

work page

[2] [6]

Marcel Keller, Peter Scholl, and Nigel P Smart

Lecture Notes in Computer Science: Authors’ Instructions 17 KSS13. Marcel Keller, Peter Scholl, and Nigel P Smart. An architecture for prac- tical actively secure mpc with dishonest majority. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security , pages 549–560. ACM,

work page 2013

[3] [7]

Yehuda Lindell

Lin13. Yehuda Lindell. Fast cut-and-choose based protocols for malicious and covert adversaries. In Advances in Cryptology–CRYPTO 2013 , pages 1–

work page 2013

[4] [9]

Payman Mohassel and Ben Riva

MR13. Payman Mohassel and Ben Riva. Garbled circuits checking garbled cir- cuits: More eﬃcient and secure two-party computation. In Advances in Cryptology–CRYPTO 2013, pages 36–53. Springer,

work page 2013

[5] [11]

Chih-hao Shen et al

S+13. Chih-hao Shen et al. Fast two-party secure computation with minimal assumptions. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security , pages 523–534. ACM,

work page 2013

[6] [1979]

David P Woodruﬀ

Woo07. David P Woodruﬀ. Revisiting the eﬃciency of malicious two-party com- putation. In Advances in Cryptology-EUROCRYPT 2007 , pages 79–96. Springer,

work page 2007

[7] [2007]

Yao86. A. C.-C. Yao. How to generate and exchange secrets. In Proc. FOCS, 1986

work page 1986

[8] [2008]

Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway

BHR12. Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In Proceedings of the 2012 ACM conference on Computer and communications security , pages 784–796. ACM,

work page 2012