Dynamic Multi-Key Block Binary Ring-Compact Bootstrapping

Multi-Key Fully Homomorphic Encryption (MK-FHE) is essential for secure multi-party computation but currently faces significant scalability bottlenecks due to linear computational growth and low bootstrapping throughput. To address these limitations, we propose DMBB-RCB, a novel fully homomorphic, bit-wise Dynamic Multi-Key Block-Binary Ring-Compact Bootstrapping scheme. Our contribution is threefold. First, we integrate the Block Binary Distribution into the dynamic setting, reducing the complexity of the core blind rotation operation from O(P⋅n) to O(p⋅k) (where k ≪ n) by leveraging key sparsity. Second, we implement an amortized ring packing strategy that aggregates multiple Learning with Errors (LWE) ciphertexts into the coefficients of a single Ring Learning with Errors (RLWE) polynomial, enabling the parallel refreshing of messages. Third, we introduce a Ring-Compact extraction architecture that natively translates RLWE states into Multi-Key Regev–Gentry–Sahai–Waters (RGSW) ciphertexts via scheme switching. Unlike traditional pipelines that suffer from severe network latency due to interactive multi-party key-switching after each bootstrapping, our architecture keeps the data entirely within the ring domain. This completely eliminates intermediate interaction rounds, enabling depth-unbounded homomorphic evaluations with zero interaction between participants during the computation phase (interaction is strictly reserved for the final joint decryption step). The proposed scheme supports the dynamic addition of participants without parameter re-generation. Theoretical analysis confirms that DMBB-RCB significantly reduces latency and enhances throughput compared to existing dynamic MKHE solutions.