{"id":"d0faf561-0737-439e-a2b0-e9cb9bf1e31e","arxiv_id":"2508.14568","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A TFHE edit distance algorithm that performs one programmable bootstrap per dynamic programming cell instead of about 94, with claimed speedups.","lead":"This paper describes an optimized algorithm, Leuvenshtein, for computing edit distance on encrypted data with fully homomorphic encryption, reducing costly bootstrap operations per cell from about 94 to 1. It claims large speedups over prior TFHE implementations and an extra speedup when one input is unencrypted.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 1-PBS-per-cell claim may require a combined lookup-table input whose bit-width grows with string length, exceeding the precision of a standard TFHE PBS for practical inputs.","rationale":"The reader's weakest assumption already points to the sensitivity of the speedup to ciphertext parameters, packing, and hidden non-PBS operations. My concern sharpens this: the very encoding implied by '1 PBS per cell' introduces a parameter-scaling issue that can break the claim entirely for realistic string lengths, not merely shrink the speedup. The abstract does not provide the algorithm details, parameter sets, or code, so the concern cannot be resolved from the material available. This does not move the verdict away from UNVERDICTED; it reinforces it. I would not reject the paper on this basis without seeing the full text, but the claimed general applicability to DNA-scale sequences should be treated as unverified until the packing width and PBS precision are shown to be compatible.","tokens_in":672,"tokens_out":6645,"duration_ms":86031,"concrete_test":"Independently re-derive from the paper's update rule the bit-width of the combined value passed to the per-cell PBS for string length L=100, then compare it with the precision supported by the TFHE parameter set used in the reported benchmarks. If the required width exceeds the PBS precision, the single-PBS-per-cell claim is unsupported for practical inputs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that a single programmable bootstrap per DP cell computes the Levenshtein update. A TFHE PBS evaluates one lookup table over a small message domain—practically up to roughly 8–12 bits for standard parameter sets (modulus size and polynomial degree). If the update is computed by packing the three neighboring cell values into one argument, e.g. x = a + B*b + B^2*c, then the domain size is about (M+1)^3, where M is the maximum representable edit-distance value. For strings of length L, M can be as large as L, so the combined message needs roughly 3*ceil(log2(L+1)) bits. For L=100 that is about 21 bits; for L=1000, about 30 bits. Neither is compatible with a single standard TFHE PBS. Thus the claimed '1 PBS per cell' either holds only for very short strings, relies on a nonstandard high-precision PBS whose per-bootstrap cost is much larger, or omits additional PBS operations needed to make the recurrence fit. The abstract reports up to 278x speedup without stating such constraints, so the headline depends on an unstated and likely restrictive condition.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript, as provided for review, consists solely of the abstract. It proposes Leuvenshtein, an FHE-based algorithm for Levenshtein edit distance built on TFHE. The abstract claims that the algorithm reduces the number of programmable bootstraps (PBS) per dynamic-programming cell from approximately 94 in a conventional Wagner-Fisher implementation to 1, performs ASCII character comparisons in only 2 PBS operations, and achieves speedups of up to 278x over the best available TFHE implementation, 39x over an optimized Wagner-Fisher implementation, and an additional 3x when one input is unencrypted and offline preprocessing is possible. No derivations, parameter sets, benchmark protocols, or full algorithm details are included in the provided text.","tokens_in":965,"tokens_out":3231,"duration_ms":41546,"significance":"If the central claim of 1 PBS per cell holds under standard TFHE parameter sets, the paper would represent a substantial practical advance in encrypted string comparison, reducing the dominant cost by roughly two orders of magnitude. The explicit reduction of character equality to 2 PBS operations and the identification of a preprocessing regime for plaintext/server inputs are also potentially valuable. However, the significance cannot be assessed from the abstract alone. The core feasibility question is whether a single standard TFHE PBS can encode the three-neighbor Levenshtein update at practical string lengths, and the abstract provides no information on message precision, ciphertext parameters, or baseline implementation details.","major_comments":[{"comment":"The central claim of 1 PBS per cell requires a precise specification of how the three neighboring cell values and the match/mismatch flag are packed into the PBS input. A TFHE PBS evaluates a lookup table over a bounded message space, typically 8-12 bits for standard parameter sets. If the input is formed as x = a + B*b + B^2*c with a,b,c in [0..L] (L being the maximum edit distance), the message width is roughly 3*log2(L+1) bits: about 21 bits for L=100 and 30 bits for L=1000. Neither is compatible with a single standard PBS. The abstract does not state the message bit-width, polynomial degree, or whether a non-standard high-precision PBS (with correspondingly higher cost) is used. Without these details, the headline 1-PBS-per-cell claim is unverifiable and may hold only for very short strings or at the cost of much larger bootstraps.","section":"Abstract"},{"comment":"The baseline count of 'approximately 94' PBS operations per cell is not derived or referenced. It is unclear whether this is a theoretical count for a naively implemented Wagner-Fisher algorithm, whether it includes equality checks, or whether the comparison uses matched security parameters and packing strategies. Since the speedup ratios are computed against this baseline, a fair comparison is load-bearing. A table of PBS counts for both algorithms under identical parameters would be more informative than the aggregate speedup factors stated.","section":"Abstract"},{"comment":"The claim that ASCII character equality checks require only 2 PBS operations is underspecified. The abstract mentions preprocessing when one input is unencrypted, which may mean the 2-PBS equality applies only to that setting. It is not clear whether the equality check is performed between encrypted characters, between one encrypted and one plaintext character, or as part of the cell update. The relationship between the 2-PBS equality mechanism and the 1-PBS cell update must be clarified, as the cell update itself must incorporate the result of the character comparison.","section":"Abstract"},{"comment":"The speedup numbers (278x, 39x, 3x) are presented without any evaluation context. No information is given about string lengths, security parameters, hardware, or how the baseline implementations were obtained. The abstract also states the algorithm is 'efficient' and 'optimised' but provides no pseudocode or complexity analysis. If the 1-PBS-per-cell claim requires larger parameters or additional non-PBS operations, the practical speedup may be far smaller than the headline ratios suggest.","section":"Abstract"}],"minor_comments":[{"comment":"The paper title and abstract do not identify the 'best available TFHE implementation' used as a baseline. A reference or concrete implementation name is needed.","section":"Abstract"},{"comment":"The abstract says 'third-generation schemes like TFHE.' This is slightly imprecise; TFHE is itself a third-generation scheme. Consider rewording.","section":"Abstract"},{"comment":"The name 'Leuvenshtein' appears to be a portmanteau of 'Levenshtein' and 'TFHE' (or 'Leuven'?). If intended, it should be clearly introduced; if a typo, correct it.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The provided manuscript is abstract-only, so I cannot assess the full paper. The central feasibility concern about the 1-PBS-per-cell encoding is severe: the abstract does not provide enough information to know whether the claim is compatible with standard TFHE parameters at practical string lengths. If the full version supplies the missing parameter details and benchmark protocols, the contribution may well be significant. I would encourage the editor to require the full text before making a final decision. The abstract's lack of references and evaluation detail also raises concerns about placement and reproducibility, but these are properly addressed in the full manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a one-page abstract with a big number. The claimed reduction from ~94 programmable bootstraps per cell to 1, if it holds, is a genuine algorithmic advance for TFHE-based edit distance. The equality-check trick at 2 PBS is also a useful detail. I can't see the full paper, so I'm reviewing the abstract on its own terms.\n\nWhat's actually new: the abstract claims a single-PBS-per-cell Levenshtein update, which is a real structural improvement over the conventional Wagner-Fisher mapping. That's worth taking seriously. The paper also acknowledges preprocessing when one input is plaintext, which is a practical angle for server-side use cases. The writing is direct and doesn't oversell beyond the 'up to 278x' caveat, though 'up to' is doing a lot of work.\n\nSoft spots: first, there are no derivations, parameter details, or benchmark protocols in the abstract. The speedup factor depends entirely on the baseline being a fair, optimized implementation with the same security level and correctness constraints. Second, the stress-test note is on point: a single TFHE PBS evaluates a lookup table over a small message domain, typically 8–12 bits. If the Levenshtein update is computed by packing three neighboring cell values into one input, the combined bit-width grows as 3*ceil(log2(L+1)), which for L=100 is already ~21 bits and for L=1000 ~30 bits. That won't fit a standard PBS. So the 1-PBS claim either holds only for short strings, uses a nonstandard high-precision PBS that costs more, or hides extra operations. The abstract doesn't state any such constraint, and that's a serious omission.\n\nI want to be clear: I can't tell whether the stress-test concern actually lands without reading the full paper. The authors may have a clever way to avoid the packing, or they may accept a larger message modulus. But it's exactly the kind of thing a referee needs to probe. The lack of any parameter or noise-growth discussion in the abstract makes the headline number unverifiable at this stage.\n\nWho this is for: people working on FHE for genomics or finance, and anyone tracking TFHE bootstrapping optimizations. If the full paper is solid, it could be a useful building block. As it stands, it's a promising abstract with an unresolved scaling question.\n\nRecommendation: send it to peer review. The claim is important enough that a careful referee should check the precision bounds and benchmark methodology. Don't desk reject on the abstract alone, but the authors should be pushed to disclose the exact parameter regime where the 1-PBS claim holds.","headline":"Abstract-only paper claiming a 94-to-1 PBS-per-cell reduction for FHE edit distance; the idea is genuinely interesting but the evidence is thin and a plausible precision ceiling may cap the claim.","tokens_in":741,"tokens_out":848,"would_cite":false,"duration_ms":26349,"reading_group":"maybe","serious_thinker":"unclear","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Encrypted edit distance now needs one bootstrap per cell, down from 94.","keywords":["fully homomorphic encryption","edit distance","Levenshtein distance","programmable bootstrap","TFHE","DNA sequence alignment","privacy-preserving string matching","dynamic programming"],"falsifier":"Implement both Leuvenshtein and the optimized Wagner-Fisher algorithm in the same FHE library with identical security parameters, and measure wall-clock time and bootstrap count per cell on strings of moderate length (e.g., 100×100). If the measured speedup is far below the advertised 39x, or if a correct implementation requires more than one PBS per cell, the central claim is falsified. The equality-check claim can be tested by counting bootstraps in a standalone ASCII comparison.","tokens_in":678,"feed_emoji":"🔐","tokens_out":4371,"duration_ms":46398,"temperature":0.7,"pith_summary":"Leuvenshtein is a new algorithm for computing the Levenshtein (edit) distance on encrypted strings under third-generation fully homomorphic encryption. The paper's central claim is that the standard dynamic-programming cell update can be restructured so that each cell of the edit-distance table costs a single programmable bootstrap instead of about 94 required by the conventional Wagner-Fisher approach. It also shows that equality checks between ASCII characters can be carried out with just 2 programmable bootstraps, and that a further roughly 3x speedup is available when one of the two strings is unencrypted and can be preprocessed on the server. If the claim holds, encrypted edit-distance queries on DNA sequences, financial records, or other sensitive text become tens to hundreds of times faster, moving them closer to practical use.","feed_headline":"Encrypted edit distance: 1 bootstrap per cell, down from 94","feed_subtitle":"A restructured dynamic-programming update makes encrypted string matching up to 278x faster, plus 3x via preprocessing.","key_machinery":"The key object is the single-bootstrap cell update for the dynamic-programming table. A programmable bootstrap is a homomorphic operation that evaluates a lookup table on an encrypted value while reducing noise; in TFHE-style schemes it dominates the cost. Leuvenshtein encodes the three neighboring table entries and the character-match bit so that the recurrence for the current cell can be evaluated in one PBS, rather than decomposing the update into many small comparisons and additions. The same machinery yields a two-bootstrap ASCII equality test.","core_discovery":"The authors propose a recurrence and ciphertext encoding for the Levenshtein distance table in which the update of each cell is compressed into one programmable bootstrap (PBS), a primitive that evaluates a lookup table on encrypted data while refreshing the ciphertext noise. Compared with the conventional Wagner-Fisher dynamic program, which requires approximately 94 PBS operations per cell because each integer comparison and addition is handled separately, Leuvenshtein needs exactly one. Character equality is handled separately by a dedicated two-bootstrap check on ASCII values. When one input is available in plaintext on the server side, precomputation of offsets yields an additional spee","pith_inferences":["The 94-to-1 PBS ratio assumes the baseline uses the same ciphertext parameters; if the single-PBS update needs larger parameters or more packing, wall-clock gains will be smaller than the PBS count suggests.","The recurrence pattern looks likely to transfer to other dynamic-programming string metrics, such as Smith-Waterman local alignment or Damerau-Levenshtein, where similar cell updates dominate cost.","A natural stress test is to benchmark end-to-end latency at fixed security and correctness levels; independent reproduction should measure whether the 39x/278x speedups hold outside the paper's own parameter choices."],"forward_implications":["Edit distance between encrypted strings of lengths n and m costs about n·m programmable bootstraps total, down from about 94·n·m, making longer encrypted strings feasible.","Encrypted exact and approximate string matching becomes practical enough for DNA-sequence alignment and financial record linkage under encryption.","A two-bootstrap ASCII equality check gives a cheap primitive for encrypted token matching, wildcard checks, and string-search building blocks.","When the server legitimately holds one plaintext string, preprocessing adds another ~3x, benefiting database-style lookups against encrypted records."],"supporting_citations":[],"fun_headline_variants":["FHE edit distance: 1 bootstrap per cell, 278x faster","From 94 to 1 bootstraps: encrypted string matching","Leuvenshtein: single-bootstrap edit distance for FHE","Encrypted edit distance: 94 PBS per cell cut to 1","Private string matching: 278x speedup with one PBS"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The claimed speedup rests on the assumption that programmable-bootstrap count is the dominant cost and that the 94-PBS Wagner-Fisher baseline is a fair, optimized comparison under the same security parameters and correctness constraints.","fun_headline_variants_meta":{"raw":{"variants":["FHE edit distance: 1 bootstrap per cell, 278x faster","From 94 to 1 bootstraps: encrypted string matching","Leuvenshtein: single-bootstrap edit distance for FHE","Encrypted edit distance: 94 PBS per cell cut to 1","Private string matching: 278x speedup with one PBS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000575,"raw_usage":{"total_tokens":2552,"prompt_tokens":746,"completion_tokens":1806,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":1712}},"tokens_in":490,"tokens_out":1806,"duration_ms":11474,"temperature":1.0,"reasoning_tokens":1712,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T18:24:09.223735+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement both Leuvenshtein and the optimized Wagner-Fisher algorithm in the same FHE library with identical security parameters, and measure wall-clock time and bootstrap count per cell on strings of moderate length (e.g., 100×100). If the measured speedup is far below the advertised 39x, or if a correct implementation requires more than one PBS per cell, the central claim is falsified. The equality-check claim can be tested by counting bootstraps in a standalone ASCII comparison.","supporting_citations":[],"review_version":1}