{"id":"db4809ac-17c8-4ff7-905a-cd1b2085fa19","arxiv_id":"2504.14497","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Cussen's compression-reconstruction algorithm, originally for plaintext matrix multiplication, is applied to plaintext-ciphertext matrix multiplication with additively homomorphic encryption, giving up to an order of magnitude speedup on an edge device.","lead":"This paper adapts a compression trick from plain matrix multiplication to speed up multiplying an unencrypted matrix by an encrypted one, without ever decrypting the data. On a Raspberry Pi 5, the method runs up to about 12 times faster than Strassen's algorithm for large matrices with small integer entries.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed order-of-magnitude speedup rests on Cussen compression reducing random t-bit columns to near-constant length; real ML and adversarial distributions are uncharacterized, so the practical scope of the central claim is not yet established.","rationale":"I read the paper as making a qualified algorithmic claim: for unpacked AHE, Cussen compression-reconstruction can reduce the dominant plaintext-ciphertext multiplication cost, yielding up to an order-of-magnitude speedup over Strassen for large matrices with small element bit-widths. The measured timings on a Raspberry Pi support this claim for uniform random matrices, and the implementation is plausibly correct since the reconstruction is exact and the code is released. I considered whether a different concern is more load-bearing. The Strassen baseline is not obviously unfair: scalar bit-width growth in Strassen's plaintext block sums makes Strassen slower, not faster, in practice, and the theoretical comparison is if anything conservative for the proposed method. The point-doubling/point-addition cost assumption could shift the breakeven point, but even a 2x error in the relative cost does not erase the order-of-magnitude speedup at t=4 or t=8. Table 3 has a numerical inconsistency for t=8 at large n, but it is minor and does not affect the measured timings. Decryption cost is identical across all three compared methods and is outside the claimed PC-MM computation. The one assumption that is both necessary and unsupported is the compression ratio m' on real non-random data. The paper's own failure cases (small n, large t) show that the method's advantage is not generic; it is entirely a property of the input distribution. Since the abstract and conclusions generalize specifically to machine-learning matrices, and no ML-derived matrices are tested, the practical breadth of the central claim is the weakest point. The reader's weakest_assumption identifies the same load-bearing concern, so my read does not change the conditional verdict.","tokens_in":26228,"tokens_out":25941,"duration_ms":248132,"concrete_test":"Run the full Algorithm 3 pipeline on real quantized weight matrices (for example, first-layer and fully-connected weights from ResNet-18, MobileNet, or a small transformer, quantized to 4 and 8 bits with standard per-tensor scaling) and on worst-case columns constructed to maximize the number of distinct values at every differencing iteration within [0, 2^t). Compare the measured m' distribution and end-to-end speedups against Strassen with the random-vector numbers in Tables 9 and 10. If real matrices give median m' around 1-4 and speedups of at least 8x, the practical claim is supported; if m' reaches a few hundred or speedup falls below 2x, the headline should be restricted to random or uniformly distributed data.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Cussen compression yields an order-of-magnitude PC-MM speedup for large matrices with small element bit-widths. The mechanism, Algorithm 3 step 3, is that each column of the plaintext matrix A, after repeated sorting, deduplication and differencing, has length m' much smaller than m; all speedup predictions (Tables 1-6) and the measured 10.5x versus Strassen at (n=512, t=8) are for independent uniform random entries. The paper provides no compression-ratio or timing data for real quantized ML weight matrices, and the assertion that such matrices 'are quite common' in machine learning is unsupported. This matters because m' is not determined by bit-width alone: an adversarial or structured t-bit column can have O(2^t) distinct iterated differences, and for t=8, n=512 the projected speedup over schoolbook drops from about 22x (Table 10) to near 1x if m' is a few hundred rather than 1-2. The paper's own data show the advantage already evaporates for (n,t) = (8,16) and (16,16). Since m' is the sole source of the speedup, the practical breadth of the headline claim is conditional on an unmeasured distributional assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a method for plaintext-ciphertext matrix multiplication (PC-MM) with unpacked additively homomorphic encryption (AHE), based on Cussen's compression-reconstruction algorithm. For each column of the plaintext matrix A, the method repeatedly sorts, deduplicates, and differences the entries to obtain a compressed vector of length m'; the required vector-scalar products with encrypted entries of B are then computed with m' plaintext-ciphertext scalar multiplications (elliptic curve scalar multiplications for EC-ElGamal) and reconstructed using ciphertext additions. The authors instantiate the method with EC-ElGamal, implement it on a Raspberry Pi 5 using the MIRACL library, and report speedups up to about 10.5x over Strassen and about 23x over the schoolbook method for large matrices with small element bit-widths. The concrete example at n=512, t=8 runs in about 15.6 minutes versus about 2.73 hours for Strassen and 5.72 hours for schoolbook. The paper also sketches an extension to the Paillier cryptosystem.","tokens_in":26500,"tokens_out":7250,"duration_ms":66706,"significance":"If the performance claim holds, this is a useful and easy-to-deploy technique for PC-MM from unpacked AHE in resource-constrained settings, where prior practice is essentially limited to schoolbook multiplication and Strassen's algorithm. The paper's strengths include a reproducible open-source implementation, exact reconstruction with no approximation error, a clear cost model based on the ECSM-to-point-addition cost ratio, and measurements across a wide range of matrix sizes and bit-widths. The main limitation is that the claimed speedup is demonstrated only on independent, uniformly random small-bit-width matrices; since the compression mechanism is data-dependent, the practical breadth of the headline claim is not yet established without data on realistic inputs.","major_comments":[{"comment":"The headline speedup is driven entirely by the assumption that Cussen compression yields m' much smaller than m for each column of A. The experiments in Section 4.2 use only independent uniform random t-bit entries; the paper provides no measurements of m' or runtime for real quantized machine-learning weight matrices, signal-processing matrices, or structured/adversarial inputs. The paper's own Table 10 shows the advantage is already lost or reversed for (n,t) in {(8,12), (8,16), (16,16)} and is only 0.94 versus Strassen at (32,16), so the beneficial regime is narrower than 'small bit-widths' alone. Since m' is not determined by the bit-width t but by the actual data distribution, the statement in Section 5 that such matrices 'are quite common' in machine learning is unsupported. Please either add measurements on realistic matrices (e.g., quantized transformer or CNN weights) or clearly restrict the claim to uniformly random small-bit-width matrices.","section":"Section 3.3, Algorithm 3 step 3; Tables 7-10"},{"comment":"All experiments fix the number of Cussen iterations at N=4, but the paper gives no justification for this choice and no sensitivity analysis. N is a free parameter that controls the trade-off between stronger compression (fewer ECSMs) and more reconstruction additions in Algorithm 2/3. The reported speedups are therefore conditional on an unexamined parameter setting. Please report how the compressed length, operation counts, and measured runtime vary with N, and justify the chosen value.","section":"Section 4.2; Figures 3-12 and Tables 1-10"},{"comment":"The analytical cost comparison in Figures 6/7 and Tables 5/6 assumes that an elliptic curve point doubling costs approximately the same as a point addition. The paper itself notes that the relative costs differ across curves and implementations. Since the measured timings are the primary evidence for the speedup, this assumption is not fatal, but the analytic estimates should either be validated against the measured point-doubling/point-addition cost ratio or de-emphasized in favor of the direct timing measurements.","section":"Section 3.3, cost model"}],"minor_comments":[{"comment":"The timing results are reported as averages, but no standard deviations, confidence intervals, or number of repetitions are given for the matrix-level measurements in Table 9. Please report the variance and the number of trials to support reproducibility.","section":"Section 4.2, Tables 7-10"},{"comment":"The phrase 'state-of-the-art' is broader than the actual comparison, which benchmarks only the schoolbook method and Strassen's algorithm among unpacked-AHE techniques. Please qualify the comparison set explicitly.","section":"Abstract and Section 1"},{"comment":"The statement that sparse plaintext matrices can be 'further compressed' is plausible but not measured. If it remains, support it with data or mark it as a speculative advantage to be validated in future work.","section":"Section 4.3.1"}],"recommendation":"major_revision","confidential_remarks":"The title page includes a footnote stating that a revised version of this paper was published in IACR Communications in Cryptology, vol. 2, no. 1 (2025). If this submission is intended as a new journal version, the authors should clarify the relationship to the published version and address any dual-submission or self-overlap concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid, narrowly scoped systems result. The authors port Cussen's compression-reconstruction trick from plaintext matrix multiplication into the unpacked-AHE world, using the fact that a plaintext-ciphertext multiply on EC-ElGamal costs about 2t point additions. On a Raspberry Pi 5 they measure 10-12x speedups over Strassen for n=256/512 and 4/8-bit random plaintext entries, with exact reconstruction. The code is public and the measurements are detailed. I believe the speedup numbers.\n\nWhat is new is not the compression algorithm—that is Cussen and Ullman—but the observation that the cost asymmetry in AHE makes it pay off, plus the careful implementation and the edge-device evaluation. The paper also gives operation-count tables and timing tables across a range of n and t, so you can see exactly where the method wins and where it loses. That transparency is good. The related-work coverage is thorough: the packed-FHE line, the prior unpacked-AHE inner-product work, and Cussen's original are all cited, and the authors do not overclaim novelty.\n\nThe soft spots are real but not fatal. The speedup is driven entirely by how much each plaintext column shrinks after Cussen's sort/dedup/difference loop. For independent uniform t-bit entries the shrinkage is dramatic; for real quantized ML weight matrices or adversarial inputs we get no data. The paper says such constrained matrices are \"quite common\" in ML without support. That caveat matters: at t=12/16 the advantage over Strassen shrinks to roughly 7-9x at n=512, and at n=8/16 the method is sometimes slower than schoolbook. So the headline should be read as \"for large random small-bit-width matrices\" until a real-world compression study appears. The measurements also lack variance bars; 100 trials are averaged but no spread is shown. The analytic model assumes point-doubling and point-addition costs are equal; the authors note the real costs differ by curve but do not quantify the impact. The choice N=4 is unexplained. I would call all of these minor-to-moderate issues, not load-bearing flaws.\n\nOne editorial flag: the arXiv footnote says a revised version was published in IACR Communications in Cryptology 2025. If this manuscript is under consideration somewhere, the publication status needs checking; it does not affect the science.\n\nBottom line: a useful, honest paper with a scoped claim that is mostly supported. I would send it to a serious referee. If you are comparing unpacked-AHE approaches, cite it; I would. I would also bring it to reading group—not because it opens a new paradigm, but because it is a clean application of a plaintext trick to encrypted arithmetic with reproducible numbers.","headline":"A solid, scoped systems result: Cussen's compression trick moves cleanly into unpacked-AHE PC-MM and delivers real speedups on a Raspberry Pi 5, with the open caveat that the gains depend on plaintext column structure.","tokens_in":26979,"tokens_out":3809,"would_cite":true,"duration_ms":38837,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Moving Cussen's compression-reconstruction algorithm into the encrypted domain gives plaintext-ciphertext matrix multiplication up to an order-of-magnitude speedup over Strassen for large low-bit-width matrices.","keywords":["plaintext-ciphertext matrix multiplication","additively homomorphic encryption","elliptic curve ElGamal","Cussen compression-reconstruction","privacy-preserving inference","edge computing","Strassen's algorithm"],"falsifier":"Count the compressed column length $m'$ for a fixed input matrix before running the encrypted multiplication. If for most columns $m'$ stays close to $m$—as happens for random 16-bit entries or for matrices with no duplicate patterns—the proposed approach's measured wall-clock time will not beat Strassen, and for $(n,t)=(8,16)$ and $(16,16)$ the paper's own measurements already show it is slower.","tokens_in":26061,"feed_emoji":"🔐","tokens_out":10131,"duration_ms":84733,"temperature":0.7,"pith_summary":"Plaintext-ciphertext matrix multiplication multiplies an unencrypted matrix $A$ by an encrypted matrix $B$ and returns an encrypted $A\\times B$, the operation behind private inference where model weights are public and user data is encrypted. With additively homomorphic encryption that stores one message per ciphertext, the schoolbook method costs $O(n^3)$ scalar-ciphertext multiplications, each far more expensive than a ciphertext addition; Strassen lowers the exponent but keeps the same imbalance. The paper's claim is that Cussen's compression-reconstruction algorithm, applied to the columns of $A$ before any encrypted arithmetic, converts most of those expensive scalar multiplications into cheap additions in the encrypted domain, and that the conversion is exact. In a software implementation on a Raspberry Pi 5 with elliptic-curve ElGamal encryption, the proposed method runs up to about 12 times faster than Strassen for large matrices with small element bit-widths, cutting the $(n=512,t=8)$ case from about 2.73 hours to about 15.6 minutes. This matters because it lowers the computational barrier for privacy-preserving machine learning and signal processing on resource-constrained edge devices.","feed_headline":"Encrypted matrix multiply gets 12x speedup via column compression","feed_subtitle":"Compressing plaintext columns before encrypted work cuts a 512x512 8-bit product from 2.7 hours to 15 minutes.","key_machinery":"The load-bearing mechanism is Cussen's compression-reconstruction algorithm, a plaintext method that rewrites an $n$-entry vector-scalar product as $m'$ scalar multiplications plus reconstruction additions: sort the vector, delete duplicate values, replace consecutive entries by their differences, and repeat; multiply the short compressed vector by the scalar; then undo the differences by prefix additions, un-sort, and re-insert duplicates. In the encrypted setting the compression phase runs on plaintext columns of $A$ and costs nothing homomorphic, while the reconstruction phase is executed with elliptic-curve point additions, which are cheap relative to the scalar multiplications being saved. The algorithm's work is to reduce the dominant plaintext-ciphertext scalar multiplication count from $n$ to $m'$ per column, with the compressed length $m'$ controlled by bit-width and duplicate structure rather than by $n$.","core_discovery":"The central discovery is that the trade-off inside Cussen's plaintext algorithm—spend sorting and differencing to shrink a vector, then reconstruct with additions—becomes decisive when the 'multiplications' are scalar-times-ciphertext operations. In elliptic-curve ElGamal, one scalar-ciphertext multiplication costs roughly $2t$ point operations (two elliptic-curve scalar multiplications of bit-width $t$), while one ciphertext-ciphertext addition costs two point additions, so replacing a scalar multiplication by several additions is a net win for moderate $t$. The paper adapts Cussen's compression phase (sort, remove duplicates, take consecutive differences) to each column of the plaintext matrix $A$, performs only $m'$ scalar-ciphertext multiplications per column, and then applies the reconstruction phase as elliptic-curve point additions to recover the exact encrypted outer products. Compression is amortized across all columns of $B$, and the reconstruction is exact, so the result matches plaintext matrix multiplication with no accuracy loss. Measured on random square matrices, the proposed PC-MM beats both schoolbook and Strassen for large $n$ and small $t$, with speedups over Strassen reaching about $12\\times$ at $(n,t)=(512,4)$ and $(256,4)$, and about $11\\times$ at $(512,8)$ and $(128,4)$.","pith_inferences":["Editorial inference: the speedup is data-dependent, so the natural stress test is to run the same implementation on real quantized neural-network weight matrices; repeated-value columns would compress at least as well as the random vectors measured, while dense high-entropy columns would erode the gain.","Editorial inference: the paper's own measurements show a sharp crossover—at bit-width 16 the method only wins from $n=32$ onward—so a practical deployment rule would check the compressed column length $m'$ before choosing between this algorithm and schoolbook.","Editorial inference: combining Strassen block decomposition with Cussen compression at the leaves may compound the gains, since the two mechanisms attack different costs (matrix multiplication depth versus scalar-multiplication count)."],"forward_implications":["For large matrices with element bit-widths of 4 to 8, PC-MM from unpacked additively homomorphic encryption becomes practical on a low-power edge board: the $n=512$, $t=8$ case runs in about 15.6 minutes instead of 2.73 hours with Strassen.","Because reconstruction is exact (the ciphertext decrypts to the true integer product), the speedup carries no accuracy trade-off beyond the integer or fixed-point encoding required by the encryption scheme.","The same compression logic transfers to other unpacked additively homomorphic schemes such as Paillier, where scalar-ciphertext 'multiplication' is modular exponentiation and ciphertext addition is modular multiplication.","Sparse plaintext matrices compress further, so low-precision and sparse machine-learning weight matrices are natural target inputs; rectangular matrices and convolution-as-matrix-multiplication are handled by the same algorithm.","The speedup grows with matrix dimension and shrinks with element bit-width, so the practical operating region is large, low-precision matrices rather than all matrix shapes."],"supporting_citations":[{"why":"Supplies the compression-reconstruction vector-scalar multiplication algorithm that the encrypted construction is built on.","marker":"[CU23]"},{"why":"Defines the Strassen algorithm used as the state-of-the-art baseline and complexity comparison.","marker":"[Str69]"},{"why":"Establishes the additively homomorphic ElGamal ciphertext operation that the EC-ElGamal instantiation relies on.","marker":"[ElG85]"},{"why":"Documents an earlier embedded ECC-based privacy-preserving matrix computation that motivates the edge-computing target.","marker":"[AB22]"},{"why":"Provides the unpacked AHE schoolbook and Strassen cost model and memory trade-off analysis the paper builds on.","marker":"[LZ23]"},{"why":"Supplies the elliptic-curve software implementation used for all measured timings.","marker":"[Sco20]"}],"fun_headline_variants":["12x faster encrypted matrix multiply via column compression","Column compression unlocks 12x speedup in encrypted matrix multiplication","Encrypted matrix multiply gets 12x speedup from column compression","Column compression gives 12x faster encrypted matrix multiply"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The speedup rests on the plaintext matrix columns compressing well: after sorting, removing duplicates, and taking differences, the compressed column length $m'$ must be much smaller than the original length $m$, which is true for random low-bit-width vectors but not guaranteed for adversarial or high-bit-width data.","fun_headline_variants_meta":{"raw":{"variants":["12x faster encrypted matrix multiply via column compression","Column compression unlocks 12x speedup in encrypted matrix multiplication","Encrypted matrix multiply gets 12x speedup from column compression","Column compression gives 12x faster encrypted matrix multiply"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000719,"raw_usage":{"total_tokens":3305,"prompt_tokens":1097,"completion_tokens":2208,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":713,"completion_tokens_details":{"reasoning_tokens":2141}},"tokens_in":713,"tokens_out":2208,"duration_ms":13752,"temperature":1.0,"reasoning_tokens":2141,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:47:31.682125+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Count the compressed column length $m'$ for a fixed input matrix before running the encrypted multiplication. If for most columns $m'$ stays close to $m$—as happens for random 16-bit entries or for matrices with no duplicate patterns—the proposed approach's measured wall-clock time will not beat Strassen, and for $(n,t)=(8,16)$ and $(16,16)$ the paper's own measurements already show it is slower.","supporting_citations":[],"review_version":1}