A Bit-Optimal, Provably Secure Encryption Scheme from any Trapdoor Permutation

Authors

  • Tola John Odule
    Olabisi Onabanjo University, Ago-Iwoye
  • Khadijat-Kubrat Adebisi Abdullah
    Olabisi Onabanjo University, Ago-Iwoye
  • Samuel Oluwatosin Hassan
    Olabisi Onabanjo University, Ago-Iwoye
  • Femi Emmanuel Ayo
    Olabisi Onabanjo University, Ago-Iwoye
  • Sefiu Adekunle Onitilo
    Olabisi Onabanjo University, Ago-Iwoye

Keywords:

Asymmetric encryption,, provable security,, one-way invertible function,, ciphertext indistinguishability,, idealized hash function paradigm

Abstract

This study presents a provably secure asymmetric encryption scheme designed for optimal efficiency. A transmitter utilizes a -bit one-way invertible function  to encode a message  for a receptor holding the inverse . The construction ensures that encryption requires only a single computation of , decryption requires only a single computation of , the ciphertext length is exactly  bits, and the permissible message length  is nearly . The method employs a probabilistic encoding of  into a string , with the ciphertext given by . Under the assumption of industry-standard compression function with any one-way invertible function, we describe and rigorously prove the security of this invertible enmesh scheme. The scheme is bit-optimal, allowing for the encryption of messages of length close to , and achieves semantic security—a strong notion that implies security against chosen-ciphertext attacks (CCA) and non-malleability in the standard-hash model.

Dimensions

Agrawal, S., & Pellet-Mary, C. (2022). Indistinguishability Obfuscation Without Maps: Proofs and Techniques. In Advances in Cryptology – CRYPTO 2022 (pp. 3-35). Springer, Cham.

Albrecht, M. R., et al. (2021). The Status of Quantum-Safe Cryptography Migration. ACM Communications in Computer Algebra, 55(3), 112-115.

Barker, E. (2022). NIST SP 800-57 Part 1 Rev. 5: Recommendation for Key Management: Part 1 – General. National Institute of Standards and Technology.

Bellare, M., & Rogaway, P. (1994). Optimal Asymmetric Encryption. In A.De Santis (Ed.) Advances in Cryptology – EUROCRYPT ’94 (pp. 92-111). Springer, Berlin Heidelberg. https://doi.org/10.1007/BFb0053428

Bernstein, D. J., & Lange, T. (2023). Post-Quantum Cryptography: Current State and Future Challenges. Annual Review of Cybersecurity, 5(1), 45-72.

Boneh, D., & Corrigan-Gibbs, H. (2021). The Random Oracle Model: A Twenty-Year Retrospective. Communications of the ACM, 64(8), 76-84. https://doi.org/10.1145/3466680

Canetti, R., et al. (2023). A Framework for Universal Composability with Stateful Applications. Journal of Cryptology, 36(2), 12.

Chakraborty, S., & Sánchez, D. (2024). Lightweight Post-Quantum Encryption for IoT Devices. IEEE Transactions on Dependable and Secure Computing, 21(2), 1234-1248.

Chase, M., et al. (2022). The Privacy of the TLS 1.3 Protocol. In 2022 IEEE Symposium on Security and Privacy (SP), (pp, 1154-1171). IEEE.

Durak, F. B., & Vaudenay, S. (2023). On the Impossibility of Instantiating the Random Oracle Model with Weaker Primitives. In Advances in Cryptology – CRYPTO 2023 (pp. 123-155). Springer.

Gentry, C., & Halevi, S. (2021). Compiler for Fully Homomorphic Encryption with Approximate Bootstrapping. In 2021 IEEE Symposium on Security and Privacy (SP) (pp. 147-167). IEEE.

Gentry, C., et al. (2021). Puncturable Key Wrapping and Its Applications. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security 2067-2083.

Goldwasser, S. & Micali, S. (1984). “Probabilistic Encryption,” Journal of Computer and System Sciences 28, 270-299.

Katz_28, J., & Lindell, Y. (2020). Introduction to modern cryptography (3rd ed.). Chapman and Hall/CRC. https://doi.org/10.1201/9781351133036

Klooß, M., & Rupp, A. (2022). Formal Verification of a Compact Encryption Scheme's CCA2 Security. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, (pp. 2101-2115).

Micciancio, D., & Walter, M. (2023). On the Bit Security of Cryptographic Primitives. SIAM Journal on Computing, 52(1), 1-46.

National Institute of Standards and Technology (NIST). (2023). FIPS 180-5: Secure Hash Standard (SHS). Gaithersburg, MD, USA. https://doi.org/10.6028/NIST.FIPS.180-5

National Institute of Standards and Technology (NIST). (2023). FIPS 204: Module-Lattice-Based Digital Signature Standard.

Peikert, C., & Shiehian, S. (2021). Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors. Journal of Cryptology, 34(3), 25. https://doi.org/10.1007/s00145-021-09383-2

Vadhan, S. P. (2023). The Science of Guessing: Probabilistic Computation and the Design of Modern Cryptography. In Proceedings of the International Congress of Mathematicians (ICM 2022) 7, (pp. 4125-4150). EMS Press. https://doi.org/10.4171/ICM2022/110

Key differences for a \mathbit{k}-bit security parameter (e.g., a \mathbit{k}-bit RSA modulus) and a secondary parameter \mathbit{k}_\mathbf{0} (e.g., 128 bits)

Published

2025-11-09

How to Cite

Odule, T. J., Abdullah, K.-K. A., Hassan, S. O., Ayo, F. E., & Onitilo, S. A. (2025). A Bit-Optimal, Provably Secure Encryption Scheme from any Trapdoor Permutation. Nigerian Journal of Physics, 34(4), 128-136. https://doi.org/10.62292/10.62292/njp.v34i4.2025.455

Issue

Vol. 34 No. 4 (2025): Nigerian Journal of Physics - Vol. 34 No. 4

Section

Articles
Copyright & Licensing

How to Cite

Odule, T. J., Abdullah, K.-K. A., Hassan, S. O., Ayo, F. E., & Onitilo, S. A. (2025). A Bit-Optimal, Provably Secure Encryption Scheme from any Trapdoor Permutation. Nigerian Journal of Physics, 34(4), 128-136. https://doi.org/10.62292/10.62292/njp.v34i4.2025.455

Most read articles by the same author(s)