International Association
for Cryptologic Research

Homomorphically multiplying a plaintext matrix with a ciphertext matrix (PC-MM) is a central task for the private evaluation of transformers, commonly used for large language models. We provide several RLWE-based algorithms for PC-MM that consist of multiplications of plaintext matrices (PC-MM) and comparatively cheap pre-processing and post-processing steps: for small and large dimensions compared to the RLWE ring degree, and with and without precomputation. For the algorithms with precomputation, we show how to perform a \pcmm with a single floating-point PC-MM of the same dimensions. This is particularly meaningful for practical purposes as a floating-point PC-MM can be implemented using high-performance BLAS libraries. The algorithms rely on the multi-secret variant of RLWE, which allows to represent multiple ciphertexts more compactly. We give algorithms to convert from usual shared-secret RLWE ciphertexts to multi-secret ciphertexts and back. Further, we show that this format is compatible with homomorphic addition, plaintext-ciphertext multiplication, and key-switching. This in turn allows us to accelerate the slots-to-coeffs and coeffs-to-slots steps of CKKS bootstrapping when several ciphertexts are bootstrapped at once. Combining batch-bootstrapping with efficient PC-MM results in MaMBo (Matrix Multiplication Bootstrapping), a bootstrapping algorithm that can perform a PC-MM for a limited overhead.

We describe an algorithm to solve the approximate Shortest Vector Problem for lattices corresponding to ideals of the ring of integers of an arbitrary number field K. This algorithm has a pre-processing phase, whose run-time is exponential in  $$\log |\varDelta |$$ log|Δ| with  $$\varDelta $$ Δ the discriminant of K. Importantly, this pre-processing phase depends only on K. The pre-processing phase outputs an “advice”, whose bit-size is no more than the run-time of the query phase. Given this advice, the query phase of the algorithm takes as input any ideal I of the ring of integers, and outputs an element of I which is at most $$\exp (\widetilde{O}((\log |\varDelta |)^{\alpha +1}/n))$$ exp(O~((log|Δ|)α+1/n)) times longer than a shortest non-zero element of I (with respect to the Euclidean norm of its canonical embedding). This query phase runs in time and space $$\exp (\widetilde{O}( (\log |\varDelta |)^{\max (2/3, 1-2\alpha )}))$$ exp(O~((log|Δ|)max(2/3,1-2α))) in the classical setting, and $$\exp (\widetilde{O}((\log |\varDelta |)^{1-2\alpha }))$$ exp(O~((log|Δ|)1-2α)) in the quantum setting. The parameter $$\alpha $$ α can be chosen arbitrarily in [0, 1 / 2]. Both correctness and cost analyses rely on heuristic assumptions, whose validity is consistent with experiments.The algorithm builds upon the algorithms from Cramer et al. [EUROCRYPT 2016] and Cramer et al. [EUROCRYPT 2017]. It relies on the framework from Buchmann [Séminaire de théorie des nombres 1990], which allows to merge them and to extend their applicability from prime-power cyclotomic fields to all number fields. The cost improvements are obtained by allowing precomputations that depend on the field only.