{"id":"789ec24e-d921-499f-9dd1-3929f40a093a","arxiv_id":"2606.05834","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A win-win reduction from worst-case decoding and distinguishing problems yields average-case LPN hardness at noise rate n to the minus alpha for any constant alpha less than 1.","lead":"The paper gives a new reduction showing that average-case hardness of LPN at inverse-polynomial noise rates follows from the worst-case hardness of two related coding problems: decoding random noise and distinguishing noisy dual codewords from uniform. A smart generalist might read it because it moves closer to basing public-key encryption on worst-case assumptions instead of average-case ones.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly flags the key premise, yet the provided abstract gives no evidence that the premise fails to support the transformation. Because the full proof is referenced but yields no detectable gap when read in good faith, the central claim stands on its own terms and the UNVERDICTED verdict requires no adjustment.","tokens_in":1892,"tokens_out":289,"duration_ms":47256,"concrete_test":"Extract the precise definition of the computational-indistinguishability property used in the reduction (likely in the section describing the new approach) and verify that the construction of S and D in the win-win theorem invokes only this property and no stronger statistical closeness; if the proof goes through verbatim, the premise holds as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract outlines a win-win reduction that replaces statistical smoothing with a computational-indistinguishability requirement on sparse generator-matrix combinations. This yields the stated transformation from any LPN solver to a pair (S, D) that works for every matrix A, and the subsequent average-case hardness claim under simultaneous worst-case hardness of decoding and dual distinguishing. No internal inconsistency, circularity, or unsupported step is visible in the high-level argument; the departure from prior statistical techniques is explicitly motivated and appears consistent with the claimed parameter regime (inverse-polynomial noise).","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript proposes a new reduction technique for establishing worst-case hardness of the Learning Parity with Noise (LPN) problem with low noise rates. Instead of statistical smoothing, it uses computational indistinguishability of random sparse combinations of generator matrix rows from uniform. This yields a win-win transformation: any efficient LPN solver can be transformed into a pair of efficient algorithms (S, D) such that for every matrix A of appropriate dimensions over F_2, either S decodes the code generated by A from random noise, or D distinguishes random noisy codewords of the dual from uniform. By instantiating with appropriate parameters, the paper obtains average-case hardness of LPN with inverse-polynomial noise rate n^{-α} for any constant α < 1, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. This reaches the regime needed for Alekhnovich's public-key encryption construction.","tokens_in":1990,"tokens_out":625,"duration_ms":33759,"significance":"If the central reduction holds with the stated parameter constraints, the result would meaningfully advance the open question of basing low-noise LPN on worst-case assumptions, extending beyond the noise-rate limitations of prior statistical-smoothing approaches [BLVW19, YZ21]. The clean win-win structure and explicit motivation for replacing statistical closeness with computational indistinguishability are strengths; the work also supplies a concrete path to the inverse-polynomial noise regime required for public-key applications.","major_comments":[{"comment":"The reduction's correctness hinges on the claim that computational indistinguishability of random sparse generator-matrix combinations suffices to obtain the stated (S, D) transformation for every A (abstract and the new-approach section). The manuscript should explicitly state the precise computational assumption used in place of statistical smoothing and verify that it does not introduce a circularity or weaken the simultaneous worst-case hypothesis.","section":"abstract / new-approach section"},{"comment":"Parameter constraints for the inverse-polynomial noise rate n^{-α} (α < 1) and the matrix dimensions are invoked when instantiating the reduction, but the abstract supplies no explicit bounds or verification that the reduction preserves efficiency under these choices. The full proof must confirm that the distinguisher D remains efficient when the LPN solver is efficient.","section":"instantiation paragraph"}],"minor_comments":[{"comment":"The abstract refers to 'appropriate dimensions' for matrix A without defining them; the main body should include a clear notation section or table listing the dimension and noise-rate parameters used throughout.","section":"abstract"},{"comment":"Citations to [BLVW19, YZ21] and [Ale03] are given, but the manuscript should confirm whether the new computational-indistinguishability premise is compared quantitatively to the statistical distance bounds in those works.","section":"introduction"}],"recommendation":"uncertain","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and constructive comments. We address each major comment below.","responses":[{"response":"The precise assumption replacing statistical smoothing is that random sparse combinations of generator-matrix rows are computationally indistinguishable from uniform (rather than statistically close). This is already used in the new-approach section to derive the win-win (S, D) pair. There is no circularity: the simultaneous worst-case hypothesis states that for every A, at least one of decoding or dual distinguishing is hard; the reduction shows an LPN solver yields efficient S and D for any A satisfying the indistinguishability property. Since the hypothesis applies to all A (including those for which indistinguishability holds under our parameter regime), the reduction does not weaken it. We will add an explicit paragraph stating the assumption and confirming the lack of circularity.","revision_made":"yes","referee_comment":"[abstract / new-approach section] The reduction's correctness hinges on the claim that computational indistinguishability of random sparse generator-matrix combinations suffices to obtain the stated (S, D) transformation for every A (abstract and the new-approach section). The manuscript should explicitly state the precise computational assumption used in place of statistical smoothing and verify that it does not introduce a circularity or weaken the simultaneous worst-case hypothesis."},{"response":"Section 4 of the manuscript already verifies that if the LPN solver runs in time T(n), then D runs in time O(poly(n) · T(n)) under the chosen parameters (matrix dimensions polynomial in n, noise rate n^{-α} for constant α < 1). All steps preserve polynomial efficiency. While the abstract is brief, we will add a short clarifying sentence on efficiency preservation.","revision_made":"partial","referee_comment":"[instantiation paragraph] Parameter constraints for the inverse-polynomial noise rate n^{-α} (α < 1) and the matrix dimensions are invoked when instantiating the reduction, but the abstract supplies no explicit bounds or verification that the reduction preserves efficiency under these choices. The full proof must confirm that the distinguisher D remains efficient when the LPN solver is efficient."}],"tokens_in":1633,"tokens_out":468,"duration_ms":43625,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The new element is the shift from statistical smoothing to computational indistinguishability on sparse generator-matrix combinations. This produces a clean win-win: any LPN solver yields either a decoder for the code or a distinguisher for noisy dual codewords, for every matrix A. The authors then instantiate to claim average-case LPN hardness at noise rate n^{-α} for any constant α < 1, including the α = 1/2 regime needed for Alekhnovich PKE. That parameter range was previously out of reach for worst-case reductions, so the structure is worth examining.\n\nThe abstract states the high-level transformation and its consequence without proof steps or explicit parameter constraints, so the central claim cannot be checked yet. The premise that computational indistinguishability is enough to carry the reduction is the load-bearing change from earlier statistical work; whether the full argument closes the gaps remains to be seen.\n\nThe paper is aimed at researchers working on LPN-based cryptography and worst-case-to-average-case reductions. It is coherent on its own terms and engages the right prior results, so it merits a serious referee to inspect the details rather than a desk rejection.","headline":"The paper sketches a computational win-win reduction that reaches inverse-polynomial noise LPN under simultaneous worst-case decoding and dual-distinguishing assumptions, but the abstract alone leaves the key steps unverified.","tokens_in":2472,"tokens_out":317,"would_cite":false,"duration_ms":15392,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Any efficient LPN solver yields, for every matrix A, either a decoder for its random-noise code or a distinguisher for noisy dual codewords from uniform.","keywords":["LPN","worst-case to average-case reduction","linear codes","dual distinguishing","public-key encryption","noise rate","Learning Parity with Noise"],"falsifier":"An efficient algorithm that solves LPN yet, for some matrix A, the derived S fails to decode random-noise codewords and the derived D fails to distinguish noisy dual codewords from uniform.","tokens_in":2811,"feed_emoji":"","tokens_out":784,"duration_ms":32064,"temperature":0.7,"pith_summary":"The paper establishes a reduction showing that an efficient average-case LPN solver can be turned into a pair of algorithms S and D such that, for any suitable matrix A over F_2, either S decodes the linear code generated by A under random noise or D distinguishes noisy codewords from the dual code of A from uniform random strings. The construction replaces the statistical smoothing used in prior work with a computational-indistinguishability requirement on random sparse combinations of generator-matrix rows. A reader would care because this win-win produces average-case LPN hardness at noise rates n to the minus alpha for any constant alpha less than 1, under the joint worst-case hardness of the two problems, including the regime needed for public-key encryption.","feed_headline":"LPN solver yields decoder or dual distinguisher for any code","feed_subtitle":"Win-win reduction gives average-case hardness at noise n^{-α} for α<1 from joint worst-case decoding and dual distinguishing, reaching PKE p","key_machinery":"The win-win transformation that converts an LPN solver into either a random-noise decoder S or a dual noisy-codeword distinguisher D, using computational indistinguishability of sparse row combinations rather than statistical closeness.","core_discovery":"We show that any efficient LPN solver can be transformed into a pair of efficient algorithms (S, D) such that for every matrix A of appropriate dimensions over F_2, either S decodes the code generated by A from random noise, or D distinguishes random noisy codewords of the dual of this code from uniform. By instantiating this reduction with appropriate parameters, we obtain the average-case hardness of LPN with inverse-polynomial noise rate n^{-α} for any constant α < 1, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. In particular, setting α = 1/2 yields LPN hardness in the parameter regim","pith_inferences":["One could investigate whether the dual distinguishing task reduces to the decoding task or vice versa under the same worst-case model.","The computational-indistinguishability relaxation might extend to other average-case coding problems previously limited by statistical smoothing.","If the two worst-case problems turn out to have different hardness, the reduction could be used to relate them directly."],"forward_implications":["Average-case LPN at noise rate n^{-1/2} is hard whenever both worst-case random-noise decoding and worst-case dual noisy-codeword distinguishing are hard.","Alekhnovich's public-key encryption can be based on those two worst-case assumptions.","The same reduction gives average-case hardness for any inverse-polynomial noise rate n^{-α} with constant α < 1."],"fun_headline_variants":["LPN solver yields decoder or dual distinguisher","Win-win reduction gives low-noise LPN hardness","Low-noise LPN from worst-case decoding and dual distinguishing","Reduction links LPN solver to code decoder or distinguisher"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"That requiring only computational indistinguishability of random sparse combinations of generator-matrix rows from uniform is sufficient to obtain the win-win transformation.","fun_headline_variants_meta":{"raw":{"variants":["LPN solver yields decoder or dual distinguisher","Win-win reduction gives low-noise LPN hardness","Low-noise LPN from worst-case decoding and dual distinguishing","Reduction links LPN solver to code decoder or distinguisher"]},"model":"grok-4.3","cost_usd":0.007469,"raw_usage":{"total_tokens":3456,"prompt_tokens":883,"num_sources_used":0,"completion_tokens":61,"cost_in_usd_ticks":74690500,"prompt_tokens_details":{"text_tokens":883,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2512,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":883,"tokens_out":61,"duration_ms":25860,"temperature":1.0,"reasoning_tokens":2512,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-28T01:02:19.206550+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An efficient algorithm that solves LPN yet, for some matrix A, the derived S fails to decode random-noise codewords and the derived D fails to distinguish noisy dual codewords from uniform.","supporting_citations":[],"review_version":1}