# American Institute of Mathematical Sciences

• Previous Article
Generalized Hamming weights of toric codes over hypersimplices and squarefree affine evaluation codes
• AMC Home
• This Issue
• Next Article
New quantum codes from metacirculant graphs via self-dual additive $\mathbb{F}_4$-codes
doi: 10.3934/amc.2022031
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## Public key cryptography based on twisted dihedral group algebras

 1 Department of Mathematics and Statistics, Universidad del Norte, Barranquilla, Colombia 2 Department of Computer Science and Engineering, Universidad del Norte, Barranquilla, Colombia

*Corresponding author: Ricardo Villanueva-Polanco

Received  November 2021 Revised  March 2022 Early access April 2022

In this paper, we propose to use a twisted dihedral group algebra for public-key cryptography. For this, we introduce a new $2$-cocycle $\alpha_{\lambda}$ to twist the dihedral group algebra. Using the ambient space $\mathbb{F}^{\alpha_{\lambda}} D_{2n}$, we then introduce a key exchange protocol and present an analysis of its security. Moreover, we explore the properties of the resulting twisted algebra $\mathbb{F}^{\alpha_{\lambda}}D_{2n}$, exploiting them to enhance our key exchange protocol. We also introduce a probabilistic public-key scheme derived from our key-exchange protocol and obtain a key encapsulation mechanism (KEM) by applying a well-known generic transformation to our public-key scheme. Finally, we present a proof-of-concept implementation of the resulting key encapsulation mechanism.

Citation: Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, doi: 10.3934/amc.2022031
##### References:
 [1] C. Bader, D. Hofheinz, T. Jager, E. Kiltz and Y. Li, Tightly-secure authenticated key exchange, In: Dodis Y., Nielsen J.B. (eds) Theory of Cryptography. Part I., 629–658, TCC 2015. Lecture Notes in Computer Science, vol 9014. Springer, Berlin, Heidelberg, 2015. doi: 10.1007/978-3-662-46494-6_26. [2] D. Boneh and V. Shoup, A Graduate Course in Applied Cryptography, 2020, available at http://toc.cryptobook.us/book.pdf. [3] R. Canetti and H. Krawczyk, Analysis of key-exchange protocols and their use for building secure channels, In: Pfitzmann B. (eds) Advances in Cryptology-EUROCRYPT 2001. (Innsbruck), 453–474, Lecture Notes in Computer Science, vol 2045. Springer, Berlin, Heidelberg, 2001. doi: 10.1007/3-540-44987-6_28. [4] C. Costello, L. De Feo, D. Jao, P. Longa, M. Naehrig and J. Renes, Supersingular Isogeny Key Encapsulation, 2020, available at https://sike.org/files/SIDH-spec.pdf. [5] J. De La Cruz and R. Villanueva-Polanco, Implementation of a key encapsulation mechanism based on a twisted dihedral group algebra, available at https://colab.research.google.com/drive/1FWcNYzNgZgSfMMBSXMq1nOCsowLzW-Ht?usp=sharing. [6] J. De La Cruz and W. Willems, Twisted group codes, IEEE Trans. Inform. Theory, 67 (2021), 5178-5184.  doi: 10.1109/TIT.2021.3089003. [7] M. J. Dworkin, SHA-3 standard: Permutation-based hash and extendable-output functions, Federal Inf. Process. Stds. (NIST FIPS), 2015. doi: 10.6028/NIST.FIPS.202. [8] M. Eftekhari, Cryptanalysis of some protocols using matrices over group rings, In: Joye M., Nitaj A. (eds) Progress in Cryptology - AFRICACRYPT 2017. AFRICACRYPT 2017,223–229. Lecture Notes in Computer Science, vol 10239. Springer, Cham. doi: 10.1007/978-3-319-57339-7_13. [9] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, In: Blakley G.R., Chaum D. (eds) Advances in Cryptology. CRYPTO 1984, 10–18, Lecture Notes in Computer Science, vol 196. Springer, Berlin, 1985. doi: 10.1007/3-540-39568-7_2. [10] M. D. Gómez Olvera, J. A. López Ramos and B. Torrecillas Jover, Public key protocols over twisted dihedral group rings, Symmetry, 2019 (2019), 11, 1019. doi: 10.3390/sym11081019. [11] L. K. Grover, A fast quantum mechanical algorithm for database search, In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pages 212–219. ACM, 1996. doi: 10.1145/237814.237866. [12] D. Hofheinz, K. Hövelmanns and E. Kiltz, A modular analysis of the Fujisaki-Okamoto transformation, Theory of cryptography. Part I, 341–371, Lecture Notes in Comput. Sci., 10677, Springer, Cham, 2017. [13] T. Jager, E. Kiltz, D. Riepel and S. Schäge, Tightly-Secure Authenticated Key Exchange, Revisited, Cryptology ePrint Archive: Report 2020/1279, 2020., Available at https://eprint.iacr.org/2020/1279 [14] D. Kahrobaei, C. Koupparis and V. Shpilrain, Public key exchange using matrices over group rings, Groups Complex. Cryptology, 5 (2013), 97-115.  doi: 10.1515/gcc-2013-0007. [15] M. Linckelmann, The Block Theory of Finite Groups, London Math. Soc., Textbook 92, Cambridge Uni. Press. [16] J. A. López-Ramos, J. Rosenthal, D. Schipani and R. Schnyder, An application of group theory in confidential network communications, Math. Meth. Apply Sci., 41 (2018), 2294-2298.  doi: 10.1002/mma.4244. [17] G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions, Adv. Math. Commun., 1 (2007), 489-507.  doi: 10.3934/amc.2007.1.489. [18] National Institute of Standards and Technology, NIST Post-Quantum Cryptography, available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions. [19] V. Roman'kov, A general encryption scheme using two-sided multiplications with its cryptanalysis, arXiv (2017), available at https://arXiv.org/abs/1709.06282. [20] V. Roman'kov, Two general schemes of algebraic cryptography, Groups Complex. Cryptol., 10 (2018), 83-98.  doi: 10.1515/gcc-2018-0009. [21] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41 (1999), 303-332.  doi: 10.1137/S0036144598347011. [22] V. Shoup, Sequences of games: A tool for taming complexity in security proofs, Cryptology ePrint Archive, Report 2004/332 (2004), available at http://eprint.iacr.org/2004/332. [23] J. Suo, L. Wang, S. Yang, W. Zheng and J. Zhang, Quantum algorithms for typical hard problems: A perspective of cryptanalysis, Quantum Inf. Process., 19 (2020), Paper No. 178, 26 pp. doi: 10.1007/s11128-020-02673-x. [24] W. Willems, Codierungstheorie, deGruyter, Berlin, 1999.

