Abstract
As the world transitions to Post-Quantum Cryptography (PQC), the significant "ciphertext expansion" of standard algorithms like Kyber poses a major challenge for secure group communications. This paper presents mmCipher, the first lattice-based framework that enables a sender to efficiently batch unique messages for multiple recipients with near-optimal bandwidth. By introducing Extended Reproducible PKE (XR-PKE), mmCipher achieves up to a 45x reduction in communication overhead while providing "Full CPA" security, which protects both the content and the structure of the message vector.
1. Introduction
In modern secure messaging platforms like Signal or WhatsApp, a single sender often broadcasts different messages to a large group of recipients. While computationally inexpensive in classical cryptography, this task becomes a bottleneck in the post-quantum era. Standard PQC algorithms produce ciphertexts significantly larger than their corresponding plaintexts. For instance, sending 1,000 independent Kyber ciphertexts to 1,000 recipients creates massive bandwidth overhead.
Existing multi-recipient schemes often suffer from two critical limitations:
- Efficiency Constraints: They are typically only optimized for scenarios where every recipient receives the identical message.
- Security Leakage: Many schemes leak the "structure" of the message vector, allowing an observer to determine if certain recipients are receiving the same message.
mmCipher addresses these gaps by ensuring that all messages are batched together, preventing structure leakage and maintaining high efficiency even for independent messages.
2. Methodology: Extended Reproducible PKE
The core of mmCipher is a new primitive called Extended Reproducible PKE (XR-PKE).
2.1 The Reproducibility Challenge
In discrete-log-based systems (e.g., ElGamal), ciphertexts can be "reproduced" for different recipients by reusing randomness. In lattice-based systems, which rely on the Module Learning with Errors (MLWE) assumption, reusing the "noise" required for security leads to catastrophic failures.
2.2 The "Hint" Mechanism
To overcome this, mmCipher utilizes a "hint generation" algorithm. The sender first creates a single, public-key-independent core ciphertext. For each recipient, the sender then generates a small "hint" based on the estimated decryption error. This hint allows each recipient to reconstruct their specific message without requiring the sender to generate a full, independent ciphertext for every individual.
3. Evaluation and Results
The authors implemented mmCipher in portable C and benchmarked it against the NIST-standardized ML-KEM (Kyber) at various security levels (128-bit, 192-bit, and 256-bit).
3.1 Bandwidth Efficiency
For a group size of 1,024 recipients, mmCipher-KEM demonstrates a 23–45x reduction in bandwidth overhead compared to individual Kyber transmissions. The total multi-recipient ciphertext is remarkably compact, measuring only 4–9% larger than the raw plaintexts. The scheme becomes more efficient than standard Kyber for any group larger than four recipients.
3.2 Computational Performance
By sharing the most computationally expensive lattice operations across the entire group, mmCipher reduces the sender's computational load by 3–5x for large groups.
4. Discussion and Future Work
While mmCipher provides a significant leap in PQC scalability, some areas remain for future optimization:
- KOSK Assumption: The current construction assumes public keys are well-formed (Knowledge of Secret Key). While a NIZK-based solution is provided to relax this, it introduces additional overhead.
- Gaussian Sampling: Future production versions will require high-precision, constant-time discrete Gaussian samplers to mitigate side-channel risks.
- Adaptive Security: Further research is needed to optimize protections against adaptive corruption in lattice-based multi-recipient settings.
5. Conclusion
mmCipher represents a major advancement in making post-quantum group communication practical. By leveraging the properties of decryption errors in lattice cryptography, it provides a bandwidth-optimal solution that scales efficiently to thousands of recipients without compromising security.
Summary updated