Abstract Fully Homomorphic Encryption (FHE) enables arbitrary computations on encrypted data, a paradigm that Multi-Key FHE (MKFHE) extends to the decentralized setting by supporting operations on ciphertexts encrypted under multiple, distinct keys. However, the high computational cost of bootstrapping remains a major bottleneck, especially in the multi-key scenario where blind rotation is the dominant overhead. To address this, we propose a novel and parallel-friendly blind rotation scheme based on the NTRU assumption for efficient MKFHE bootstrapping. Our core technical contribution is a grouped inner product algorithm optimized for automorphism-based blind rotation, which reorganizes hybrid product storage and extends the external product to be compatible with both NTRU and MK-RLWE ciphertexts. Our parallelized algorithm reduces the time complexity from O ( n ) to $$O(\sqrt{n})$$ O ( n ) . Our scheme demonstrates significant improvements over prior MKFHE works in both computational efficiency and storage requirements. At a 100-bit security level with $$k=8$$ k = 8 participants, our scheme achieves a ciphertext bootstrapping time of 0.048 seconds, representing a $$6.8 \times$$ 6.8 × speedup compared to Kwak et al.’s state-of-the-art work. Furthermore, our scheme substantially reduces storage overhead, requiring only 81.5MB for evaluation keys ( $$1.7 \times$$ 1.7 × smaller) and 64KB for re-linearization keys ( $$6.0 \times$$ 6.0 × smaller) relative to Kwak et al.’s implementation.

Abstract Toward practical and client-friendly single-server private information retrieval, we introduce FlashPIR, a scheme achieving both low client overhead and high server throughput. Constructed based on fully homomorphic encryption, our protocol possesses two distinct advantages: First, a majority of the resource-intensive computations can be performed in an offline phase, prior to query reception, significantly reducing the online response time. Second, database updates operate independently of clients, with low client computational overhead remaining nearly constant regardless of the database scale. We conducted comprehensive experiments to evaluate the performance of FlashPIR. The results demonstrate that for database sizes of 256 MB, our scheme achieves a throughput $$2.6\times$$ 2.6 × greater than KsPIR (Luo et al., CCS 2024) and $$18.5\times$$ 18.5 × greater than Spiral (Menon and Wu, S&P 2022).

Verifiable Computation over encrypted data (VCoed) has two popular paradigms: SNARK-FHE (applying SNARKs to prove FHE operations) and FHE-SNARK (homomorphically evaluating SNARK proofs). For the existing works, FHE-SNARK has a much better efficiency compared to SNARK-FHE.

Let (D,S,χ,m)-LWEn,q be the LWE problem in matrix form (A,y=As+emodq), where A,s,e are randomly chosen respectively from the seed distribution D over Zqm×n, secret distribution S over Zqn and noise distribution χm over Zm (or Rm), i.e., A←D,s←S,e←χm. For various secret-noise distributions (S,χ), the (D,S,χ,m)-LWEn,q problem is shown to be as hard as some standard worst-case lattice problems, but most of the known results require D to be the uniform distribution over Zqm×n. In this paper, we show that under the standard LWE assumption, the problem (D,S,χ,m)-LWEn,q can still be hard for some distribution D that is not (even computationally indistinguishable from) the uniform distribution over Zqm×n. Specifically, we show that if D is a semi-uniform distribution over Zqm×n (namely, D can be publicly derived from and has a “small difference” to the uniform distribution over Zqm×n), then for appropriate choices of (S,χ), the problem (D,S,χ,m)-LWEn,q is hard under the standard LWE assumption. Moreover, we also show that the semi-uniform MLWE problem is hard under the standard MLWE assumption. As a direct application, our results pave the way to prove the security of public-key encryptions with rounded public keys under the standard (M)LWE assumption.