Técnicas de compressão de chaves para criptossistemas baseados em isogenias

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

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

Resumo

Criptografia baseada em isogenias supersingulares constitui uma das famílias mais recentes dentre as propostas resistentes a ataques com computadores quânticos. Destaca-se sua baixa ocupação de banda em comparação a outros protocolos de acordo de chave, potencializada pela possibilidade de compressão de chaves ao custo de uma sobrecarga significativa no tempo de processamento. Neste trabalho, sugerem-se técnicas eficientes para minimizar os principais gargalos de processamento envolvidos na compressão e descompressão de chaves. Em conjunto, essas técnicas produzem ganhos observados de até três vezes em relação aos melhores resultados de técnicas anteriormente propostas.

Referências

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.