Kyfrog KEM, with 0.5 MiB Ciphertexts, Achieves High Security Using Learning-with-Errors and ML-KEM Inspiration

The increasing need for robust data security drives ongoing research into post-quantum cryptography, and a new key-encapsulation mechanism, KyFrog, offers a compelling approach to safeguarding information in the face of potential attacks from future quantum computers.

Victor Duarte Melo, an independent researcher, and Willian J. Buchanan from Edinburgh Napier University, developed KyFrog as a conservative Learning-with-Errors (LWE) scheme that prioritises security through a unique parameter selection. Unlike many existing schemes that favour small key and ciphertext sizes, KyFrog employs larger dimensions and carefully chosen error distributions to achieve a high security margin against known lattice attacks, as estimated by the Lattice Estimator. While this strategy results in a significantly larger ciphertext size, the public and secret keys remain comparable to those of the established ML-KEM standard, representing a valuable trade-off for applications demanding the highest levels of protection. LWE-Based KEM Prioritizes Extreme Security KyFrog is a new key-encapsulation mechanism built on the Learning With Errors problem, a post-quantum cryptographic approach designed to resist attacks from future quantum computers. The primary goal of KyFrog is extremely high security, even if it means larger ciphertext sizes, prioritizing robustness and a substantial security margin over efficiency. Scientists carefully selected conservative parameters to maximize security, resulting in a design that offers a significant advantage in long-term protection. The design achieves a substantial security margin, exceeding that of many other post-quantum KEMs, though this comes with a trade-off: ciphertexts are significantly larger, reaching approximately 0. 5 MiB. Public and secret key sizes are 1440 and 2048 bytes respectively, while the current security estimate, based on lattice attack models, is approximately 325 bits against both classical and quantum attacks. A complete C++23 implementation is available, enabling reproducibility and detailed analysis. To find optimal parameters, the team developed KyFrog Hunter, a tool that automates the search for suitable parameter sets. This tool explored various values while maintaining other parameters, ultimately identifying a modulus of 1103 within a region of acceptable settings. The results demonstrate a methodology for parameter selection, focusing on maximizing estimated security against lattice attacks under conservative models, rather than minimizing bandwidth. KyFrog is designed to be resistant to attacks from both classical and quantum computers, and the security estimate is based on the lattice estimator, a tool for assessing LWE-based schemes. This makes KyFrog well-suited for protecting high-value master keys, cryptocurrency wallets with infrequent access, and long-term records where confidentiality is paramount. While not ideal for low-bandwidth scenarios due to its large ciphertext size, KyFrog serves as a valuable platform for studying conservative LWE parameter sets. Future work includes thorough evaluation of side-channel vulnerabilities, exploring compression techniques to reduce ciphertext size, and investigating alternative parameter combinations to optimize the balance between security and efficiency.

The team also plans to integrate KyFrog into higher-level protocols and encourage independent cryptanalysis. KyFrog Parameter Selection for Lattice Security Researchers engineered KyFrog, a Learning-with-Errors key-encapsulation mechanism, to explore a different design point compared to standard schemes, prioritizing long-term security over compact ciphertext size. This work utilizes a dimension of 1024 and a prime modulus of 1103, coupled with narrow error distributions possessing standard deviations of 1. 4, to achieve approximately 325 bits of classical and quantum security against state-of-the-art lattice attacks. Security levels were estimated using the Lattice Estimator, integrated into an automated pipeline called KyFrog Hunter, which systematically explores and validates candidate parameter sets. Scientists developed KyFrog Hunter, an automated system that integrates the Lattice Estimator to assess the security of various parameter combinations. This tool allows for rigorous validation of candidate parameter sets, ensuring a robust security margin.

The team meticulously documented key-generation reports and KyFrog Hunter run statistics to provide transparency and reproducibility. Experiments employed a construction where the ciphertext size reaches approximately 0. 5 MiB, a deliberate trade-off for enhanced security. The research team implemented a full C++23 implementation of KyFrog, incorporating constant-time coding and careful randomness management to mitigate potential side-channel attacks. Benchmarking was conducted to assess performance characteristics, and the team explored potential use cases, including key escrow, cold-wallet key wrapping, and archival protection of high-value secrets, where a large security margin is paramount. This approach delivers a substantial security buffer against future cryptanalytic advances, even at the expense of increased ciphertext size. KyFrog Achieves 325-bit Post-Quantum Security KyFrog represents a significant departure in post-quantum cryptographic design, prioritizing a different operating point than existing schemes. Researchers achieved a design utilizing a large dimension of 1024 and a small prime modulus of 1103, coupled with narrow error distributions possessing standard deviations of 1. 4. This approach targets approximately 325 bits of classical security against state-of-the-art lattice attacks, as estimated using the Lattice Estimator. The work demonstrates a trade-off, accepting an extremely large KEM ciphertext size of approximately 524,813 bytes, while maintaining public and secret key sizes comparable to existing standards at 1440 and 2048 bytes respectively. The KyFrog construction relies on a standard Learning-with-Errors foundation, employing a 1024-dimensional lattice and carefully chosen parameters to balance security and performance.

The team implemented a Fujisaki, Okamoto-style KEM transform, mirroring the structure of existing schemes, but without the optimizations provided by Number Theoretic Transforms. The resulting ciphertext encoding consists of a header, followed by 256 independently encrypted bits. Data shows that the key generation process expands a 256-bit seed into a public matrix and secret vectors, resulting in a compact 1440-byte public key.

Researchers Conclusion KyFrog represents a new approach to key encapsulation, achieving a high level of security by prioritizing a conservative parameter set and accepting a large ciphertext size. Researchers developed this Learning-with-Errors-based mechanism with dimensions of 1024, a prime modulus of 1103, and narrow error distributions, targeting approximately 325 bits of classical and quantum security. This design offers a substantial security margin beyond currently standardized parameter sets, providing a buffer against evolving lattice attacks.

The team successfully implemented and tested KyFrog, creating a complete open-source C++23 implementation and releasing associated experimental data for reproducibility and collaboration. Through automated parameter searches, they identified numerous candidate sets meeting stringent security and correctness thresholds, demonstrating the feasibility of this approach. While KyFrog’s ciphertexts are significantly larger, approximately 0. 5 MiB, than those of other schemes, its public and secret key sizes remain comparable to existing standards. The authors acknowledge that the large ciphertext size represents a trade-off and future work will focus on exploring alternative encodings and compression schemes to mitigate this. Further research will also investigate integrating KyFrog into higher-level protocols, such as secure messaging systems, and encouraging independent cryptanalytic review to validate its security claims.

The team provides a reference key-generation instance and all associated data to facilitate this ongoing work. 👉 More information 🗞 KyFrog: A High-Security LWE-Based KEM Inspired by ML-KEM 🧠 ArXiv: https://arxiv.org/abs/2512.06411 Tags: