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