show all references

##### References:
 [1] C. Bader, D. Hofheinz, T. Jager, E. Kiltz and Y. Li, Tightly-secure authenticated key exchange, In: Dodis Y., Nielsen J.B. (eds) Theory of Cryptography. Part I., 629–658, TCC 2015. Lecture Notes in Computer Science, vol 9014. Springer, Berlin, Heidelberg, 2015. doi: 10.1007/978-3-662-46494-6_26. [2] D. Boneh and V. Shoup, A Graduate Course in Applied Cryptography, 2020, available at http://toc.cryptobook.us/book.pdf. [3] R. Canetti and H. Krawczyk, Analysis of key-exchange protocols and their use for building secure channels, In: Pfitzmann B. (eds) Advances in Cryptology-EUROCRYPT 2001. (Innsbruck), 453–474, Lecture Notes in Computer Science, vol 2045. Springer, Berlin, Heidelberg, 2001. doi: 10.1007/3-540-44987-6_28. [4] C. Costello, L. De Feo, D. Jao, P. Longa, M. Naehrig and J. Renes, Supersingular Isogeny Key Encapsulation, 2020, available at https://sike.org/files/SIDH-spec.pdf. [5] J. De La Cruz and R. Villanueva-Polanco, Implementation of a key encapsulation mechanism based on a twisted dihedral group algebra, available at https://colab.research.google.com/drive/1FWcNYzNgZgSfMMBSXMq1nOCsowLzW-Ht?usp=sharing. [6] J. De La Cruz and W. Willems, Twisted group codes, IEEE Trans. Inform. Theory, 67 (2021), 5178-5184.  doi: 10.1109/TIT.2021.3089003. [7] M. J. Dworkin, SHA-3 standard: Permutation-based hash and extendable-output functions, Federal Inf. Process. Stds. (NIST FIPS), 2015. doi: 10.6028/NIST.FIPS.202. [8] M. Eftekhari, Cryptanalysis of some protocols using matrices over group rings, In: Joye M., Nitaj A. (eds) Progress in Cryptology - AFRICACRYPT 2017. AFRICACRYPT 2017,223–229. Lecture Notes in Computer Science, vol 10239. Springer, Cham. doi: 10.1007/978-3-319-57339-7_13. [9] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, In: Blakley G.R., Chaum D. (eds) Advances in Cryptology. CRYPTO 1984, 10–18, Lecture Notes in Computer Science, vol 196. Springer, Berlin, 1985. doi: 10.1007/3-540-39568-7_2. [10] M. D. Gómez Olvera, J. A. López Ramos and B. Torrecillas Jover, Public key protocols over twisted dihedral group rings, Symmetry, 2019 (2019), 11, 1019. doi: 10.3390/sym11081019. [11] L. K. Grover, A fast quantum mechanical algorithm for database search, In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pages 212–219. ACM, 1996. doi: 10.1145/237814.237866. [12] D. Hofheinz, K. Hövelmanns and E. Kiltz, A modular analysis of the Fujisaki-Okamoto transformation, Theory of cryptography. Part I, 341–371, Lecture Notes in Comput. Sci., 10677, Springer, Cham, 2017. [13] T. Jager, E. Kiltz, D. Riepel and S. Schäge, Tightly-Secure Authenticated Key Exchange, Revisited, Cryptology ePrint Archive: Report 2020/1279, 2020., Available at https://eprint.iacr.org/2020/1279 [14] D. Kahrobaei, C. Koupparis and V. Shpilrain, Public key exchange using matrices over group rings, Groups Complex. Cryptology, 5 (2013), 97-115.  doi: 10.1515/gcc-2013-0007. [15] M. Linckelmann, The Block Theory of Finite Groups, London Math. Soc., Textbook 92, Cambridge Uni. Press. [16] J. A. López-Ramos, J. Rosenthal, D. Schipani and R. Schnyder, An application of group theory in confidential network communications, Math. Meth. Apply Sci., 41 (2018), 2294-2298.  doi: 10.1002/mma.4244. [17] G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions, Adv. Math. Commun., 1 (2007), 489-507.  doi: 10.3934/amc.2007.1.489. [18] National Institute of Standards and Technology, NIST Post-Quantum Cryptography, available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions. [19] V. Roman'kov, A general encryption scheme using two-sided multiplications with its cryptanalysis, arXiv (2017), available at https://arXiv.org/abs/1709.06282. [20] V. Roman'kov, Two general schemes of algebraic cryptography, Groups Complex. Cryptol., 10 (2018), 83-98.  doi: 10.1515/gcc-2018-0009. [21] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41 (1999), 303-332.  doi: 10.1137/S0036144598347011. [22] V. Shoup, Sequences of games: A tool for taming complexity in security proofs, Cryptology ePrint Archive, Report 2004/332 (2004), available at http://eprint.iacr.org/2004/332. [23] J. Suo, L. Wang, S. Yang, W. Zheng and J. Zhang, Quantum algorithms for typical hard problems: A perspective of cryptanalysis, Quantum Inf. Process., 19 (2020), Paper No. 178, 26 pp. doi: 10.1007/s11128-020-02673-x. [24] W. Willems, Codierungstheorie, deGruyter, Berlin, 1999.
