Pith. sign in

REVIEW 3 major objections 3 minor 70 references

Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption

T0 review · 3 major / 3 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2504.14497 v1 pith:SVQM6375 submitted 2025-04-20 cs.CR

Krishna Sai Tarun Ramapragada , Utsav Banerjee This is my paper · ORCID
classification cs.CR
keywords plaintext-ciphertextmatrixmultiplicationadditivelyhomomorphicencryptionellipticcurveElGamalCussencompression-reconstructionprivacy-preservinginferenceedgecomputingStrassen'salgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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)$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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).
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

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.

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 (3)
  1. [Section 3.3, Algorithm 3 step 3; Tables 7-10] 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.
  2. [Section 4.2; Figures 3-12 and Tables 1-10] 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.
  3. [Section 3.3, cost model] 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.
minor comments (3)
  1. [Section 4.2, Tables 7-10] 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.
  2. [Abstract and Section 1] 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.
  3. [Section 4.3.1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proposed PC-MM speedups are measured against standard baselines, and the underlying Cussen compression is an external algorithm whose behavior is an empirical input, not a fitted consequence of the claimed result.

full rationale

The paper's central claim is an experimentally measured speedup: 'Our measurement results indicate up to an order of magnitude speedup with our proposed PC-MM compared to Strassen's algorithm in case of large matrices with relatively small element bit-widths.' This is supported by direct timing comparisons (Tables 7-10) between Algorithm 3, schoolbook PC-MM, and Strassen PC-MM, all implemented with the same EC-ElGamal AHE on a Raspberry Pi 5. No parameter is fitted to the target speedup, and no quantity used in the comparison is defined in terms of the measured outcome. The compression phase of Algorithm 3 is inherited from Cussen's plaintext matrix-multiplication algorithm [CU23], which is an external citation rather than the authors' own prior work, and the compressed column length m' comes from measured random-vector statistics, not from an equation that presupposes the final speedup. The paper's caveat that the advantage disappears for (n,t) in {(8,12),(8,16),(16,16)} and that real or adversarial matrices may not compress as well is a limitation on the breadth of the claim, not evidence that the derivation is circular. The unquantified assertion that constrained large matrices 'are quite common' in machine learning is an empirical generalization that could be challenged as unsupported, but it is not a self-referential or definitional reduction. The measured 10.5x speedup versus Strassen at (512,8) stands as an independent benchmark result, so no circularity score is warranted.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim relies on the Cussen algorithm's correctness, the cost asymmetry between scalar multiplications and additions, and the compressibility of small-bit-width plaintext matrices. No new entities are introduced.

free parameters (1)
  • Number of Cussen iterations N = 4
    Fixed at 4 compression-reconstruction iterations for all experiments; no sensitivity analysis or optimization reported, so it is a hand-chosen constant.
assumptions (4)
  • standard math The elliptic curve ElGamal scheme is additively homomorphic for bounded message spaces (Equation 4).
    Used in Section 3.1 to define PC-MM; requires message space bound n*Bs*Bm < q.
  • domain assumption Cussen's compression-reconstruction algorithm correctly computes vector-scalar products exactly (from [CU23]).
    The paper relies on the correctness of Algorithm 2 from [CU23] and provides only a toy example, not a full proof.
  • domain assumption Cost of ECSM with t-bit scalar is approximately 2t point additions, with point doubling and point addition having equal cost.
    Used in Section 3.3 to justify the trade-off; the authors state 'we assume they are approximately the same for simplicity'. Actual measurements support the overall conclusion.
  • domain assumption Random matrices used for profiling are representative of practical ML weight matrices with small bit-widths.
    The speedup is data-dependent; the paper justifies this by noting ML weights are often small integers, but does not evaluate on real ML workloads.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption." pith.science (2026). https://pith.science/paper/SVQM6375

@misc{pith2026250414497,
  author       = {Pith},
  title        = {Pith review of: Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SVQM6375}},
  note         = {Machine review of arXiv:2504.14497}
}
read the original abstract

