{"id":"e5f2291e-4fcd-4ef1-ab66-b1a71ad53d19","arxiv_id":"2607.13540","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Effectively zero-knowledge proofs, introduced by Ilango, are reformulated in bounded arithmetic with 'indistinguishable from true' derived as a theorem, and upgraded to genuine zero-knowledge under a hard-generator conjecture and a common random string.","lead":"This paper restates Ilango's new 'effectively zero-knowledge proofs' in the language of mathematical logic, so a key security property follows from the definition instead of being assumed. It then sketches how, under a proof-complexity conjecture and with a shared random string, that weak notion can be upgraded into ordinary, genuinely zero-knowledge proofs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 3's advertised upgrade to 'genuine' ZK is unsupported: replacing ψ_n by the tautology τ(g_s)^b leaves no standard assignment to serve as the simulator's dummy witness, so the nonstandard-model simulator of Thm 2.2 cannot be turned into a usual-sense PPT simulator.","rationale":"The paper's Sec. 2 is a careful and, as far as I can verify, correct conditional development: under (Th), a NIWI, and a hard tautology sequence, Theorem 2.2 establishes ZK relative to T, and Theorem 2.4 derives 'indistinguishable from true' rather than assuming it. The author is consistently honest about the conditional nature of the main construction and about the absence of a known hard tautology sequence. Credit is due for that clarity. The reader's weakest assumption points to the unproved hard-generator Claim imported from [11], and to the external nature of soundness. I agree partially: the unproved Claim is indeed a significant gap. But there is a deeper, more load-bearing problem that the reader's verdict does not identify. The advertised 'genuine zero-knowledge in the usual sense' in Sec. 3 does not follow even if the Claim is granted. The only simulator constructed in the paper lives in a nonstandard model and relies on an assignment that falsifies ψ_m. Since τ(g_s)^b, for b outside the range, is a standard tautology, no such falsifying assignment exists in the standard universe. The paper gives no alternative standard simulator, and none is apparent from the stated assumptions. This is not merely a missing proof of the Claim; it is a logical gap between the Claim and the stated conclusion. Therefore the manuscript's central advertised upgrade should not be accepted as standing. The paper could be salvaged by demoting Sec. 3 to an open problem or by adding an explicit trapdoor/CRS-style assumption and proving the required indistinguishability, but as written the strong claim is unsupported. This warrants moving the verdict from CONDITIONAL to REJECT.","tokens_in":6970,"tokens_out":21043,"duration_ms":216524,"concrete_test":"Attempt to instantiate the Sec. 3 protocol and write the claimed usual-sense simulator explicitly as a standard PPT algorithm. For a fixed shared string (s,s') with b∉Rng(g_s), determine what witness the simulator uses for φ∨¬τ(g_s)^b. Since no standard v satisfies ¬τ(g_s)^b, the only specified simulation strategy fails. To rescue the claim one must add an unstated assumption, e.g., that the simulator may choose b∈Rng(g_s) with a known preimage and that the resulting CRS distribution is computationally indistinguishable from the real one. Checking whether the text states or derives any such assumption settles whether the upgrade is valid.","verdict_should_be":"REJECT","load_bearing_attack":"Definition 2.1 defines ZK relative to T via the non-existence of short T-proofs of ¬∃C Simulator_c(n,C). Theorem 2.2 proves this by building a simulator C_m inside a nonstandard model M*, using an assignment v* with ¬ψ_m(v*)=1 (Claim 1 in the proof). That is a consistency statement, not a standard algorithmic existence. Section 3 then claims that replacing ψ_n by τ(g_s)^b, where the shared random string chooses b outside Rng(g_s) with high probability, yields 'ZK in the usual sense.' But when b∉Rng(g_s), τ(g_s)^b is a tautology, so ¬τ(g_s)^b is unsatisfiable in the standard model. Hence there is no standard v with ¬τ(g_s)^b(v)=1, and the dummy-witness strategy used throughout the paper — witness (0,v) for φ∨¬τ(g_s)^b — cannot be realized in the standard universe. The paper supplies no other standard simulator. The hardness Claim, even if proved, only says these tautologies are hard for all pps; it does not provide a falsifying assignment, nor a trapdoor allowing a simulator to force b∈Rng(g_s) while preserving the CRS distribution. Thus the implication from the hard-generator assumption to genuine (usual-sense) ZK is not established. At best, the construction preserves ZK relative to T, a strictly weaker notion.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper reformulates Ilango's effectively zero-knowledge proofs in the language of bounded arithmetic. Under the assumptions that T is a true p-time axiomatized theory containing S_2^1, that (A,B) is a NIWI, and that there is a p-time construable sequence of tautologies Ψ hard for P(T*), the author defines a p-time prover Prover[A,B,Ψ] and proves (Theorem 2.2) that it is ZK relative to T: for every c,e≥1, no T-proof of size ≤n^e can prove the nonexistence of a size ≤n^d simulator. The definition does not include the 'indistinguishable from true' property; instead Theorem 2.4 derives it as a consequence. Section 3 discusses the difficulty of constructing the required hard tautologies and then outlines an attempt, based on proof-complexity generators and a shared random string, to turn the construction into genuinely zero-knowledge proofs in the usual sense. The main advertised upgrade in Section 3 is, however, not established.","tokens_in":7310,"tokens_out":6182,"duration_ms":68623,"significance":"The Section 2 reformulation is a genuine contribution: it gives a short, modular proof using the Krajíček–Pudlák theorem and nonstandard models, and it shows that 'indistinguishable from true' can be a theorem rather than a definitional requirement. The paper is also honest about the conditional nature of the main existence result and about the lack of known constructions for the hard tautology sequence. If the Section 3 upgrade worked, it would be a notable connection between proof-complexity generators and zero-knowledge. However, as written, the upgrade is only a sketch and the specific claim of 'ZK in the usual sense' is not backed by a working standard-model simulator. The central Section 2 results are sound and worth publishing, but the paper's advertised stronger contribution needs substantial additional work.","major_comments":[{"comment":"The claim that replacing ψ_n by τ(g_s)^b yields ZK 'in the usual sense' is unsupported. In the proof of Theorem 2.2, the simulator C_m is built using an assignment v* with ¬ψ_m(v*)=1 supplied by a nonstandard model M*; the dummy witness is (0,v*). For τ(g_s)^b with b outside Rng(g_s), the formula τ(g_s)^b is a tautology, so ¬τ(g_s)^b has no satisfying assignment in any model, standard or nonstandard. Thus the dummy-witness strategy cannot be realized. The hardness Claim only asserts that such tautologies have no short propositional proofs; it does not give the simulator a falsifying assignment, nor does it provide a way to sample b inside Rng(g_s) while preserving the CRS distribution. No alternative standard simulator is described. The implication from the hard-generator assumption to usual-sense ZK is therefore not established. The author should either supply an explicit standard simul","section":"Section 3"},{"comment":"The load-bearing Claim that a random s makes g_s hard for all pps is imported from the author's own [11] and stated without proof. Since this Claim is essential for the proposed transformation to genuine ZK, the manuscript should either prove it or give a precise theorem statement and reference. Moreover, the use of a shared random string (s,s') changes the setting: the p-time sequence Ψ is no longer fixed, and the definition of ZK relative to T (Definition 2.1) or its CRS analogue is not reformulated. Before the 'usual sense' claim can be evaluated, the author must define the CRS-based ZK notion and state exactly which hardness and NIWI assumptions are needed in that model.","section":"Section 3"},{"comment":"The proof of Theorem 2.2 establishes only the consistency of the existence of a simulator, not the existence of a standard algorithmic simulator. This is explicitly built into Definition 2.1 and is not in itself a defect. However, the paper's abstract and Section 3 use the phrase 'genuinely zero-knowledge proofs' for the CRS-based construction, creating a risk of conflating the two notions. A revised version should carefully separate 'ZK relative to T' from 'usual ZK' and avoid implying that Theorem 2.2 by itself yields a standard simulator.","section":"Theorem 2.2"}],"minor_comments":[{"comment":"There are several typos: 'can be turned it into' should be 'can be turned into'; 'form proof complexity' should be 'from proof complexity'; 'termedeffectively ZKin' has a spacing issue. The word 'Gödel' in reference [4] is misspelled.","section":"Throughout"},{"comment":"Lemma 2.3 is cited rather than proved. The argument is standard, but since the lemma is used in Theorem 2.4, it would be helpful to include a proof sketch or a precise statement with page/claim references from [12] or [7].","section":"Lemma 2.3"},{"comment":"The symbol m is used both for the generator stretch (m=2n) and, in the proof of Theorem 2.2, for a nonstandard element. This is confusing. Use different letters for the generator stretch and the model element.","section":"Section 3"},{"comment":"The notation '1(m)' and 'n' for dyadic numerals is introduced in Section 1 but used in the proof of Theorem 2.2 without a reminder. A short sentence recalling that '1(m)' is the dyadic numeral for m would help the reader.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"The Section 2 results are solid and are the main value of the paper. The major issue is confined to Section 3's advertised 'genuine ZK' upgrade, which lacks a standard simulator and a formal CRS-based definition. The author should either provide the missing simulator argument or substantially weaken the claim. I would be willing to review a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core of this paper, Sec. 2, is worth reading. Krajicek recasts Ilango's effectively zero-knowledge proofs in bounded arithmetic, defines ZK relative to a theory, and proves existence under the same assumptions. The genuinely new and good part is that 'indistinguishable from true' falls out as a theorem (Thm 2.4) instead of being baked into the definition. The model-theoretic proof of Thm 2.2 via the K-P theorem and overspill is standard and, as far as I can check, sound. That is a clean conceptual improvement over Ilango, and it alone justifies a serious look.\n\nThe soft spots are concentrated in Sec. 3. The claim that replacing ψ_n with τ(g_s)^b and a shared random string yields ZK 'in the usual sense' is not supported. The stress-test note is right: the simulator in Thm 2.2 works by picking a nonstandard assignment v* that falsifies the tautology. When τ(g_s)^b is a genuine standard tautology (i.e., b is outside the range of g_s), no such v* exists in the standard universe. The dummy-witness trick used throughout the paper—witness (0,v) for φ∨¬τ—therefore has no standard realization, and no other standard simulator is supplied. The hardness Claim, even if proved, only says these tautologies are hard; it does not give a way to generate a fake witness in the standard world. So the construction, at best, preserves ZK relative to T, which is a strictly weaker notion.\n\nOther issues are real but less severe: the hard-sequence assumption on Ψ is conjectural and the paper itself notes no construction is known; the Sec. 3 Claim comes from a companion paper without proof; and protocol soundness is unverifiable by the parties, a limitation the author concedes. These are more 'incomplete' than 'wrong'. But the Sec. 3 overclaim is a load-bearing flaw in the advertised contribution.\n\nWho is this for? People working in proof complexity and the logical foundations of zero knowledge. The Sec. 2 material deserves peer review; Sec. 3 should either be proved or explicitly downgraded to a conjecture. I would send it to a referee, but with a clear request to fix or fence off Sec. 3.","headline":"The Sec. 2 logical reformulation of effectively ZK is a real contribution, but the Sec. 3 claim to genuine ZK does not survive contact with the standard model.","tokens_in":7904,"tokens_out":4620,"would_cite":true,"duration_ms":47539,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03F20","68Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Hard tautologies make zero-knowledge a provability phenomenon: a NIWI-based prover for SAT is zero-knowledge relative to a theory when the statement 'no small simulator exists' has no short proof in that theory, and a shared random string t","keywords":["proof complexity","zero-knowledge proofs","effectively zero-knowledge","non-interactive witness indistinguishability","bounded arithmetic","proof complexity generators","propositional tautologies","common random string"],"falsifier":"Find a propositional proof system that proves every p-time tautology sequence in size polynomial in the formula length; then no sequence Ψ can be hard for that system, so the hypothesis of Theorem 2.2 fails. For the generator upgrade, exhibit a specific proof system that, for every seed s and every b, proves τ(g_s)^b in polynomial size; that would refute the hard-generator claim on which the ordinary zero-knowledge construction rests.","tokens_in":6731,"feed_emoji":"🔐","tokens_out":7937,"duration_ms":72559,"temperature":0.7,"pith_summary":"This paper argues that zero-knowledge can be redefined in proof-theoretic terms, replacing the usual requirement that a simulator exists with the requirement that the absence of a simulator is hard to prove. Under a hardness assumption about propositional tautologies, it shows that a simple non-interactive witness-indistinguishable prover for SAT is zero-knowledge in this logical sense. The reformulation derives the 'indistinguishable from true' property as a consequence rather than building it into the definition. It then shows that, with a shared random string and a hard proof-complexity generator, this logical zero-knowledge can be upgraded to zero-knowledge in the usual cryptographic sense.","feed_headline":"Hard tautologies make zero-knowledge a provability barrier","feed_subtitle":"Proving that no simulator exists is the barrier; a shared random string upgrades the notion to genuine zero-knowledge.","key_machinery":"The key mechanism is the model-theoretic equivalence from bounded arithmetic: a propositional formula is not provable in the proof system P(T) exactly when there is an extension of a model of T in which the formula is falsified. This lets the proof translate 'Ψ is hard for P(T*)' into 'there is a non-standard model containing a simulator circuit', which is what makes the zero-knowledge claim go through. The second mechanism is the τ-formula of a proof-complexity generator: τ(g_s)^b is a tautology exactly when b lies outside the range of g_s. A generator hard for all propositional proof systems therefore supplies a p-time sequence of hard tautologies, which the shared-random-string constructi","core_discovery":"The central claim is that, under the assumptions that the base theory T is true and contains enough arithmetic, that (A,B) is a NIWI pair, and that a p-time sequence of tautologies Ψ is hard for the proof system P(T*), the prover Prover[A,B,Ψ] is ZK relative to T. Concretely, for every c,e ≥ 1 and all sufficiently large n, there is no T-proof of size at most n^e of the sentence asserting that no circuit of size at most n^d is a simulator for the prover. The proof uses a model-theoretic equivalence: if Ψ is not provable in P(T*), then a non-standard model can be extended to one where Ψ is false, and in that extension a simulator circuit can be built. The paper also proves that this definition","pith_inferences":["Editorial inference: the logical definition suggests a hierarchy of zero-knowledge notions indexed by the strength of T; weaker theories make the absence of a simulator harder to prove, so protocols could remain zero-knowledge even as actual simulators start to appear.","Editorial inference: the soundness of the generator-based protocol is tied to the range-avoidance problem; any algorithm that finds b in the range of g_s would make τ(g_s)^b falsifiable and break both soundness and the zero-knowledge argument.","Editorial inference: if the hard-generator conjecture holds, the common random string could plausibly be an ordinary public random string, removing the need for a trusted setup in these protocols."],"forward_implications":["Provided the hardness assumption holds, SAT admits a non-interactive zero-knowledge proof in the logical sense, with no interaction and no setup beyond the NIWI.","The 'indistinguishable from true' property follows automatically from the definition, so it does not need to be imposed as a separate condition.","With a shared random string and a hard proof-complexity generator, the logical zero-knowledge protocol becomes zero-knowledge in the ordinary cryptographic sense.","The verifier cannot prove the protocol sound from within the base theory, because soundness depends on tautologies whose tautologyhood the theory itself cannot establish."],"fun_headline_variants":["Proof complexity exposes zero-knowledge's true cost","Shared randomness turns effectively ZK into real ZK","Barrier in zero-knowledge: no small simulator proofs","Zero-knowledge meets proof complexity: a hard barrier","Why zero-knowledge proofs hit a provability wall"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The argument stands or falls with the assumption that there exists a p-time sequence of tautologies that is hard for the proof system P(T*); this is equivalent to there being no propositional proof system that has only polynomial slowdown over all others.","fun_headline_variants_meta":{"raw":{"variants":["Proof complexity exposes zero-knowledge's true cost","Shared randomness turns effectively ZK into real ZK","Barrier in zero-knowledge: no small simulator proofs","Zero-knowledge meets proof complexity: a hard barrier","Why zero-knowledge proofs hit a provability wall"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00053,"raw_usage":{"total_tokens":2365,"prompt_tokens":690,"completion_tokens":1675,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":434,"completion_tokens_details":{"reasoning_tokens":1599}},"tokens_in":434,"tokens_out":1675,"duration_ms":13140,"temperature":1.0,"reasoning_tokens":1599,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T04:54:08.033501+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a propositional proof system that proves every p-time tautology sequence in size polynomial in the formula length; then no sequence Ψ can be hard for that system, so the hypothesis of Theorem 2.2 fails. For the generator upgrade, exhibit a specific proof system that, for every seed s and every b, proves τ(g_s)^b in polynomial size; that would refute the hard-generator claim on which the ordinary zero-knowledge construction rests.","supporting_citations":[],"review_version":1}