Proposed parameters
 $p$ $m$ $n$ $l_1$ (bits) $l$ (bits) $19$ $1$ $19$ $\{128, 192, 256\}$ $124$ $23$ $1$ $23$ $\{128, 192, 256\}$ $149$ $31$ $1$ $31$ $\{128, 192, 256\}$ $200$ $41$ $1$ $41$ $\{128, 192, 256\}$ $264$
 $p$ $m$ $n$ $l_1$ (bits) $l$ (bits) $19$ $1$ $19$ $\{128, 192, 256\}$ $124$ $23$ $1$ $23$ $\{128, 192, 256\}$ $149$ $31$ $1$ $31$ $\{128, 192, 256\}$ $200$ $41$ $1$ $41$ $\{128, 192, 256\}$ $264$
 [1] Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247 [2] Yu-Chi Chen. Security analysis of public key encryption with filtered equality test. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021053 [3] Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052 [4] Mohammad Sadeq Dousti, Rasool Jalili. FORSAKES: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. Advances in Mathematics of Communications, 2015, 9 (4) : 471-514. doi: 10.3934/amc.2015.9.471 [5] Xinwei Gao. Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants. Advances in Mathematics of Communications, 2019, 13 (2) : 221-233. doi: 10.3934/amc.2019015 [6] Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215 [7] Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells. Ironwood meta key agreement and authentication protocol. Advances in Mathematics of Communications, 2021, 15 (3) : 397-413. doi: 10.3934/amc.2020073 [8] Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023 [9] Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281 [10] Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489 [11] Rainer Steinwandt, Adriana Suárez Corona. Attribute-based group key establishment. Advances in Mathematics of Communications, 2010, 4 (3) : 381-398. doi: 10.3934/amc.2010.4.381 [12] Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046 [13] Hongyan Guo. Automorphism group and twisted modules of the twisted Heisenberg-Virasoro vertex operator algebra. Electronic Research Archive, 2021, 29 (4) : 2673-2685. doi: 10.3934/era.2021008 [14] Riccardo Aragona, Marco Calderini, Roberto Civino. Some group-theoretical results on Feistel Networks in a long-key scenario. Advances in Mathematics of Communications, 2020, 14 (4) : 727-743. doi: 10.3934/amc.2020093 [15] Yvo Desmedt, Niels Duif, Henk van Tilborg, Huaxiong Wang. Bounds and constructions for key distribution schemes. Advances in Mathematics of Communications, 2009, 3 (3) : 273-293. doi: 10.3934/amc.2009.3.273 [16] Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. [17] Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2-party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 87-92. doi: 10.3934/amc.2011.5.87 [18] Yang Lu, Quanling Zhang, Jiguo Li. An improved certificateless strong key-insulated signature scheme in the standard model. Advances in Mathematics of Communications, 2015, 9 (3) : 353-373. doi: 10.3934/amc.2015.9.353 [19] Jake Bouvrie, Boumediene Hamzi. Kernel methods for the approximation of some key quantities of nonlinear systems. Journal of Computational Dynamics, 2017, 4 (1&2) : 1-19. doi: 10.3934/jcd.2017001 [20] Sikhar Patranabis, Debdeep Mukhopadhyay. Identity-based key aggregate cryptosystem from multilinear maps. Advances in Mathematics of Communications, 2019, 13 (4) : 759-778. doi: 10.3934/amc.2019044

2021 Impact Factor: 1.015