Funciones pseudoaleatorias inconscientes en grupos no conmutativos
DOI:
https://doi.org/10.5281/zenodo.17445479Palabras clave:
criptografía no conmutativa, elemento conjugador, funciones pseudoaleatorias inconscientes, protocolos criptográficos, MSC 20F12, MSC 20F18, MSC 20H20, MSC 94A60Resumen
Las aplicaciones de las funciones pseudoaleatorias inconscientes en la criptografía y en la seguridad de la información son múltiples. Pueden citarse la derivación de claves basadas en contraseñas, acuerdo de claves basados en contraseñas, password hardening, CAPTCHAs imposibles de rastrear, acuerdo de claves homomórfico y la intersección de conjuntos segura. Los primeros trabajos se basan en protocolos para la transferencia inconsciente, computación multiparte segura o en algunas variantes del problema del logaritmo discreto. Recientemente han surgido propuestas postcuánticas basadas en las isogenias de curvas elípticas y en los problemas sobre lattices. En este trabajo se propone el diseño de una función pseudoaleatoria inconsciente que base su seguridad en la dificultad de encontrar el elemento conjugador en grupos no conmutativos. Se realiza además un experimento utilizando como plataforma el grupo discreto de Heisenberg sobre un campo finito.
Descargas
Citas
[1] Albrecht, M.R., Davidson, A., Deo, A., and Smart, N.P. (2021). Round-optimal verifiable oblivious pseudorandom functions from ideal lattices. In Garay, J.A. (editor): Public-Key Cryptography – PKC 2021, pages 261-289. Springer International Publishing. https://doi.org/10.1007/978-3-030-75248-4_10
[2] Anjaneyulu, G.S.G.N., Reddy, P.V., and Reddy, U.M. (2008). Secured digital signature scheme using polynomials over non-commutative division semirings. International Journal of Computer Science and Network Security, 8(8):278. http://paper.ijcsns.org/07_book/200808/20080839.pdf
[3] Anshel, I., Anshel, M., and Goldfeld, D. (1999). An algebraic method for public-key cryptography. Mathematical Research Letters, 6:287-291. https://api.semanticscholar.org/CorpusID:11621019
[4] Basso, A. (2024). A post-quantum round-optimal oblivious prf from isogenies. In Selected Areas in Cryptography - SAC 2023, pages 147-168. Springer-Verlag. https://doi.org/10.1007/978-3-031-53368-6_8
[5] Battarbee, C., Kahrobaei, D., Perret, L., and Shahandashti, S.F. (2023). Spdh-sign: towards efficient, post-quantum group-based signatures. In International Conference on Post-Quantum Cryptography, pages 113-138. Springer. https://doi.org/10.1007/978-3-031-40003-2_5
[6] Battarbee, C., Kahrobaei, D., Perret, L., and Shahandashti, S.F. (2024). A subexponential quantum algorithm for the semidirect discrete logarithm problem. In International Conference on Post-Quantum Cryptography, pages 202-226. Springer. https://doi.org/10.1007/978-3-031-62743-9_7
[7] Binz, E. and Pods, S. (2008). The Geometry of Heisenberg Groups: With Applications in Signal Theory, Optics, Quantization, and Field Quantization. American Mathematical Society. https://books.google.com.cu/books?id=yIP0BwAAQBAJ
[8] Boneh, D., Kogan, D., and Woo, K. (2020). Oblivious pseudorandom functions from isogenies. In Moriai, S. and Wang, H. (editors): Advances in Cryptology – ASIACRYPT 2020, pages 520-550. Springer International Publishing. https://doi.org/10.1007/978-3-030-64834-3_18
[9] Boneh, D. and Shoup, V. (2023). A graduate course in applied cryptography. https://toc.cryptobook.us/book.pdf
[10] Cao, Z., Dong, X., and Wang, L. (2007). New public key cryptosystems using polynomials over non-commutative rings. IACR Cryptol. ePrint Arch., 2007:9. https://api.semanticscholar.org/CorpusID:14026951
[11] Carvalho, A. and Malheiro, A. (2025). Subsets of groups in public-key cryptography. Advances in Mathematics of Communications, 19(3):980-995. https://doi.org/10.3934/amc.2024036
[12] Chaum, D. and Pedersen, T.P. (1993). Wallet databases with observers. In Brickell, E.F. (editor): Advances in Cryptology – CRYPTO' 92, pages 89-105. Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-48071-4_7
[13] Cumplido, M., Kahrobaei, D., and Noce, M. (2024). The root extraction problem in braid group-based cryptography. La Matematica, 3(3):1207-1217. https://link.springer.com/content/pdf/10.1007/s44007-024-00117-x.pdf
[14] Freedman, M.J., Ishai, Y., Pinkas, B., and Reingold, O. (2005). Keyword search and oblivious pseudorandom functions. In Kilian, J. (editor): Theory of Cryptography, pages 303-324. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-30576-7_17
[15] González Vasco, M.I., Kahrobaei, D., and McKemmie, E. (2024). Applications of finite non-abelian simple groups to cryptography in the quantum era. La Matematica, 3(2):588-603. https://doi.org/10.1007/s44007-024-00096-z
[16] Grigoriev, D. and Ponomarenko, I. (2005). Constructions in public-key cryptography over matrix groups. https://hal.science/hal-03047011/document
[17] Hazay, C. and Lindell, Y. (2008). Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In Canetti, R. (editor): Theory of Cryptography, pages 155-175. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-78524-8_10
[18] Herstein, I.N. (2012). Álgebra Moderna. Trillas, 2nd edition. https://www.academia.edu/14931038/Algebra_Moderna_Herstein
[19] Hungerford, T.W. (1974). Groups, pages 23-69. Springer New York. https://doi.org/10.1007/978-1-4612-6101-8_2
[20] Jarecki, S., Kiayias, A., and Krawczyk, H. (2014). Round-Optimal Password-Protected Secret Sharing and TPAKE in the Password-Only Model. In Sarkar, P. and Iwata, T. (editors): Advances in Cryptology – ASIACRYPT 2014, pages 233-253. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-45608-8_13
[21] Jarecki, S., Krawczyk, H., and Resch, J. (2019). Updatable Oblivious Key Management for Storage Systems. In CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 379-393. Association for Computing Machinery. https://doi.org/10.1145/3319535.3363196
[22] Jarecki, S., Krawczyk, H., and Xu, J. (2018). OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-computation Attacks. In Nielsen, J.B. and Rijmen, V. (editors): Advances in Cryptology – EUROCRYPT 2018, pages 456-486. Springer International Publishing. https://doi.org/10.1007/978-3-319-78372-7_15
[23] Kahrobaei, D., Flores, R., and Noce, M. (2022). Group-based cryptography in the quantum era. Cryptology ePrint Archive, Paper 2022 1161. https://eprint.iacr.org/2022/1161
[24] Kahrobaei, D. and Lam, H.T. (2014). Heisenberg groups as platform for the aag key-exchange protocol. In 2014 IEEE 22nd International Conference on Network Protocols, pages 660-664. https://doi.org/10.1109/ICNP.2014.105
[25] Kahrobaei, D., Noce, M., and Rodaro, E. (2024). Applications of automaton groups in cryptography. International Journal of Computer Mathematics: Computer Systems Theory, 9(2):96-106. https://doi.org/10.1080/23799927.2024.2335157
[26] Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J., and Park, C. (2000). New Public-Key Cryptosystem Using Braid Groups. In Bellare, M. (editor): Advances in Cryptology – CRYPTO 2000, pages 166-183. Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-44598-6_10
[27] Kolesnikov, V., Kumaresan, R., Rosulek, M., and Trieu, N. (2016). Efficient batched oblivious prf with applications to private set intersection. In Proceedings of the ACM Conference on Computer and Communications Security, pages 818-829. Association for Computing Machinery. https://doi.org/10.1145/2976749.2978381
[28] Kostrikin, A.I. (1983). Introducción al álgebra. Mir. https://archive.org/details/kostrikin-introduccion-al-algebra-mir-1983
[29] Menezes, A., van Oorschot, P.C., and Vanstone, S.A. (1996). Handbook of Applied Cryptography. CRC Press. https://theswissbay.ch/pdf/Gentoomen%20Library/Cryptography/Handbook%20of%20Applied%20Cryptography%20-%20Alfred%20J.%20Menezes.pdf
[30] Moriya, T., Onuki, H., and Takagi, T. (2020). Sigamal: A supersingular isogeny-based pke and its application to a prf. In Advances in Cryptology - ASIACRYPT 2020, pages 551-580. Springer-Verlag. https://doi.org/10.1007/978-3-030-64834-3_19
[31] Myasnikov, A., Shpilrain, V., and Ushakov, A. (2011). Non-Commutative Cryptography and Complexity of Group-Theoretic Problems. American Mathematical Society. https://dl.acm.org/doi/10.5555/2161874
[32] Naor, M. and Reingold, O. (1997). Number-theoretic constructions of efficient pseudo-random functions. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 458-467. https://doi.org/10.1109/SFCS.1997.646134
[33] Pan, P., Wang, L., Wang, L., Li, L., and Yang, Y. (2012). CSPDHIES: a new public-key encryption scheme from matrix conjugation. Security and Communication Networks, 5(7):809-822. https://doi.org/10.1002/sec.376
[34] Rotman, J.J. (2003). Advanced Modern Algebra. Prentice Hall, 2nd edition. https://share.google/aCcDkPO1CbxXLIACh
[35] Shoup, V. (2009). A Computational Introduction to Number Theory and Algebra. Cambridge University Press, 2nd edition. https://shoup.net/ntb
[36] Shpilrain, V. and Ushakov, A. (2005). Thompson's Group and Public Key Cryptography. In Ioannidis, J., Keromytis, A., and Yung, M. (editors): Applied Cryptography and Network Security, pages 151-163. Springer Berlin Heidelberg. https://doi.org/10.1007/11496137_11
[37] Sibert, H., Dehornoy, P., and Girault, M. (2006). Entity authentication schemes using braid word reduction. Discrete Applied Mathematics, 154(2):420-436. https://doi.org/10.1016/j.dam.2005.03.015
[38] Tinani, S., Matteotti, C., and Rosenthal, J. (2023). Cryptanalysis of some nonabelian group-based key exchange protocols. https://arxiv.org/abs/2203.03525
[39] Wang, T. and Xu, Z. (2023). The application of group theory behind modern cryptography. Theoretical and Natural Science, 13:195-201. https://doi.org/10.54254/2753-8818/13/20240844
[40] Zhao, M., Wang, H., and Yao, B. (2023). Graphic groups, graph homomorphisms, and graphic group lattices in asymmetric topology cryptography. Entropy, 25(5):720. https://doi.org/10.3390/e25050720
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2025 David Ricardo Ledo Baster, Huber Martínez Rodríguez
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
Esta licencia permite copiar y redistribuir el material en cualquier medio o formato bajo los siguientes términos: se debe dar crédito de manera adecuada, no se puede hacer uso del material con propósitos comerciales, y si remezcla, transforma o crea a partir del material, no podrá distribuir el material modificado. Bajo la licencia mencionada, los autores mantienen los derechos de autor de su trabajo.
