{"id":"f4a0bb22-2c72-419d-9c6e-8721486e591b","arxiv_id":"2603.02071","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A committee-based transformation gives setup-free asynchronous common coins with O~(n^2.5) (perfect) and O~(n^{7/3}) (hash-based) communication against Θ(n) adaptive byzantine faults.","lead":"By running many small committees that each generate their own random bit and then publishing those bits cheaply, the paper converts expensive 'strong' random coins into cheaper 'weak' ones. This yields the first setup-free asynchronous common coins that use subcubic communication against a linear number of adaptive faults.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.1 assumes concurrent composability of Cstr that Definition 1.1 does not state; Lemma 5.4's independent b_i lacks support.","rationale":"The reader's weakest_assumption already identifies the reliance on external strong coins under concurrent composition. I agree that this is the most load-bearing concern. The paper's Lemma 5.4 needs the committee coin values to be independent; Definition 1.1 only gives per-instance fairness, and Section 6's instantiation is via cited black-box frameworks whose composability is not established in the text. This is not an ad hominem or an appeal to consensus: it is a precise gap between the theorem's stated hypothesis and the proof's use of that hypothesis. If the external AVSS-based strong coins are in fact UC/standalone composable in the required sense, the central claim survives; if not, the theorem's statement needs an additional composability hypothesis and the headline 'first setup-free subcubic coins' is not proven. Because this can likely be repaired by a more precise model and/or a composability audit of [22], I would not reject the paper but would make acceptance conditional on that verification. The minor typos and the false σ=0 edge case in Lemma 5.2 are not load-bearing.","tokens_in":22946,"tokens_out":21135,"duration_ms":204081,"concrete_test":"Re-formalize Theorem 2.1 in a model where Cstr is assumed to satisfy the ideal common-coin functionality from [14] (fresh, independent uniform value per instance) instead of the property-based Definition 1.1, and re-derive Lemma 5.4. If the step 'the bits b1,...,bq are independent' still requires an additional assumption, then audit the Monte-Carlo strong coin of [22] (as instantiated with [1] and [6]) for q-concurrent, overlapping-committee adaptive security: either prove a composability theorem for those AVSS-based coins or exhibit two committees whose outputs are correlated conditioned on the good events. A negative result would require adding a concurrency assumption to Theorem 2.1.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The transformation's proof of fairness, Lemma 5.4, couples each committee Qi with an independent uniformly random bit bi and writes X = sum bi, then applies the anti-concentration bound Lemma 5.2. This requires that the q strong-coin instances produce mutually independent common outputs. Definition 1.1, however, only gives per-instance δ-fairness: for each instance, with probability at least δ the honest outputs equal some fresh uniform v. It does not assert, nor prove, that running q instances on overlapping committees under one adaptive adversary yields independent v_i. The proof of Lemma 5.4 simply asserts 'where the bits b1,...,bq for the q committees are independent,' and the text's remark that this can be formalized with an ideal common-coin functionality [14] is not a derivation: the cited functionality would provide the needed independence only if Cstr realizes it under concurrent composition, which is not stated in Definition 1.1 and not proved for the external strong coins used in Section 6 ([22], [1], [6]). If the adversary can correlate the committee outputs—for instance, by corrupting parties that appear in multiple committees after learning one committee's output—X may be far more concentrated than binomial, and the claimed fairness bound (1-(1-δ)q-z) can fail even when every individual committee is δ-fair. This is the load-bearing step of the central claim: without independence of the committee coin values, the virtual-Ben-Or argument collapses, and the subcubic costs are not justified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies asynchronous common coin tossing among n parties with an adaptive byzantine adversary and no PKI/setup. Its main contribution is a committee-based transformation T(Cstr,z,k,ε,α) that takes a δ-fair \"strong\" binary common coin Cstr costing O~(n^k) communication and produces a weaker binary coin costing O~(ε^{-2k} n^{3-2/k}) communication, while sacrificing an εn fraction of fault tolerance and losing only an arbitrarily small constant of fairness. The construction fixes q deterministic committees, runs Cstr inside each committee, publishes the resulting bits through a sparse crusader-agreement-based Publish protocol, and then aggregates committee outputs in a virtual Ben-Or style majority. The paper instantiates the strong coin with AVSS-based protocols from prior work to obtain a perfectly secure coin Cperfect for t≤(1/4−ε)n with O~(n^{2.5}) communication, and a hash-based cryptographic coin Ccrypto for t≤(1/3−ε)n with O~(n^{7/3}) communication. If the proof were complete, these would be the first setup-free asynchronous common coins with o(n^3) communication against Θ(n) adaptive byzantine faults.","tokens_in":23307,"tokens_out":19669,"duration_ms":204088,"significance":"The claimed result is significant: breaking the O(n^3) communication barrier for setup-free, PKI-free asynchronous common coins against Θ(n) adaptive faults would be a meaningful step, and the paper gives explicit complexity tradeoffs as well as concrete instantiations. The committee-based transformation is elegant, and the combinatorial lemmas (Lemma 4.1, Lemma 5.1, Lemma 5.2) are proved with standard probabilistic and anti-concentration arguments rather than being black-boxed. However, two load-bearing gaps in the current write-up prevent the result from being established as stated: the proof requires a joint independence/composability property of the strong coin that Definition 1.1 does not supply, and the liveness argument for the final aggregation step is inconsistent with the paper's own strongly adaptive adversary model. The paper is a good candidate for publication after these issues are repaired.","major_comments":[{"comment":"The proof of Lemma 5.4 asserts: 'where the bits b1,...,bq for the q committees are independent.' This independence is load-bearing: Lemma 5.2 is applied to X = Σ bi to obtain anti-concentration. But Definition 1.1 only gives, per instance, a probability at least δ that the honest outputs equal a fresh uniform bit; it does not give a joint distribution over q concurrent instances on overlapping committees under one adaptive adversary. The cited ideal common-coin functionality [14] would supply the needed independence only if Cstr is proved to realize that functionality under concurrent composition, which is neither stated in Definition 1.1 nor proved for the concrete coins from [22], [1], [6] used in Section 6. Without independence, the adversary could correlate committee outputs, and X could be far more concentrated than a binomial, so the bound Pr[∧_i g_i=1] ≥ 1−(1−δ)^q would not imply","section":"Section 5, Lemma 5.4 and proof of Theorem 2.1"},{"comment":"The liveness argument states that 'the parties in H* broadcasting bits ensures that every honest party i receives |H*| ≥ 2n/3+1 bits by the time T+5.' This is false in the paper's strongly adaptive model (Section 3), where the adversary may corrupt a party after it sends a message and drop that message. The adversary can use its t corruptions to drop messages from t of the n−t honest senders, leaving a given honest recipient with as few as n−2t delivered honest messages. For t > n/6, n−2t < 2n/3+1, so the adversary can prevent the condition on Line 19 from ever being satisfied even if all honest parties have sent their Line-16 broadcasts. This breaks the liveness guarantee of T(Cstr,z,k,ε,α). The final aggregation step needs a robust mechanism (or a different channel/liveness assumption) that survives adaptive message dropping.","section":"Section 5, liveness proof, Lines 16-20"}],"minor_comments":[{"comment":"The definition is explicitly informal and does not state any composition or independence property across concurrent instances. Since the proof of Theorem 2.1 needs a joint guarantee over q overlapping instances, the formal version of the assumption should be given in the theorem statement or the definition, not left to a parenthetical remark about ideal functionalities.","section":"Definition 1.1"},{"comment":"Both lemmas are proved by the probabilistic method, but the protocols require the parties to know the resulting bipartite graph and committee list. Please clarify whether an explicit/deterministic construction is intended, or whether the parties are assumed to have non-uniform advice; if the latter, this should be stated in the model and complexity claims.","section":"Appendix, Lemmas 4.1 and 5.1"},{"comment":"The expression 'O(n^{7/3}ε^{-6}z^{-3}n^{7/3} log n)' appears to contain a duplicated n^{7/3} factor; it should presumably be 'O(n^{7/3}ε^{-6}z^{-3} log n)'. The perfect-security expression also has an unmatched parenthesis.","section":"Section 6, Ccrypto complexity"},{"comment":"In the proof of Lemma 4.1, the sentence about a counterexample set B says vertices in V have at least Δ/2 neighbors 'in V'; this should be 'in B'.","section":"Appendix, Lemma 4.1 proof"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an important question and the proposed transformation is promising. However, the independence/concurrent-composition gap in Lemma 5.4 and the final-phase liveness gap are both load-bearing and must be fixed before the main claims are established. The liveness issue seems likely to be repairable with a different aggregation step or a clarified model; the fairness issue likely requires either a stronger theorem hypothesis or a composition proof for the cited AVSS-based strong coins. I would not reject at this point, but I would ask the authors to address both concerns in a major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline: this paper pulls off something genuinely new — the first setup-free asynchronous common coins with o(n^3) communication against Θ(n) adaptive faults. The committee transformation improves on Bracha's old virtual-party idea by removing message duplication and replacing per-committee BA with a sparse crusader publication. The resulting bounds — O(n^{2.5}) for perfect security, O(n^{7/3}) for cryptographic — are the first subcubic numbers for this problem, and the construction is clean: the Publish protocol is a neat design, and the Chernoff/hypergeometric proofs for committee safety look solid.\n\nThe soft spot is real and load-bearing. Lemma 5.4 needs the q committee outputs b_1,...,b_q to be independent. Definition 1.1 only gives per-instance δ-fairness: each committee, with probability at least δ, outputs a fresh uniform bit. It says nothing about independence across concurrently running instances, especially when the adversary can corrupt parties sitting on multiple committees. The proof simply asserts 'the bits ... are independent' and cites [14] for an ideal functionality. That only helps if C_str actually realizes that functionality under concurrent composition — which is neither stated in Definition 1.1 nor proved for the external strong coins from [22], [1], [6]. If the adversary can correlate the committee outputs, the sum X is not binomial, the anti-concentration bound fails, and the virtual Ben-Or argument collapses. This is not a nitpick: it is the step that produces the claimed constant fairness. I think it is repairable — one can add an explicit concurrent-composition assumption to Theorem 2.1 or prove the cited strong coins have it — but as written it is a gap.\n\nThe paper is otherwise honest. It flags its own large constants, credits Bracha, and self-cites only prior published building blocks. Non-constructive committee existence is acceptable for an existence result.\n\nWho should read it: anyone working on asynchronous BA or coin complexity. It's a theory paper, not practical. It deserves serious peer review — the construction is clever and the question is important — but the referee should focus on the independence/composition issue. I would not cite it in my own work until that is fixed.\n\nMy recommendation: send to peer review, with an expectation of major revision to close the concurrent-composition gap.","headline":"Real advance in coin complexity, but the proof needs a concurrent-composition assumption it doesn't state.","tokens_in":23767,"tokens_out":7851,"would_cite":false,"duration_ms":71474,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68M14"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that any strong but costly asynchronous common coin can be transformed into a cheaper weak coin, yielding the first setup-free asynchronous coins with subcubic communication and constant fairness against Θ(n) adaptive byza","keywords":["common coin","byzantine agreement","asynchronous protocols","adaptive adversary","committee-based transformation","communication complexity","verifiable secret sharing","setup-free protocols"],"falsifier":"Find one adaptive adversary that corrupts at most (α−ε)n parties and makes at least c = ⌈z'√q/3⌉ committees 'bad' (each containing at least αs corrupted members). Lemma 5.1 asserts this is impossible for the paper's deterministic committee list; if such a corruption set exists, the transformed coin's fairness collapses because the majority of committee bits is no longer guaranteed to be random.","tokens_in":22853,"feed_emoji":"🪙","tokens_out":7315,"duration_ms":75269,"temperature":0.7,"pith_summary":"The paper is trying to establish that expensive, rarely failing 'strong' coins can be systematically converted into cheap, lower-fairness 'weak' coins, and that this conversion is enough to break the long-standing n^3 communication barrier for setup-free asynchronous coin tossing. The transformation is committee-based: it splits the parties into many small committees, runs the strong coin inside each committee, and lets the committees act as virtual parties in a virtual majority-based coin. The paper proves a general trade-off — a strong coin costing O~(n^k) bits yields a weak coin costing O~(ε^{-2k} n^{3-2/k}) bits while losing only εn fault tolerance — and instantiates it with a perfectly secure coin for t ≤ (1/4−ε)n faults at O~(n^{2.5}) bits, and a hash-based coin for t ≤ (1/3−ε)n faults at O~(n^{7/3}) bits. If correct, this gives the first setup-free asynchronous byzantine agreement protocols with subcubic communication against a linear number of adaptive byzantine faults.","feed_headline":"First subcubic async coin toss without setup","feed_subtitle":"Run one strong coin per small committee, publish the bits sparsely — weak coins get cheaper while keeping constant fairness.","key_machinery":"The central machinery is a committee-based transformation T(Cstr,z,k,ε,α) that simulates a q-party majority coin with committees as virtual parties. The three load-bearing components are: (1) Lemma 5.1, a probabilistic construction of deterministic committees that guarantees fewer than c bad committees for any set of at most (α−ε)n corrupted parties; (2) the Publish protocol, which lets a committee reveal its bit to nearly all parties in O(s^2 + n(s/d + log n)) messages by combining crusader agreement with a sparse bipartite graph whose right-hand vertices have Δ neighbors; (3) an anti-concentration bound on symmetric binomials (Lemma 5.2) that, together with the odd choice of q, keeps the m","core_discovery":"On its own terms, the paper's discovery is that a strong binary coin — one whose good event happens with probability δ very close to 1 — can be amplified down into a weak coin: choose q odd committees of size s, run one independent strong-coin instance inside each committee, publish each committee's bit via a deliberately imperfect publication protocol based on crusader agreement and sparse communication graphs, and have every party take the majority of the published committee bits. The committees are chosen deterministically so that, against any adaptive adversary corrupting at most (α−ε)n parties, fewer than O(√q) committees are 'bad'; the strong-coin failures plus the majority bias of an","pith_inferences":["The virtual-party trick is not tied to binary outputs: the same committee-and-majority structure could, in principle, amplify strong coins with larger output domains, giving a more direct route to multivalued coins than the paper's parallel-bits approach.","The paper's O(log n) latency comes from the strong coins needing Θ(log n) rounds to reach failure probability 2^{-Θ(log n)}; a constant-latency strong coin with the same cost would immediately give a constant-latency weak coin under this same transformation.","Because the transformation treats the strong coin as a black box, improving the underlying strong coin's cost or security should automatically propagate through the same formula; this suggests the explicit open targets of O(n^2) communication and O(1) latency are exactly the places where such an improvement would show up."],"forward_implications":["For any strong coin with cost M(n)=O(n^c), c>2, and O(log n) message size, the transformed weak coin costs O(n^{3-2/c} log n) messages of the same size — the trade-off improves as c shrinks toward 2.","With an O(1)-toss binary byzantine agreement protocol, these coins yield setup-free asynchronous byzantine agreement with o(n^3) communication against Θ(n) adaptive byzantine faults; the perfectly secure coin achieves even o(n^4) bits under the paper's accounting.","The same technique gives leader election and multi-bit outputs with only polylogarithmic overhead, either by parallel independent tosses or by batching the per-committee strong-coin and publication steps.","If the strong coin is only λ-live, the transformed coin is still 1−(1−λ)^q-live, so the method also converts probabilistic-liveness coins into coins with near-deterministic liveness.","The transformation reduces fault tolerance by exactly εn relative to the strong coin it consumes, giving protocol designers a direct knob for trading resilience for communication."],"fun_headline_variants":["Async coin toss goes subcubic without PKI","Cheaper weak coins from strong ones in async","Committee-based coin tossing: subcubic and PKI-free","First async coin toss without setup under n^3","Subcubic async common coins: no PKI, just committees"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole construction stands or falls with the δ-fair strong coin: it must keep its δ ≈ 1−O(1/q) failure probability even when many instances run concurrently on overlapping committees under an adaptive adversary, and the concrete instantiations inherit the secrecy and security of their underlying verifiable-secret-sharing schemes.","fun_headline_variants_meta":{"raw":{"variants":["Async coin toss goes subcubic without PKI","Cheaper weak coins from strong ones in async","Committee-based coin tossing: subcubic and PKI-free","First async coin toss without setup under n^3","Subcubic async common coins: no PKI, just committees"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000216,"raw_usage":{"total_tokens":1319,"prompt_tokens":841,"completion_tokens":478,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":585,"completion_tokens_details":{"reasoning_tokens":398}},"tokens_in":585,"tokens_out":478,"duration_ms":5839,"temperature":1.0,"reasoning_tokens":398,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T19:27:55.971706+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find one adaptive adversary that corrupts at most (α−ε)n parties and makes at least c = ⌈z'√q/3⌉ committees 'bad' (each containing at least αs corrupted members). Lemma 5.1 asserts this is impossible for the paper's deterministic committee list; if such a corruption set exists, the transformed coin's fairness collapses because the majority of committee bits is no longer guaranteed to be random.","supporting_citations":[],"review_version":1}