Plaintext-ciphertext matrix multiplication (PC-MM) is an indispensable tool in privacy-preserving computations such as secure machine learning and encrypted signal processing. While there are many established algorithms for plaintext-plaintext matrix multiplication, efficiently computing plaintext-ciphertext (and ciphertext-ciphertext) matrix multiplication is an active area of research which has received a lot of attention. Recent literature have explored various techniques for privacy-preserving matrix multiplication using fully homomorphic encryption (FHE) schemes with ciphertext packing and Single Instruction Multiple Data (SIMD) processing. On the other hand, there hasn't been any attempt to speed up PC-MM using unpacked additively homomorphic encryption (AHE) schemes beyond the schoolbook method and Strassen's algorithm for matrix multiplication. In this work, we propose an efficient PC-MM from unpacked AHE, which applies Cussen's compression-reconstruction algorithm for plaintext-plaintext matrix multiplication in the encrypted setting. We experimentally validate our proposed technique using a concrete instantiation with the additively homomorphic elliptic curve ElGamal encryption scheme and its software implementation on a Raspberry Pi 5 edge computing platform. Our proposed approach achieves up to an order of magnitude speedup compared to state-of-the-art for large matrices with relatively small element bit-widths. Extensive measurement results demonstrate that our fast PC-MM is an excellent candidate for efficient privacy-preserving computation even in resource-constrained environments.

Figures

Figures reproduced from arXiv: 2504.14497 by the authors.

