Key compression techniques for cryptosystems

• Gustavo H. M. Zanon USP
• Marcos A. Simplicio Jr. USP

DOI: https://doi.org/10.5753/sbseg_estendido.2022.225550

Abstract

Supersingular isogeny-based cryptography is one of the most recent families among proposals resistant to attacks with quantum computers. Its low bandwidth occupation is noteworthy compared to other key agreement protocols, enhanced by the possibility of key compression at the cost of a significant overhead in processing time. In this work, efficient techniques are suggested to minimize the main processing bottlenecks involved in key compression and decompression. Together, these techniques produce observed gains of up to three times over the best results of previously proposed techniques.

References

Alkim, E., Ducas, L., Pöppelmann, T., and Schwabe, P. (2016). Post-quantum key exchange: A new hope. In Proceedings of the 25th USENIX Conference on Security Symposium, SEC’16, page 327–343, USA. USENIX Association.

Aragon, N., Barreto, P. S. L. M., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Gaborit, P., Gueron, S., Guneysu, T., Aguilar Melchor, C., Misoczki, R., Persichetti, E., Sendrier, N., Tillich, J.-P., and Zemor, G. (2017). BIKE: Bit Flipping Key Encapsulation. Submission to the NIST post quantum standardization process.

Azarderakhsh, R., Jao, D., Kalach, K., Koziel, B., and Leonardi, C. (2016). Key compression for isogeny-based cryptosystems. In Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography, pages 1–10, Abu Dhabi, EAU. ACM.

Bahajji, Z. A. (2015). Indexing https pages by default. https://webmasters.googleblog.com/2015/12/indexing-https-pages-by-default.html. Acessado em 4 de agosto de 2019.

Braithwaite, M. (2016). Experimenting with post-quantum cryptography. https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html. Acessado em 5 de agosto de 2019.

Costello, C., Jao, D., Longa, P., Naehrig, M., Renes, J., and Urbanik, D. (2017). Efficient compression of SIDH public keys. In Advances in Cryptology – Eurocrypt 2017, number 10210 in Lecture Notes in Computer Science, pages 679–706, Paris, France. Springer.

DeFeo, L., Jao, D., and Plût, J. (2014). Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Journal of Mathematical Cryptology, 8(3):209–247.

Doliskani, J., Pereira, G. C. C. F., and Barreto, P. S. L. M. (2017). Faster cryptographic hash function from supersingular isogeny graphs. Cryptology ePrint Archive, Report 2017/1202. https://eprint.iacr.org/2017/1202.

Lidzborski, N. (2014). Staying at the forefront of email security and reliability: Https-only and 99.978 percent availability. [link]. Acessado em 4 de agosto de 2019.

Naehrig, M. and Renes, J. (2019). Dual isogenies and their application to public-key compression for isogeny-based cryptography. In Galbraith, S. D. and Moriai, S., editors, Advances in Cryptology – ASIACRYPT 2019, pages 243–272, Cham. Springer International Publishing.

Peng, W., Wang, B., Hu, F., Wang, Y., Fang, X., Chen, X., and Wang, C. (2019). Factoring larger integers with fewer qubits via quantum annealing with optimized parameters. Science China Physics, Mechanics and Astronomy, 62.

Pereira, G., Doliskani, J., and Jao, D. (2020). x-only point addition formula and faster compressed sike. Journal of Cryptographic Engineering, pages 1–13.

Schaefer, E. and Stoll, M. (2004). How to do a p-descent on an elliptic curve. Transactions of the American Mathematical Society, 356(3):1209–1231.

Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS ’94, pages 124–134, Washington, DC, USA. IEEE Computer Society.

Zanon, G. H. M., Simplicio Jr, M. A., Pereira, G. C. C. F., Doliskani, J., and Barreto, P. S. L. M. (2018). Faster isogeny-based compressed key agreement. In International Workshop on Post-Quantum Cryptography – PQCrypto 2018, volume 10786 of Lecture Notes in Computer Science, pages 248–268, Fort Lauderdale (FL), US. Springer.

Zanon, G. H. M., Simplicio Jr, M. A., Pereira, G. C. C. F., Doliskani, J., and Barreto, P. S. L. M. (2019). Faster key compression for isogeny-based cryptosystems. IEEE Transactions on Computers, 68(5):688–701.