{"id":"64b4a858-904c-49bf-9ea3-3c71a3ec3290","arxiv_id":"2505.01845","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The claimed Θ(Q log p / log Q) speedup is a restatement of known fixed-base precomputation tradeoffs, and the supplied experiments do not validate the stated memory and timing gains.","lead":"This paper proposes an M-ary precomputation scheme for accelerating batches of elliptic-curve scalar multiplications with a fixed base point, claiming a log-factor time improvement over naive methods. The approach is a variant of classical fixed-base precomputation, and the reported experimental gains are not supported by the data shown.","discovery_kind":"incremental","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3's blinding step is internally inconsistent: S is already kP, so subtracting r·B^d·P yields the wrong result, or requires a per-scalar scalar multiplication not counted in Eq. (28).","rationale":"The reader's CONDITIONAL verdict is reinforced, but on a stronger basis: the blinding step is flawed in the main algorithm, not merely in the reported experiments. The M-ary precomputation idea itself is standard, and with r≡0 the complexity analysis in Eqs. (24)–(28) is plausible; that is why I do not escalate to REJECT. However, Algorithm 3 as published does not compute what it claims, and Section 3.7.1's side-channel claim depends on the broken step. The memory inconsistency in Table 7 (d·B≈7,000 points for secp256k1 at Q=1000, exceeding the reported 0.145 MB) remains a separate validation gap. A revision must correct or remove the blinding step, specify the table row range consistently, and reconcile measured memory with declared parameters.","tokens_in":21619,"tokens_out":15923,"duration_ms":166428,"concrete_test":"Run Algorithm 3 exactly as printed (rows 0..d−1, no row d) on secp256k1 for Q=1 with k=123456789, r=7, and compare the final S with kP; repeat with r=0 and with a 128-bit r. If any nonzero-r run gives S≠kP, the pseudocode is internally incorrect. In the same harness, count group operations spent in the 'Correct' line when r is 128-bit; if it is Θ(log p), then Eq. (28) omits a Θ(Q log p) term and the headline complexity does not describe Algorithm 3 as written.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Algorithm 3, Step 3, as printed, cannot be correct. It replaces k by k+r·B^d, decomposes only digits 0,...,d−1, computes S=Σ_{i=0}^{d−1} M[i][k_i], and then sets S←S−r·(B^d·P). Because k<n<B^d (the paper requires B^{d−1}≥n−1), the lower d digits of the shifted scalar are exactly the digits of k, so S=kP. The correction therefore returns (k−r·B^d)·P, not kP. If the intended S was the full shifted scalar, the digit rB^d must be included, but the table M defined in §3.2.2 and Appendix B.3 has rows only i=0,...,d−1, with no M[d][·]. Computing r·(B^d·P) by a generic scalar multiplication costs Ω(log r) point operations; for a full-size blinding r that is Ω(log p) per scalar, so the total becomes Θ(Q log p), erasing the speedup claimed in Eq. (28). Restricting r to {0,1} makes B^d·P available as M[d−1][B], but the algebra still gives (k−r·B^d)·P, and one bit of randomization is not meaningful DPA protection. Thus the published algorithm does not simultaneously compute kP correctly, run in Θ(Q log p / log Q), and provide the claimed blinding.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a batch fixed-base scalar multiplication algorithm for elliptic curves. For Q scalars, it selects a digit count d and radix B via the Lambert W function, precomputes a table M[i][j] = j·B^i·P, and computes each scalar as a sum of d table entries. The authors claim time complexity Θ(Q log p / log Q) and memory complexity Θ(Q log p / log² Q), and they present a sparse binary variant, ElGamal encryption experiments, and NS3 communication simulations. The theoretical derivation in Sections 3.3–3.5 is internally consistent under an additions-only cost model and does not fit constants to data. However, Algorithm 3's scalar blinding step is mathematically incorrect, the reported peak-memory measurements cannot accommodate the precomputed table described in the paper, and the binary-variant parameter derivation in Section 3.6 contains an error.","tokens_in":21936,"tokens_out":18251,"duration_ms":191193,"significance":"If the unblinded variant were the contribution, the asymptotic speedup and the memory scaling improvement over a sliding-window method with window size log Q would be a plausible and potentially useful result for large fixed-base batches; the Lambert-W-based parameter selection is a reasonable closed-form minimizer of the paper's own cost expression, and no free parameters are fitted to the experimental data. However, as submitted, the security claim rests on an incorrect randomization step, the memory measurements contradict the algorithm's own storage requirements, and the binary variant's minimization is not derived correctly. These issues are load-bearing for the paper's central claims, so the practical and theoretical significance cannot be accepted in the current form.","major_comments":[{"comment":"The scalar blinding step in Algorithm 3 does not compute kP. Since B^d·P is not the identity in general, the blinded scalar k + r·B^d is not congruent to k modulo the group order. The sum S over the lower d digits equals kP, because adding r·B^d does not change digits 0 through d−1, so the correction S ← S − r·(B^d·P) returns (k − r·B^d)·P; alternatively, including the missing position-d digit would return (k + r·B^d)·P. Neither is kP. A correct randomization must use k + r·ord(P), and the base-B digits of that value cannot be read off from the digits of k without additional work, so the per-scalar cost in Eq. (28) does not cover the blinding. Consequently, §3.7.1's DPA-resistance claim and the DPA column of Table 3 are unsupported, and Algorithm 3 as printed is incorrect for any nonzero r.","section":"Algorithm 3, Step 3; §3.7.1"},{"comment":"The peak-memory numbers in Table 7 cannot be produced by Algorithm 3 with the parameters of Sections 3.3–3.4. For secp256k1 at Q = 1000, d = ⌈ln p / (W(Q/e) + 1)⌉ ≈ 33 and B = ⌈p^{1/d}⌉ ≈ 217, so the table M of Eq. (20) contains roughly d·(B+1) ≈ 7,000 points; even with 33-byte compressed point storage this is about 0.23 MB, while the reported peak is 0.1449 MB. At Q = 1 the gap is even larger: d ≈ 139 and B ≈ 4 give roughly 700 points (about 0.02 MB compressed), against a reported peak of 0.000797 MB. The measurements therefore cannot include the precomputed table, or they use parameters different from those stated in the paper. The claimed 30% memory saving and the Θ(Q log p / log² Q) memory regime are not supported by the reported experiments.","section":"§4.2.2, Table 7"},{"comment":"Equation (38) is not the minimizer of Eq. (37). The Q-dependent term in Θ(d(p^{1/d} + Q log p^{1/d})) is Θ(Q log p), which is independent of d; minimizing the remaining term d·p^{1/d} over real d gives d = ln p (natural logarithm) and B = e, not d = log₂ p. If one instead sets d = log₂ p, then B = p^{1/d} = 2, not e. As written, Eq. (38) asserts d = log₂ p and B = e simultaneously, which is impossible. The claimed Θ(log p) space and Θ(Q log p) time for the binary variant therefore do not follow from the stated minimization, and the NS3 results attributed to the binary variant in Table 6 rest on an unproven configuration.","section":"§3.6.2, Eq. (38)"},{"comment":"The experimental sections do not state whether Algorithm 3's blinding step was enabled, which coordinate system and point encoding were used for the table, how peak memory was measured, or how the number Q of scalar multiplications relates to the plaintext length L in the ElGamal experiments. Combined with the blinding error in Algorithm 3, the reported encryption and simulation times cannot be attributed to the algorithm as printed, and the results are not reproducible without the source code or detailed implementation notes. These details are needed before the claimed practical gains can be evaluated.","section":"§4.2.2–§4.3"}],"minor_comments":[{"comment":"Equation (B.11) defines M_{i,j} for 0 ≤ j < B, while Algorithm 3 and Eq. (20) use 0 ≤ j ≤ B; the recurrence M_{i,1} = M_{i−1,B} requires the j = B entry, so the appendix bound should be corrected to 0 ≤ j ≤ B.","section":"Appendix B.3, Eq. (B.11)"},{"comment":"The notation 'd√n' and 'd√p' is ambiguous and should be typeset as a radical with index d, i.e., ⌈√[d]{n}⌉ and √[d]{p}.","section":"Eqs. (24), (37), (38)"},{"comment":"The abstract and conclusion cite '30% memory savings' without a baseline; Table 7 shows reductions that vary by curve and Q, for example about 18% versus Double-and-Add on secp256k1 at Q = 1000 and about 71% versus Sliding Window on secp384r1 at Q = 100.","section":"Abstract; §4.2.3; Conclusion"},{"comment":"The text states that M-ary (binary) ranks first in 9 of 12 test cases, but in Table 7 it has the lowest peak memory in all 12 rows; the count should be corrected.","section":"§4.3.2"},{"comment":"The bullet points describing Figure 6 conflict with the figure captions: the text assigns panel (a) to encryption time, (b) to communication time, and (c) to simulation time, while the captions assign (a) to simulation time, (b) to encryption time, and (c) to communication time.","section":"§4.3.2, Figure 6"},{"comment":"The text should state explicitly how the number of scalar multiplications Q is derived from the plaintext length L in the ElGamal experiments; otherwise the claimed 1/log Q scaling cannot be checked.","section":"§4.2.3, Table 5"},{"comment":"The binary entries are written as 'Mi,20,Mi,21,...' without superscripts; this should be M_{i,2^0}, M_{i,2^1}, and so on.","section":"Eq. (33)"}],"recommendation":"major_revision","confidential_remarks":"The theoretical complexity derivation for the unblinded algorithm is the most promising part of the paper and may be salvageable, but the current version combines an incorrect security step with memory measurements that are inconsistent with the algorithm's own table size. I would recommend a major revision requiring the authors to correct or remove the blinding claim, provide actual implementation and memory-measurement details, redo the experimental validation with the stated parameters, and fix the binary-variant derivation. The authors should also compare against a fixed-base sliding-window method with window size log Q, since that is the natural baseline for the claimed memory improvement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main construction in Sections 3.2–3.4 is the standard fixed-base precomputation method from the 1990s (BGMW/Lim-Lee): decompose the scalar in base B, precompute j·B^i·P, and sum the digits. The paper does not cite that literature and presents the method as new. The claimed asymptotic speed-up is not an advance over the fixed-base comb and window methods that already achieve the same log-factor reduction with comparable memory.\n\nWhat is genuinely useful here is small: the choice of B and d via the Lambert W function is a neat closed form, and the exposition of the base-B decomposition is clear and easy to follow. The experimental tables also suggest a real implementation, though no code is shipped and there are no error bars.\n\nThe soft spots are serious. The blinding step in Algorithm 3 is wrong as printed. After replacing k by k+r·B^d and decomposing only digits 0..d−1, the sum S already equals kP. Subtracting r·(B^d·P) gives (k−r·B^d)P. Making the blinding correct requires including the extra digit r, which means the table needs a row d and the digit r itself must be formed; otherwise you need a generic scalar multiplication by r, which costs Θ(log p) per scalar and destroys the claimed Θ(Q log p / log Q) time. So the published algorithm cannot simultaneously be correct, fast, and DPA-protected. The stress-test note holds up.\n\nThe memory claims are also inconsistent. For secp256k1 at Q=1000, the paper's own formula gives d≈33 and B≈217, so the table has roughly 7,000 points. Even compressed that is around 0.2–0.4 MB, yet the reported peak memory for M-ary (ours) is 0.145 MB. Either the implementation uses different parameters or the table is excluded from the measurement; either way the claimed 30% memory saving is unsupported. There is also a smaller mismatch: the abstract claims 59% encryption-time reduction on secp256k1, but Table 5 at L=360 shows 0.38s vs 0.79s, about 52%.\n\nBottom line: this is not a paper for cryptographers. Read it as a beginner-level exposition of a known technique, with extra parameter tuning that does not need a journal paper. For peer review I would desk reject it. If the authors were to rewrite it as a short note that correctly credits BGMW/Lim-Lee, removes the faulty blinding claim, and fixes the memory accounting, it might be publishable as a minor optimization note — but not in its current form.","headline":"The core algorithm is the classical BGMW/Lim-Lee fixed-base precomputation method, the blinding step as printed is internally inconsistent, and the reported memory figures do not match the described table size; only the Lambert W parameter choice is new and it is minor.","tokens_in":22471,"tokens_out":2124,"would_cite":false,"duration_ms":24739,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A base-B precomputation table is claimed to reduce batch elliptic-curve scalar-multiplication time from $\\Theta(Q \\log p)$ to $\\Theta(Q \\log p / \\log Q)$ while using $\\Theta(Q \\log p / \\log^2 Q)$ memory.","keywords":["elliptic curve cryptography","scalar multiplication","M-ary precomputation","time-space tradeoff","Lambert W function","ElGamal encryption","NS3 simulation","precomputation table"],"falsifier":"On secp256k1, set $Q=1000$, compute $d = \\lceil \\ln p / (W(1000/e)+1) \\rceil$ and $B = \\lceil p^{1/d} \\rceil$, then count the points the implementation actually stores before scalar multiplication begins. If the stored count is not $d \\cdot B$ (roughly 7,000 points) yet the reported peak memory is 0.1449 MB, the precomputation table is not part of the measurement and the claimed 30% memory savings and the asymptotic memory complexity are unsupported.","tokens_in":21446,"feed_emoji":"⚡","tokens_out":9952,"duration_ms":80171,"temperature":0.7,"pith_summary":"This paper proposes a precomputation method for elliptic-curve cryptography that computes many scalar multiplications at once when the base point is fixed, claiming to reduce the time from $\\Theta(Q \\log p)$ to $\\Theta(Q \\log p / \\log Q)$ while using $\\Theta(Q \\log p / \\log^2 Q)$ memory. The trick is to write each scalar in a base $B$ and look up multiples of $B^i P$ in a table instead of scanning every bit of every scalar. The paper also presents a sparse variant that stores only powers-of-two multiples per level, cutting memory to $\\Theta(\\log p)$ at a small runtime cost. Experiments with ElGamal encryption and an NS3 communication simulation report up to 59% faster encryption on secp256k1 and 22–25% reductions in communication and simulation time on the larger curves.","feed_headline":"Precomputed M-ary tables cut batch ECC cost by a log factor","feed_subtitle":"On secp256k1, the authors report 59% faster encryption and 30% lower peak memory for Q=1000 scalars.","key_machinery":"The load-bearing object is the M-ary table $M[i][j] = j\\,(B^i P)$, built by the recurrence $M[i][j] = M[i][j-1] + M[i][1]$ and $M[i][1] = M[i-1][B]$, so the whole table costs $\\Theta(dB)$ point additions. The second piece is the base-$B$ decomposition $k = \\sum_{i=0}^{d-1} a_i B^i$, which turns one scalar multiplication into $d$ lookups and $d-1$ additions. The third piece is the parameter choice: $B = \\lceil p^{1/d} \\rceil$ and $d = \\lceil \\ln p / (W(Q/e)+1) \\rceil$, where $W$ is the principal Lambert $W$ function; this minimizes $d(B+Q)$, converting the complexity into $\\Theta(Q \\log p / \\log Q)$, and it is what makes the claimed speedup asymptotic in $Q$. The sparse variant stores only $H[i][j] = M[i][2^j]$ and reconstructs each digit by binary decomposition, which replaces $O(\\log B)$ storage per row with a constant number of entries.","core_discovery":"The paper's central claim is that a table $M[i][j] = j\\,(B^i P)$, precomputed once for a fixed curve and base point, lets any scalar $k$ be turned into $kP$ in $d$ point additions: write $k$ in base $B$ and sum the $d$ selected table entries. With $B$ chosen as the $d$-th root of the field size and $d$ chosen as the minimizer of $x(p^{1/x}+Q)$, which is $\\ln p / (W(Q/e)+1)$ for the Lambert $W$ function, the total cost of $Q$ scalar multiplications becomes $\\Theta(d(B+Q)) = \\Theta(Q \\log p / \\log Q)$ and the table size becomes $\\Theta(dB) = \\Theta(Q \\log p / \\log^2 Q)$. A binary-storage variant keeps only the $2^j$ multiples in each row, bringing memory down to $\\Theta(\\log p)$ while restoring the time to $\\Theta(Q \\log p)$. The paper argues this beats the $\\Theta(Q \\log p)$ time of double-and-add, NAF, $2^k$-ary, and Montgomery-ladder baselines and the $\\Theta(2^r)$ memory of windowed methods, and reports consistent speedups in ElGamal and NS3 evaluations.","pith_inferences":["The same Lambert-$W$ balancing—splitting the scalar into $d$ base-$B$ digits so that the table cost $dB$ and the per-scalar lookup cost $dQ$ are equalized—should transfer to multi-scalar multiplication (MSM) pipelines, where a table of powers of the generator per level could be reused across many scalars; the paper mentions MSM only as future work, but the asymptotic benefit is immediate.","Because the time formula $d(B+Q)$ already includes the precomputation cost, the reported encryption-time reductions depend on $Q$ being large enough that $W(Q/e)+1$ exceeds a small constant; for small $Q$ the method degenerates to a fixed table of $\\Theta(\\log p)$ points with no asymptotic gain, a regime the paper's $\\log Q$ formulas do not make explicit.","If the memory measurements exclude the precomputation table, the 30% memory savings claim is not comparable to sliding-window memory, which counts table plus working state; a fair comparison would count the table bytes explicitly."],"forward_implications":["For applications that repeatedly multiply by the same base point—ElGamal encryption rounds, signature verification with fixed public keys, batch payment processing—the $1/\\log Q$ factor makes large batches asymptotically cheaper than any method that scans all $\\log p$ bits per scalar.","The memory complexity $\\Theta(Q \\log p / \\log^2 Q)$ grows sublinearly in $Q$, so the table size is manageable for $Q$ in the hundreds to thousands on the tested curves, unlike exponential-in-window precomputation schemes.","The binary-storage variant gives a practical memory floor of $\\Theta(\\log p)$ for constrained devices, converting the speed advantage into a space-time trade-off.","On the tested curves, the method reports up to 59% lower ElGamal encryption time on secp256k1 at $Q=1000$ and 22–25% lower communication and simulation time in the NS3 network scenario."],"supporting_citations":[{"why":"Supplies the double-and-add baseline whose $\\Theta(Q \\log p)$ scalar-multiplication time the paper's method aims to beat.","marker":"[11]"},{"why":"Provides the NAF-based baseline and the signed-binary representation machinery used for comparison.","marker":"[12]"},{"why":"Gives the sliding-window precomputation baseline whose exponential-in-window storage the M-ary table is designed to improve on.","marker":"[14, 15]"},{"why":"Montgomery ladder baseline used for security comparison and constant-time considerations.","marker":"[16]"},{"why":"Fixed-base comb baseline, the closest precomputation competitor for fixed-base batch scalar multiplication.","marker":"[17]"},{"why":"Time-space tradeoff analysis for function inversion that the paper cites as motivation for balancing precomputation storage and online computation cost.","marker":"[38]"},{"why":"Elastic MSM preprocessing technique that motivates the sparse binary storage variant of the table.","marker":"[39]"}],"fun_headline_variants":["M-ary tables cut batch ECC time by a log factor","Precompute M-ary tables for faster ECC scalar multiplication","M-ary precomputation: 59% faster ECC encryption, 30% less memory","Log-factor speedup for ECC via M-ary precomputation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The experimental numbers are taken as evidence for the complexity claims, which presupposes that the implementation actually builds and retains the full $d \\times B$ precomputation table with the stated parameter choices; if the reported peak memory of 0.1449 MB on secp256k1 at $Q=1000$ excludes that table (which alone would hold roughly 7,000 points, about 0.4 MB uncompressed), then the memory and complexity validation does not measure what the theory claims.","fun_headline_variants_meta":{"raw":{"variants":["M-ary tables cut batch ECC time by a log factor","Precompute M-ary tables for faster ECC scalar multiplication","M-ary precomputation: 59% faster ECC encryption, 30% less memory","Log-factor speedup for ECC via M-ary precomputation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000414,"raw_usage":{"total_tokens":2184,"prompt_tokens":1037,"completion_tokens":1147,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":653,"completion_tokens_details":{"reasoning_tokens":1065}},"tokens_in":653,"tokens_out":1147,"duration_ms":9746,"temperature":1.0,"reasoning_tokens":1065,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:11:15.668535+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On secp256k1, set $Q=1000$, compute $d = \\lceil \\ln p / (W(1000/e)+1) \\rceil$ and $B = \\lceil p^{1/d} \\rceil$, then count the points the implementation actually stores before scalar multiplication begins. If the stored count is not $d \\cdot B$ (roughly 7,000 points) yet the reported peak memory is 0.1449 MB, the precomputation table is not part of the measurement and the claimed 30% memory savings and the asymptotic memory complexity are unsupported.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the double-and-add baseline whose $\\Theta(Q \\log p)$ scalar-multiplication time the paper's method aims to beat."},{"cited_title":"Avanzi, C","cited_arxiv_id":null,"evidence_quote":"Provides the NAF-based baseline and the signed-binary representation machinery used for comparison."},{"cited_title":"Ansari, M","cited_arxiv_id":null,"evidence_quote":"Montgomery ladder baseline used for security comparison and constant-time considerations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Fixed-base comb baseline, the closest precomputation competitor for fixed-base batch scalar multiplication."},{"cited_title":"Golovnev, S","cited_arxiv_id":null,"evidence_quote":"Time-space tradeoff analysis for function inversion that the paper cites as motivation for balancing precomputation storage and online computation cost."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Elastic MSM preprocessing technique that motivates the sparse binary storage variant of the table."}],"review_version":1}