Figure 1
Figure 1. Matrix multiplication Am×n × Bn×l = Cm×l using (a) row-and-column inner products and (b) column-and-row outer products (diagram inspired by [Gri17]) [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Toy example showing four iterations each of the Compression Phase and the Reconstruction Phase of plaintext vector-scalar multiplication using Cussen’s algorithm [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Number of multiplications and additions required for plaintext vector-scalar multiplication using schoolbook approach and Cussen’s algorithm for random vectors of length n ∈ {2 3 , 2 4 , · · · , 2 9} with element bit-widths t ∈ {4, 8, 12, 16} [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: Number of multiplications and additions required for plaintext matrix multipli￾cation using schoolbook approach, Strassen’s algorithm and Cussen’s algorithm for random square matrices of dimension n ∈ {2 3 , 2 4 , · · · , 2 9} with element bit-widths t ∈ {4, 8, 12, 16}…
Figure 5
Figure 5. Figure 5: Toy example showing efficient multiplication of plaintext vector and EC-ElGamal ciphertext corresponding to encrypted scalar using proposed approach with four iterations of Cussen’s compression-reconstruction algorithm. with 4 iterations of compression and reconstructi…
Figure 6
Figure 6. Figure 6: Equivalent number of elliptic curve point additions required for plaintext vector and ciphertext scalar multiplication using schoolbook approach and proposed approach based on Cussen’s algorithm for random vectors of length n ∈ {2 3 , 2 4 , · · · , 2 9} with element bi…
Figure 7
Figure 7. Figure 7: Equivalent number of elliptic curve point additions required for plaintext￾ciphertext matrix multiplication PC-MM using schoolbook approach, Strassen’s algorithm and proposed approach based on Cussen’s algorithm for random square matrices of dimension n ∈ {2 3 , 2 4 , …
Figure 8
Figure 8. Figure 8: Experimental setup used for evaluating and profiling proposed fast PC-MM. FCE+23, LZ23], while few have presented implementations on embedded micro-controllers and IoT platforms [RPCS22, AB22, Ban23]. It is generally believed that homomorphic computations on encrypted …
Figure 9
Figure 9. Figure 9: Time taken for plaintext vector and ciphertext scalar multiplication using schoolbook approach and proposed approach based on Cussen’s algorithm for random vectors of length n ∈ {2 3 , 2 4 , · · · , 2 9} with element bit-widths t ∈ {4, 8, 12, 16} [PITH_FULL_IMAGE:figu…
Figure 10
Figure 10. Figure 10: Speedup observed for plaintext vector and ciphertext scalar multiplication using proposed approach based on Cussen’s algorithm compared to schoolbook approach for random vectors of length n ∈ {2 3 , 2 4 , · · · , 2 9} with element bit-widths t ∈ {4, 8, 12, 16}. elemen…
Figure 11
Figure 11. Figure 11: Time taken for plaintext-ciphertext matrix multiplication PC-MM using school￾book approach, Strassen’s algorithm and proposed approach based on Cussen’s algorithm for random square matrices of dimension n ∈ {2 3 , 2 4 , · · · , 2 9} with element bit-widths t ∈ {4, 8, …
Figure 12
Figure 12. Figure 12: Speedups observed for plaintext-ciphertext matrix multiplication PC-MM using proposed approach based on Cussen’s algorithm compared to schoolbook approach and Strassen’s algorithm for random square matrices of dimension n ∈ {2 3 , 2 4 , · · · , 2 9} with element bit-w…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

70 extracted references · 40 canonical work pages

  1. [1]

    Selcuk Uluagac, and Mauro Conti

    Abbas Acar, Hidayet Aksu, A. Selcuk Uluagac, and Mauro Conti. A Survey on Homomorphic Encryption Schemes: Theory and Implementation . ACM Computing Surveys , 51(4):1--35, 2018. https://doi.org/10.1145/3214303 doi:10.1145/3214303

    doi:10.1145/3214303 2018

  2. [2]

    Embedded Software Implementation of Privacy Preserving Matrix Computation using Elliptic Curve Cryptography for IoT Applications

    Faiek Ahsan and Utsav Banerjee. Embedded Software Implementation of Privacy Preserving Matrix Computation using Elliptic Curve Cryptography for IoT Applications . In IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS) , 2022. https://doi.org/10.1109/ANTS56424.2022.10227758 doi:10.1109/ANTS56424.2022.10227758

    work page arXiv 2022

  3. [3]

    Simple Functional Encryption Schemes for Inner Products

    Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval. Simple Functional Encryption Schemes for Inner Products . In IACR International Workshop on Public Key Cryptography (PKC) , pages 733--751, 2015. https://doi.org/10.1007/978-3-662-46447-2_33 doi:10.1007/978-3-662-46447-2_33

    work page doi:10.1007/978-3-662-46447-2_33 2015

  4. [4]

    Fully Secure Functional Encryption for Inner Products, From Standard Assumptions

    Shweta Agrawal, Beno \^ t Libert, and Damien Stehl \'e . Fully Secure Functional Encryption for Inner Products, From Standard Assumptions . In Annual International Cryptology Conference (CRYPTO) , pages 333--362, 2016. https://doi.org/10.1007/978-3-662-53015-3_12 doi:10.1007/978-3-662-53015-3_12

    work page doi:10.1007/978-3-662-53015-3_12 2016

  5. [5]

    Secure and Efficient Outsourced Matrix Multiplication with Homomorphic Encryption

    Aikata Aikata and Sujoy Sinha Roy. Secure and Efficient Outsourced Matrix Multiplication with Homomorphic Encryption . In International Conference on Cryptology in India (Indocrypt) , pages 51--74, 2024. https://doi.org/10.1007/978-3-031-80308-6_3 doi:10.1007/978-3-031-80308-6_3

    work page doi:10.1007/978-3-031-80308-6_3 2024

  6. [6]

    Privacy-Preserving Edge Computing from Pairing-Based Inner Product Functional Encryption

    Utsav Banerjee. Privacy-Preserving Edge Computing from Pairing-Based Inner Product Functional Encryption . In IEEE Global Communications Conference (GLOBECOM) , pages 2184--2189, 2023. https://doi.org/10.1109/GLOBECOM54140.2023.10436785 doi:10.1109/GLOBECOM54140.2023.10436785

    arXiv 2023

  7. [7]

    Plaintext-Ciphertext Matrix Multiplication and FHE Bootstrapping: Fast and Fused

    Youngjin Bae, Jung Hee Cheon, Guillaume Hanrot, Jai Hyun Park, and Damien Stehl \'e . Plaintext-Ciphertext Matrix Multiplication and FHE Bootstrapping: Fast and Fused . In Annual International Cryptology Conference (CRYPTO) , pages 387--421, 2024. https://doi.org/10.1007/978-3-031-68382-4_12 doi:10.1007/978-3-031-68382-4_12

    work page doi:10.1007/978-3-031-68382-4_12 2024

  8. [8]

    Packed Ciphertexts in LWE-based Homomorphic Encryption

    Zvika Brakerski, Craig Gentry, and Shai Halevi. Packed Ciphertexts in LWE-based Homomorphic Encryption . In International Conference on Practice and Theory in Public-Key Cryptography (PKC) , pages 1--13, 2013. https://doi.org/10.1007/978-3-642-36362-7_1 doi:10.1007/978-3-642-36362-7_1

    work page doi:10.1007/978-3-642-36362-7_1 2013

Show all 70 references
  1. [9]

    (Leveled) Fully Homomorphic Encryption without Bootstrapping

    Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping . ACM Transactions on Computation Theory , 6(3):1--36, 2014. https://doi.org/10.1145/2633600 doi:10.1145/2633600

    2014 doi

  2. [10]

    Function-Hiding Inner Product Encryption

    Allison Bishop, Abhishek Jain, and Lucas Kowalczyk. Function-Hiding Inner Product Encryption . In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) , pages 470--491, 2015. https://doi.org/10.1007/978-3-662-48797-6_20 doi:...

    2015 doi

  3. [11]

    Bernstein and Tanja Lange

    Daniel J. Bernstein and Tanja Lange. Explicit-Formulas Database , 2024. URL: https://www.hyperelliptic.org/EFD

    2024

  4. [12]

    Blake, Gadiel Seroussi, and Nigel Smart

    Ian F. Blake, Gadiel Seroussi, and Nigel Smart. Elliptic Curves in Cryptography , volume 265. Cambridge University Press, 1999. https://doi.org/10.1017/cbo9781107360211 doi:10.1017/cbo9781107360211

    1999 doi

  5. [13]

    Blake, Gadiel Seroussi, and Nigel Smart

    Ian F. Blake, Gadiel Seroussi, and Nigel Smart. Advances in Elliptic Curve Cryptography , volume 317. Cambridge University Press, 2005. https://doi.org/10.1017/cbo9780511546570 doi:10.1017/cbo9780511546570

    2005 doi

  6. [14]

    Homomorphic Encryption for Arithmetic of Approximate Numbers

    Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers . In International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT) , pages 409--437, 2017. https://doi.org/10.1007...

    2017 doi

  7. [15]

    Maliciously Secure Matrix Multiplication with Applications to Private Deep Learning

    Hao Chen, Miran Kim, Ilya Razenshteyn, Dragos Rotaru, Yongsoo Song, and Sameer Wagh. Maliciously Secure Matrix Multiplication with Applications to Private Deep Learning . In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYP...

    2020 doi

  8. [16]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms . The MIT Press, 3rd edition, 2009

    2009

  9. [17]

    Quadratic Functional Encryption for Secure Training in Vertical Federated Learning

    Shuangyi Chen, Anuja Modi, Shweta Agrawal, and Ashish Khisti. Quadratic Functional Encryption for Secure Training in Vertical Federated Learning . In IEEE International Symposium on Information Theory (ISIT) , pages 60--65, 2023. https://doi.org/10.1109/ISIT54713.2023.10206955...

    2023

  10. [18]

    Daniel Cussen and Jeffrey D. Ullman. Matrix Multiplication Using Only Addition . arXiv preprint arXiv:2307.01415, 2023. URL: https://arxiv.org/abs/2307.01415

    2023 arXiv

  11. [19]

    Functional Encryption for Inner Product with Full Function Privacy

    Pratish Datta, Ratna Dutta, and Sourav Mukhopadhyay. Functional Encryption for Inner Product with Full Function Privacy . In IACR International Conference on Practice and Theory in Public-Key Cryptography (PKC) , pages 164--195, 2016. https://doi.org/10.1007/978-3-662-49384-7_...

    2016 doi

  12. [20]

    High-Speed Hardware Implementations of Elliptic Curve Cryptography: A Survey

    Guerric Meurice De Dormale and Jean-Jacques Quisquater. High-Speed Hardware Implementations of Elliptic Curve Cryptography: A Survey . Journal of Systems Architecture , 53(2-3):72--84, 2007. https://doi.org/10.1016/j.sysarc.2006.09.002 doi:10.1016/j.sysarc.2006.09.002

    2007 doi

  13. [21]

    East: Efficient and Accurate Secure Transformer Framework for Inference

    Yuanchao Ding, Hua Guo, Yewei Guan, Weixin Liu, Jiarong Huo, Zhenyu Guan, and Xiyong Zhang. East: Efficient and Accurate Secure Transformer Framework for Inference . arXiv preprint arXiv:2308.09923, 2023. URL: https://arxiv.org/abs/2308.09923

    2023 arXiv

  14. [22]

    A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms

    Taher ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms . IEEE Transactions on Information Theory , 31(4):469--472, 1985. https://doi.org/10.1109/TIT.1985.1057074 doi:10.1109/TIT.1985.1057074

    1985

  15. [23]

    Troncoso-Pastoriza, Bonnie Berger, and Jean-Pierre Hubaux

    David Froelicher, Hyunghoon Cho, Manaswitha Edupalli, Joao Sa Sousa, Jean-Philippe Bossuat, Apostolos Pyrgelis, Juan R. Troncoso-Pastoriza, Bonnie Berger, and Jean-Pierre Hubaux. Scalable and Privacy-Preserving Federated Principal Component Analysis . In IEEE Symposium on Secu...

    1908

  16. [24]

    State-of-the-Art of Secure ECC Implementations: A Survey on Known Side-Channel Attacks and Countermeasures

    Junfeng Fan, Xu Guo, Elke De Mulder, Patrick Schaumont, Bart Preneel, and Ingrid Verbauwhede. State-of-the-Art of Secure ECC Implementations: A Survey on Known Side-Channel Attacks and Countermeasures . In IEEE International Symposium on Hardware-Oriented Security and Trust (H...

    2010

  17. [25]

    Somewhat Practical Fully Homomorphic Encryption

    Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption . Cryptology ePrint Archive, Paper 2012/144, 2012. URL: https://eprint.iacr.org/2012/144

    2012

  18. [26]

    Fully Homomorphic Encryption using Ideal Lattices

    Craig Gentry. Fully Homomorphic Encryption using Ideal Lattices . In Annual ACM Symposium on Theory of Computing (STOC) , pages 169--178, 2009. https://doi.org/10.1145/1536414.1536440 doi:10.1145/1536414.1536440

    2009

  19. [27]

    Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information

    Shafi Goldwasser and Silvio Micali. Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information . In Annual ACM Symposium on Theory of Computing (STOC) , pages 365--377, 1982. https://doi.org/10.1145/3335741.3335749 doi:10.1145/3335741.3335749

    1982

  20. [28]

    Secure and Efficient General Matrix Multiplication on Cloud using Homomorphic Encryption

    Yang Gao, Gang Quan, Soamar Homsi, Wujie Wen, and Liqiang Wang. Secure and Efficient General Matrix Multiplication on Cloud using Homomorphic Encryption . The Journal of Supercomputing , 80(18):26394--26434, 2024. https://doi.org/10.1007/s11227-024-06428-8 doi:10.1007/s11227-0...

    2024 doi

  21. [29]

    ML Wiki: Matrix-Matrix Multiplication , 2017

    Alexey Grigorev. ML Wiki: Matrix-Matrix Multiplication , 2017. URL: http://mlwiki.org/index.php/Matrix-Matrix_Multiplication

    2017

  22. [30]

    Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

    Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based . In Annual Cryptology Conference (CRYPTO) , pages 75--92, 2013. https://doi.org/10.1007/978-3-642-40041-4_5 doi:10.1007/9...

    2013 doi

  23. [31]

    Choi, Daniel S

    Seungwan Hong, Yoolim A. Choi, Daniel S. Joo, and Gamze Gürsoy. Privacy-Preserving Model Evaluation for Logistic and Linear Regression using Homomorphically Encrypted Genotype Data . Journal of Biomedical Informatics , 156:104678, 2024. https://doi.org/10.1016/j.jbi.2024.10467...

    2024

  24. [32]

    More Efficient Secure Matrix Multiplication for Unbalanced Recommender Systems

    Zhicong Huang, Cheng Hong, Chenkai Weng, Wen-jie Lu, and Hunter Qu. More Efficient Secure Matrix Multiplication for Unbalanced Recommender Systems . IEEE Transactions on Dependable and Secure Computing , 20(1):551--562, 2023. https://doi.org/10.1109/TDSC.2021.3139318 doi:10.11...

    2023

  25. [33]

    Iron: Private Inference on Transformers

    Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang. Iron: Private Inference on Transformers . In Advances in Neural Information Processing Systems (NeurIPS) , volume 35, pages 15718--15731, 2022. URL: https://proceedings.neurips.cc/paper/2022/hash/6...

    2022

  26. [34]

    Hankerson, Alfred J

    Darrel R. Hankerson, Alfred J. Menezes, and Scott A. Vanstone. Guide to Elliptic Curve Cryptography . Springer Science & Business Media, 2006. https://doi.org/10.1007/b97644 doi:10.1007/b97644

    2006 doi

  27. [35]

    Computing's Energy Problem (and what we can do about it)

    Mark Horowitz. Computing's Energy Problem (and what we can do about it) . In IEEE International Solid-State Circuits Conference (ISSCC) , pages 10--14, 2014. https://doi.org/10.1109/ISSCC.2014.6757323 doi:10.1109/ISSCC.2014.6757323

    2014

  28. [36]

    Algorithms in HElib

    Shai Halevi and Victor Shoup. Algorithms in HElib . In Annual Cryptology Conference (CRYPTO) , pages 554--571, 2014. https://doi.org/10.1007/978-3-662-44371-2_31 doi:10.1007/978-3-662-44371-2_31

    2014 doi

  29. [37]

    Secure Matrix Multiplication based on Fully Homomorphic Encryption

    Hai Huang and Haoran Zong. Secure Matrix Multiplication based on Fully Homomorphic Encryption . The Journal of Supercomputing , 79(5):5064--5085, 2023. https://doi.org/10.1007/s11227-022-04850-4 doi:10.1007/s11227-022-04850-4

    2023 doi

  30. [38]

    A Systematic Review of Fast, Scalable, and Efficient Hardware Implementations of Elliptic Curve Cryptography for Blockchain

    Rares Ifrim, Dumitrel Loghin, and Decebal Popescu. A Systematic Review of Fast, Scalable, and Efficient Hardware Implementations of Elliptic Curve Cryptography for Blockchain . ACM Transactions on Reconfigurable Technology and Systems , 17(4):1--33, 2024. https://doi.org/10.11...

    2024 doi

  31. [39]

    Secure Outsourced Matrix Computation and Application to Neural Networks

    Xiaoqian Jiang, Miran Kim, Kristin Lauter, and Yongsoo Song. Secure Outsourced Matrix Computation and Application to Neural Networks . In ACM SIGSAC Conference on Computer and Communications Security (CCS) , pages 1209--1222, 2018. https://doi.org/10.1145/3243734.3243837 doi:1...

    2018

  32. [40]

    Privacy-Preserving Deep Sequential Model with Matrix Homomorphic Encryption

    Jaehee Jang, Younho Lee, Andrey Kim, Byunggook Na, Donggeon Yhee, Byounghan Lee, Jung Hee Cheon, and Sungroh Yoon. Privacy-Preserving Deep Sequential Model with Matrix Homomorphic Encryption . In ACM on Asia Conference on Computer and Communications Security (ASIA CCS) , pages...

    2022

  33. [41]

    Elliptic Curves and Side-Channel Analysis

    Marc Joye. Elliptic Curves and Side-Channel Analysis . ST Journal of System Research , 4(1):17--21, 2003. URL: https://marcjoye.github.io/papers/Joy03ecc.pdf

    2003

  34. [42]

    GAZELLE: A Low Latency Framework for Secure Neural Network Inference

    Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. GAZELLE: A Low Latency Framework for Secure Neural Network Inference . In USENIX Security Symposium , pages 1651--1669, 2018. URL: https://www.usenix.org/conference/usenixsecurity18/presentation/juvekar

    2018

  35. [43]

    The Montgomery Powering Ladder

    Marc Joye and Sung-Ming Yen. The Montgomery Powering Ladder . In International Workshop on Cryptographic Hardware and Embedded Systems (CHES) , pages 291--302, 2002. https://doi.org/10.1007/3-540-36400-5_22 doi:10.1007/3-540-36400-5_22

    2002 doi

  36. [44]

    Function-Hiding Inner Product Encryption Is Practical

    Sam Kim, Kevin Lewi, Avradip Mandal, Hart Montgomery, Arnab Roy, and David J Wu. Function-Hiding Inner Product Encryption Is Practical . In Security and Cryptography for Networks (SCN) , pages 544--562, 2018. https://doi.org/10.1007/978-3-319-98113-0_29 doi:10.1007/978-3-319-9...

    2018 doi

  37. [45]

    Privacy Preserving Data Classification using Inner-Product Functional Encryption

    Damien Ligier, Sergiu Carpov, Caroline Fontaine, and Renaud Sirdey. Privacy Preserving Data Classification using Inner-Product Functional Encryption . In International Conference on Information Systems Security and Privacy (ICISSP) , pages 423--430, 2017. https://doi.org/10.52...

    2017 doi

  38. [46]

    Using Fully Homomorphic Encryption for Statistical Analysis of Categorical, Ordinal and Numerical Data

    Wen-jie Lu, Shohei Kawasaki, and Jun Sakuma. Using Fully Homomorphic Encryption for Statistical Analysis of Categorical, Ordinal and Numerical Data . In Network and Distributed System Security Symposium (NDSS) , 2017. https://doi.org/10.14722/ndss.2017.23119 doi:10.14722/ndss....

    2017

  39. [47]

    Achieving Privacy Preservation in WiFi Fingerprint-Based Localization

    Hong Li, Limin Sun, Haojin Zhu, Xiang Lu, and Xiuzhen Cheng. Achieving Privacy Preservation in WiFi Fingerprint-Based Localization . In IEEE Conference on Computer Communications (INFOCOM) , pages 2337--2345, 2014. https://doi.org/10.1109/INFOCOM.2014.6848178 doi:10.1109/INFOC...

    2014

  40. [48]

    Privacy-Preserving and Publicly Verifiable Matrix Multiplication

    Jing Liu and Liang Feng Zhang. Privacy-Preserving and Publicly Verifiable Matrix Multiplication . IEEE Transactions on Services Computing , 16(3):2059--2071, 2023. https://doi.org/10.1109/TSC.2022.3215499 doi:10.1109/TSC.2022.3215499

    2023

  41. [49]

    Improved Privacy-Preserving PCA using Optimized Homomorphic Matrix Multiplication

    Xirong Ma, Chuan Ma, Yali Jiang, and Chunpeng Ge. Improved Privacy-Preserving PCA using Optimized Homomorphic Matrix Multiplication . Computers & Security , 138:103658, 2024. https://doi.org/10.1016/j.cose.2023.103658 doi:10.1016/j.cose.2023.103658

    2024

  42. [50]

    Menezes, Paul C

    Alfred J. Menezes, Paul C. Van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography . CRC Press, 2018. https://doi.org/10.1201/9780429466335 doi:10.1201/9780429466335

    2018 doi

  43. [51]

    Privacy-Enhanced Machine Learning with Functional Encryption

    Tilen Marc, Miha Stopar, Jan Hartman, Manca Bizjak, and Jolanda Modic. Privacy-Enhanced Machine Learning with Functional Encryption . In European Symposium on Research in Computer Security , pages 3--21, 2019. https://doi.org/10.1007/978-3-030-29959-0_1 doi:10.1007/978-3-030-29959-0_1

    2019 doi

  44. [52]

    THOR: Secure Transformer Inference with Homomorphic Encryption

    Jungho Moon, Dongwoo Yoo, Xiaoqian Jiang, and Miran Kim. THOR: Secure Transformer Inference with Homomorphic Encryption . Cryptology ePrint Archive, Paper 2024/1881, 2024. URL: https://eprint.iacr.org/2024/1881

    2024

  45. [53]

    Digital Image Processing: Filtering in the Frequency Domain (Circulant Matrices and Convolution) , 2014

    Christophoros Nikou. Digital Image Processing: Filtering in the Frequency Domain (Circulant Matrices and Convolution) , 2014. URL: https://www.cs.uoi.gr/ cnikou/Courses/Digital\_Image\_Processing/\ \_04c\_Frequency\_Filtering\_(Circulant\_Matrices).pdf

    2014

  46. [54]

    Privacy-Preserving Deep Learning via Additively Homomorphic Encryption

    Le Trieu Phong, Yoshinori Aono, Takuya Hayashi, Lihua Wang, and Shiho Moriai. Privacy-Preserving Deep Learning via Additively Homomorphic Encryption . IEEE Transactions on Information Forensics and Security , 13(5):1333--1345, 2017. https://doi.org/10.1109/tifs.2017.2787987 do...

    2017

  47. [55]

    Public-Key Cryptosystems Based on Composite Degree Residuosity Classes

    Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes . In International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) , pages 223--238, 1999. https://doi.org/10.1007/3-540-48910-x_16 doi:10.1007/3-540-48910-x_16

    1999 doi

  48. [56]

    Ciphertext-Ciphertext Matrix Multiplication: Fast for Large Matrices

    Jai Hyun Park. Ciphertext-Ciphertext Matrix Multiplication: Fast for Large Matrices . Cryptology ePrint Archive, Paper 2025/448, 2025. URL: https://eprint.iacr.org/2025/448

    2025

  49. [57]

    Bolt: Privacy-Preserving, Accurate and Efficient Inference for Transformers

    Qi Pang, Jinhao Zhu, Helen M \"o llering, Wenting Zheng, and Thomas Schneider. Bolt: Privacy-Preserving, Accurate and Efficient Inference for Transformers . In IEEE Symposium on Security and Privacy (SP) , pages 4753--4771, 2024. https://doi.org/10.1109/SP54263.2024.00130 doi:...

    2024

  50. [58]

    A Survey on Hardware Implementations of Elliptic Curve Cryptosystems

    Bahram Rashidi. A Survey on Hardware Implementations of Elliptic Curve Cryptosystems . arXiv preprint arXiv:1710.08336, 2017. URL: https://arxiv.org/abs/1710.08336

    2017 arXiv

  51. [59]

    Partially Encrypted Deep Learning using Functional Encryption

    Th \'e o Ryffel, David Pointcheval, Francis Bach, Edouard Dufour-Sans, and Romain Gay. Partially Encrypted Deep Learning using Functional Encryption . In Advances in Neural Information Processing Systems (NeurIPS) , pages 4517--4528, 2019. URL: https://proceedings.neurips.cc/p...

    2019

  52. [60]

    Manohar Reddy, Sajimon P

    H. Manohar Reddy, Sajimon P. C., and Sriram Sankaran. On the Feasibility of Homomorphic Encryption for Internet of Things . In IEEE World Forum on Internet of Things (WF-IoT) , pages 1--6, 2022. https://doi.org/10.1109/WF-IoT54382.2022.10152214 doi:10.1109/WF-IoT54382.2022.10152214

    2022

  53. [61]

    Rivest, Adi Shamir, and Leonard Adleman

    Ronald L. Rivest, Adi Shamir, and Leonard Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems . Communications of the ACM , 21(2):120--126, 1978. https://doi.org/10.1145/359340.359342 doi:10.1145/359340.359342

    1978

  54. [62]

    On Matrix Multiplication with Homomorphic Encryption

    Panagiotis Rizomiliotis and Aikaterini Triakosia. On Matrix Multiplication with Homomorphic Encryption . In Cloud Computing Security Workshop (CCSW) , pages 53--61, 2022. https://doi.org/10.1145/3560810.3564267 doi:10.1145/3560810.3564267

    2022

  55. [63]

    Convolution as Matrix Multiplication , 2022

    Ali Salehi. Convolution as Matrix Multiplication , 2022. URL: https://github.com/alisaaalehi/convolution\_as\_multiplication

    2022

  56. [64]

    On the Deployment of Curve Based Cryptography for the Internet of Things

    Michael Scott. On the Deployment of Curve Based Cryptography for the Internet of Things . Cryptology ePrint Archive, Paper 2020/514, 2020. URL: https://eprint.iacr.org/2020/514

    2020

  57. [65]

    Gaussian Elimination is Not Optimal

    Volker Strassen. Gaussian Elimination is Not Optimal . Numerische Mathematik , 13(4):354--356, 1969. https://doi.org/10.1007/BF02165411 doi:10.1007/BF02165411

    1969 doi

  58. [66]

    Secure Outsourced Computation of Multiple Matrix Multiplication Based on Fully Homomorphic Encryption

    Shufang Wang and Hai Huang. Secure Outsourced Computation of Multiple Matrix Multiplication Based on Fully Homomorphic Encryption . KSII Transactions on Internet and Information Systems , 13(11):5616--5630, 2019. https://doi.org/10.3837/tiis.2019.11.019 doi:10.3837/tiis.2019.11.019

    2019 doi

  59. [67]

    The Death and Rebirth of Privacy-Preserving WiFi Fingerprint Localization with Paillier Encryption

    Zheng Yang and Kimmo Jarvinen. The Death and Rebirth of Privacy-Preserving WiFi Fingerprint Localization with Paillier Encryption . In IEEE Conference on Computer Communications (INFOCOM) , pages 1223--1231, 2018. https://doi.org/10.1109/INFOCOM.2018.8486221 doi:10.1109/INFOCO...

    2018

  60. [68]

    Secure Outsourced Matrix Multiplication with Fully Homomorphic Encryption

    Lin Zhu, Qiang-sheng Hua, Yi Chen, and Hai Jin. Secure Outsourced Matrix Multiplication with Fully Homomorphic Encryption . In European Symposium on Research in Computer Security (ESORICS) , pages 249--269, 2023. https://doi.org/10.1007/978-3-031-50594-2_13 doi:10.1007/978-3-0...

    2023 doi

  61. [69]

    A New Framework for Fast Homomorphic Matrix Multiplication

    Xiaopeng Zheng, Hongbo Li, and Dingkang Wang. A New Framework for Fast Homomorphic Matrix Multiplication . Designs, Codes and Cryptography , pages 1--23, 2025. https://doi.org/10.1007/s10623-025-01614-y doi:10.1007/s10623-025-01614-y

    2025 doi

  62. [70]

    Secure Transformer Inference Made Non-Interactive

    Jiawen Zhang, Xinpeng Yang, Lipeng He, Kejia Chen, Wen jie Lu, Yinghao Wang, Xiaoyang Hou, Jian Liu, Kui Ren, and Xiaohu Yang. Secure Transformer Inference Made Non-Interactive . In Network and Distributed System Security Symposium (NDSS) , 2025. https://doi.org/10.14722/ndss....

    2025

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.