{"id":"ef873d9e-f25e-4d77-a26d-a316f9e56c40","arxiv_id":"1908.03718","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proposes an information-theoretically secure three-party computation protocol using cut-and-choose, claiming malicious security with 2^{-s} cheating probability.","lead":"This paper adapts the cut-and-choose technique, standard in garbled-circuit secure computation, to information-theoretically secure three-party computation with one malicious party. It claims a protocol with cheating probability 2^{-s} at a small constant overhead over semi-honest protocols, but the security proof is asserted rather than derived.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The input-selection step in Fig. 6 does not implement Eq. (8): the same [c] share is updated with each σ_i in turn, so party i's effective selection bit is c⊕σ_1⊕...⊕σ_i instead of c⊕σ_i; honest executions can feed random inputs into output runs and output wrong values.","rationale":"The most load-bearing point is not the absence of a simulator in Theorem 3's proof, but a concrete correctness failure in the protocol as written. Eq. (8) in Section 4.1 requires the selection bit for party i to be c(j)⊕σ_ij. The pseudocode in Fig. 6, step 2, accumulates the σ updates into the same [c(j)] sharing, so by the time party i's input is selected the effective bit is c(j)⊕σ_1j⊕...⊕σ_ij. Except for i=1, this is the wrong bit in general. Since σ_i are random and secret, honest parties will often select random inputs for output runs and true inputs for check runs, breaking both correctness and the claimed cut-and-choose argument. This is an internal inconsistency, so the reader's final reject verdict is correct, though for a different reason than the reader's weakest_assumption. No further concern about simulator omission is needed to reject; the protocol fails on honest execution. A fix would require a fresh copy of [c] for each party or a different selection circuit, but that is not the submitted protocol.","tokens_in":13918,"tokens_out":10353,"duration_ms":101085,"concrete_test":"Trace the protocol for s=1 and a single AND gate f(a,b,c)=a∧b∧c with true inputs x0_1=x0_2=x0_3=1, random inputs x1_1=x1_2=x1_3=0, σ=(1,0,0), and c=0. Eq. (8) says the output run should use (1,1,1) and output 1. In Fig. 6, after P1 adds σ_1 the shared selection bit is 1; after P2 and P3 it remains 1, so P2 and P3 select their random inputs 0. The honest parties compute 0, not 1, and with s=1 the consistency check over output runs does not catch it. A still simpler analytical check: derive the effective selection bit for party i after the loop and compare it with c(j)⊕σ_ij; they differ whenever σ_1⊕...⊕σ_{i-1}=1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.1's protocol (Fig. 6, 'Select proper inputs') is meant to realize Eq. (8): x_ij = (x^{σ_ij}_i ⊕ x^{1-σ_ij}_i)(c(j) ⊕ σ_ij) ⊕ x^{σ_ij}_i. However, the pseudocode updates the same secret-shared [c(j)] inside the loop over i: for each i, P_i adds σ_ij to its own share, so after processing i=1,2,3 the shared value is c(j)⊕σ_1j⊕σ_2j⊕σ_3j, not c(j)⊕σ_ij. For i=1 the selection bit is c⊕σ_1; for i=2 it is c⊕σ_1⊕σ_2; for i=3 it is c⊕σ_1⊕σ_2⊕σ_3. Each party's input is therefore selected with the wrong bit unless the preceding σ's happen to cancel. Since the σ_ij are random and private, the honest execution of Fig. 6 does not, in general, use true inputs in output runs (c(j)=0) or random inputs in check runs; the protocol does not even compute the intended function correctly. This is an internal inconsistency between Eq. (8) and the pseudocode, not merely a missing simulator. Consequently Theorem 3 cannot be true for the protocol as written, because the protocol fails correctness for honest parties before any adversarial behavior is considered.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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}.","tokens_in":14230,"tokens_out":5594,"duration_ms":56343,"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":[{"comment":"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":"Section 4.1, Fig. 6 ('Select proper inputs')"},{"comment":"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":"Section 4.2, Theorem 3"},{"comment":"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.","section":"Section 4.1, Fig. 5 vs Fig. 6"}],"minor_comments":[{"comment":"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":"Throughout"},{"comment":"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":"Section 2.4, Eq. (3)"},{"comment":"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":"Section 4.1, Fig. 6"},{"comment":"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.","section":"Section 1.1"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nEven 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.\n\nWho 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.","headline":"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.","tokens_in":14713,"tokens_out":2677,"would_cite":false,"duration_ms":28958,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["secure multiparty computation","three-party computation","information-theoretic security","cut-and-choose","malicious adversaries","secret sharing","cheating probability","covert security"],"falsifier":"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.","tokens_in":13722,"feed_emoji":"🔐","tokens_out":11895,"duration_ms":112064,"temperature":0.7,"pith_summary":"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.","feed_headline":"Cut-and-choose reaches information-theoretic 3PC","feed_subtitle":"Repeating a secret-shared computation s times catches a cheating party with probability 2^{-s}, at near-semi-honest cost.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the semi-honest ITSEC 3PC protocol that the construction repeats $s$ times as its base.","marker":"[CHC15]"},{"why":"Provides the threshold secret sharing used in the perfectly hiding and perfectly binding commitment scheme.","marker":"[Sha79]"},{"why":"Introduces the cut-and-choose paradigm that the paper transplants into the information-theoretic setting.","marker":"[LP07]"},{"why":"Establishes prior 3PC from cut-and-choose in the garbled-circuit setting, the approach this paper adapts.","marker":"[CKMZ14]"},{"why":"Serves as the reference for the $2^{-s}$ cheating probability and for converting the protocol into covert security with fixed small $s$.","marker":"[Lin13]"}],"fun_headline_variants":["Cut-and-choose gives info-theoretic security for 3PC","Malicious 3PC at semi-honest cost via repeated cut-and-choose","3PC with cheating probability 2^{-s} from cut-and-choose","Info-theoretic 3PC: repeat circuit s times to catch cheaters","Three-party computation goes info-theoretic with cut-and-choose"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Cut-and-choose gives info-theoretic security for 3PC","Malicious 3PC at semi-honest cost via repeated cut-and-choose","3PC with cheating probability 2^{-s} from cut-and-choose","Info-theoretic 3PC: repeat circuit s times to catch cheaters","Three-party computation goes info-theoretic with cut-and-choose"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000345,"raw_usage":{"total_tokens":1902,"prompt_tokens":965,"completion_tokens":937,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":839}},"tokens_in":581,"tokens_out":937,"duration_ms":8557,"temperature":1.0,"reasoning_tokens":839,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:04:45.008328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}