
-
Previous Article
The $[46, 9, 20]_2$ code is unique
- AMC Home
- This Issue
-
Next Article
Some optimal cyclic $ \mathbb{F}_q $-linear $ \mathbb{F}_{q^t} $-codes
Ironwood meta key agreement and authentication protocol
100 Beard Sawmill Rd, Suite 350, Shelton, CT 06484, USA |
Number theoretic public-key solutions, currently used in many applications worldwide, will be subject to various quantum attacks, making them less attractive for longer-term use. Certain group theoretic constructs are now showing promise in providing quantum-resistant cryptographic primitives, and may provide suitable alternatives for those looking to address known quantum attacks. In this paper, we introduce a new protocol called a Meta Key Agreement and Authentication Protocol (MKAAP) that has some characteristics of a public-key solution and some of a shared-key solution. Specifically, it has the deployment benefits of a public-key system, allowing two entities that have never met before to authenticate without requiring real-time access to a third-party, but does require secure provisioning of key material from a trusted key distribution system (similar to a symmetric system) prior to deployment. We then describe a specific MKAAP instance, the Ironwood MKAAP, discuss its security, and show how it resists certain quantum attacks such as Shor's algorithm or Grover's quantum search algorithm. We also show Ironwood implemented on several "internet of things" (IoT devices), measure its performance, and show how it performs significantly better than ECC using fewer device resources.
References:
[1] |
I. Anshel, M. Anshel, D. Goldfeld and S. Lemieux,
Key agreement, the Algebraic Eraser$^{TM}$, and lightweight cryptography, Algebraic Methods in Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 418 (2006), 1-34.
doi: 10.1090/conm/418/07943. |
[2] |
I. Anshel, D. Atkins, D. Goldfeld and P. E. Gunnells, Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser, arXiv: 1601.04780v1 [cs.CR]. Google Scholar |
[3] |
I. Anshel, D. Atkins, D. Goldfeld and P. E. Gunnells, WalnutDSA$^{TM}$: A Lightweight Quantum Resistant Digital Signature Algorithm, https://eprint.iacr.org/2017/058.pdf. Google Scholar |
[4] |
I. Anshel, M. Anshel and D. Goldfeld,
An algebraic method for public-key cryptography, Math. Res. Lett., 6 (1999), 287-291.
doi: 10.4310/MRL.1999.v6.n3.a3. |
[5] |
E. Artin,
The theory of braids, Annals of Math., 48 (1947), 101-126.
doi: 10.2307/1969218. |
[6] |
D. Atkins and D. Goldfeld, Addressing the algebraic eraser over the air protocol, https://eprint.iacr.org/2016/205.pdf. Google Scholar |
[7] |
A. Ben-Zvi, S. R. Blackburn and B. Tsaban, A practical cryptanalysis of the algebraic eraser, Advances in Cryptology - CRYPTO 2016, Part I, Lecture Notes in Comput. Sci., Springer, Berlin, 9814 (2016), 179–189. http://eprint.iacr.org/2015/1102.
doi: 10.1007/978-3-662-53018-4_7. |
[8] |
S. R. Blackburn and M. J. B. Robshaw, On the security of the algebraic eraser tag authentication protocol, Applied Cryptography and Network Security, Lecture Notes in Comput. Sci., Springer, 9696 (2016), 3–17. http://eprint.iacr.org/2016/091.
doi: 10.1007/978-3-319-39555-5_1. |
[9] |
M. Düll, B. Haase, G. Hinterwälder, M. Hutter, C. Paar, A. H. Sánchez and P. Schwabe, High-speed Curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers, https://eprint.iacr.org/2015/343.pdf. Google Scholar |
[10] |
D. Garber, S. Kaplan, M. Teicher, B. Tsaban and U. Vishne,
Length-based conjugacy search in the braid group, Algebraic Methods in Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 418 (2006), 75-87.
doi: 10.1090/conm/418/07947. |
[11] |
V. Gebhardt,
A new approach to the conjugacy problem in Garside groups, J. Algebra, 292 (2005), 282-302.
doi: 10.1016/j.jalgebra.2005.02.002. |
[12] |
D. Goldfeld and P. E. Gunnells, Defeating the Kalka-Teicher-Tsaban linear algebra attack on the Algebraic Eraser, (2012), arXiv: 1202.0598. Google Scholar |
[13] |
M. I. González Vasco, S. Magliveras and R. Steinwandt, Group-Theoretic Cryptography, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2015.
![]() |
[14] |
L. K. Grover,
A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM, Symposium on the Theory of Computing, ACM, New York, (1996), 212-219.
doi: 10.1145/237814.237866. |
[15] |
P. E. Gunnells, On the cryptanalysis of the generalized simultaneous conjugacy search problem and the security of the Algebraic Eraser, arXiv: 1105.1141v1 [cs.CR]. Google Scholar |
[16] |
D. Hofheinz and R. Steinwandt,
A practical attack on some braid group based cryptographic primitives, Public Key Cryptography—PKC 2003, Lecture Notes in Comput. Sci., Springer, Berlin, 2567 (2002), 187-198.
doi: 10.1007/3-540-36288-6_14. |
[17] |
A. Kalka, M. Teicher and B. Tsaban,
Short expressions of permutations as products and cryptanalysis of the Algebraic Eraser, Advances in Applied Mathematics, 49 (2012), 57-76.
doi: 10.1016/j.aam.2012.03.001. |
[18] |
K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang and C. Park,
New public-key cryptosystem using braid groups, Advances in Cryptology - CRYPTO 2000, Lecture Notes in Computer Science, Springer, Berlin, 1880 (2000), 166-183.
doi: 10.1007/3-540-44598-6_10. |
[19] |
C. Lomont, The hidden subgroup problem - review and open problems, (2004), arXiv: quant-ph/0411037. Google Scholar |
[20] |
H. R. Morton,
The multivariable Alexander polynomial for a closed braid, Low-dimensional topology, Contemp. Math., Amer. Math. Soc., Providence, RI, 233 (1999), 167-172.
doi: 10.1090/conm/233/03427. |
[21] |
C. Mulland and B. Tsaban, $ \rm SL _2$ homomorphic hash functions: Worst case to average case reduction and short collision search, Des. Codes Cryptogr., 81 (2016), 83–107, arXiv: 1306.5646v3 [cs.CR].
doi: 10.1007/s10623-015-0129-8. |
[22] |
A. D. Myasnikov and A. Ushakov,
Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux key agreement protocol, Groups Complex. Cryptol., 1 (2009), 63-75.
doi: 10.1515/GCC.2009.63. |
[23] |
A. Myasnikov, V. Shpilrain and A. Ushakov, Group-Based Cryptography, Advanced Courses in Mathematics, CRM Barcelona Birkhäuser, Basel, 2008. |
[24] |
P. W. Shor,
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing, 26 (1997), 1484-1509.
doi: 10.1137/S0097539795293172. |
[25] |
G. Zémor, Hash functions and graphs with large girths, Eurocrypt '91, Lecture Notes in Computer Science, 547 (1991), 508-511. Google Scholar |
show all references
References:
[1] |
I. Anshel, M. Anshel, D. Goldfeld and S. Lemieux,
Key agreement, the Algebraic Eraser$^{TM}$, and lightweight cryptography, Algebraic Methods in Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 418 (2006), 1-34.
doi: 10.1090/conm/418/07943. |
[2] |
I. Anshel, D. Atkins, D. Goldfeld and P. E. Gunnells, Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser, arXiv: 1601.04780v1 [cs.CR]. Google Scholar |
[3] |
I. Anshel, D. Atkins, D. Goldfeld and P. E. Gunnells, WalnutDSA$^{TM}$: A Lightweight Quantum Resistant Digital Signature Algorithm, https://eprint.iacr.org/2017/058.pdf. Google Scholar |
[4] |
I. Anshel, M. Anshel and D. Goldfeld,
An algebraic method for public-key cryptography, Math. Res. Lett., 6 (1999), 287-291.
doi: 10.4310/MRL.1999.v6.n3.a3. |
[5] |
E. Artin,
The theory of braids, Annals of Math., 48 (1947), 101-126.
doi: 10.2307/1969218. |
[6] |
D. Atkins and D. Goldfeld, Addressing the algebraic eraser over the air protocol, https://eprint.iacr.org/2016/205.pdf. Google Scholar |
[7] |
A. Ben-Zvi, S. R. Blackburn and B. Tsaban, A practical cryptanalysis of the algebraic eraser, Advances in Cryptology - CRYPTO 2016, Part I, Lecture Notes in Comput. Sci., Springer, Berlin, 9814 (2016), 179–189. http://eprint.iacr.org/2015/1102.
doi: 10.1007/978-3-662-53018-4_7. |
[8] |
S. R. Blackburn and M. J. B. Robshaw, On the security of the algebraic eraser tag authentication protocol, Applied Cryptography and Network Security, Lecture Notes in Comput. Sci., Springer, 9696 (2016), 3–17. http://eprint.iacr.org/2016/091.
doi: 10.1007/978-3-319-39555-5_1. |
[9] |
M. Düll, B. Haase, G. Hinterwälder, M. Hutter, C. Paar, A. H. Sánchez and P. Schwabe, High-speed Curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers, https://eprint.iacr.org/2015/343.pdf. Google Scholar |
[10] |
D. Garber, S. Kaplan, M. Teicher, B. Tsaban and U. Vishne,
Length-based conjugacy search in the braid group, Algebraic Methods in Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 418 (2006), 75-87.
doi: 10.1090/conm/418/07947. |
[11] |
V. Gebhardt,
A new approach to the conjugacy problem in Garside groups, J. Algebra, 292 (2005), 282-302.
doi: 10.1016/j.jalgebra.2005.02.002. |
[12] |
D. Goldfeld and P. E. Gunnells, Defeating the Kalka-Teicher-Tsaban linear algebra attack on the Algebraic Eraser, (2012), arXiv: 1202.0598. Google Scholar |
[13] |
M. I. González Vasco, S. Magliveras and R. Steinwandt, Group-Theoretic Cryptography, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2015.
![]() |
[14] |
L. K. Grover,
A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM, Symposium on the Theory of Computing, ACM, New York, (1996), 212-219.
doi: 10.1145/237814.237866. |
[15] |
P. E. Gunnells, On the cryptanalysis of the generalized simultaneous conjugacy search problem and the security of the Algebraic Eraser, arXiv: 1105.1141v1 [cs.CR]. Google Scholar |
[16] |
D. Hofheinz and R. Steinwandt,
A practical attack on some braid group based cryptographic primitives, Public Key Cryptography—PKC 2003, Lecture Notes in Comput. Sci., Springer, Berlin, 2567 (2002), 187-198.
doi: 10.1007/3-540-36288-6_14. |
[17] |
A. Kalka, M. Teicher and B. Tsaban,
Short expressions of permutations as products and cryptanalysis of the Algebraic Eraser, Advances in Applied Mathematics, 49 (2012), 57-76.
doi: 10.1016/j.aam.2012.03.001. |
[18] |
K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang and C. Park,
New public-key cryptosystem using braid groups, Advances in Cryptology - CRYPTO 2000, Lecture Notes in Computer Science, Springer, Berlin, 1880 (2000), 166-183.
doi: 10.1007/3-540-44598-6_10. |
[19] |
C. Lomont, The hidden subgroup problem - review and open problems, (2004), arXiv: quant-ph/0411037. Google Scholar |
[20] |
H. R. Morton,
The multivariable Alexander polynomial for a closed braid, Low-dimensional topology, Contemp. Math., Amer. Math. Soc., Providence, RI, 233 (1999), 167-172.
doi: 10.1090/conm/233/03427. |
[21] |
C. Mulland and B. Tsaban, $ \rm SL _2$ homomorphic hash functions: Worst case to average case reduction and short collision search, Des. Codes Cryptogr., 81 (2016), 83–107, arXiv: 1306.5646v3 [cs.CR].
doi: 10.1007/s10623-015-0129-8. |
[22] |
A. D. Myasnikov and A. Ushakov,
Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux key agreement protocol, Groups Complex. Cryptol., 1 (2009), 63-75.
doi: 10.1515/GCC.2009.63. |
[23] |
A. Myasnikov, V. Shpilrain and A. Ushakov, Group-Based Cryptography, Advanced Courses in Mathematics, CRM Barcelona Birkhäuser, Basel, 2008. |
[24] |
P. W. Shor,
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing, 26 (1997), 1484-1509.
doi: 10.1137/S0097539795293172. |
[25] |
G. Zémor, Hash functions and graphs with large girths, Eurocrypt '91, Lecture Notes in Computer Science, 547 (1991), 508-511. Google Scholar |


Artin Length | MSP430 | LPC1768 | |
2626 | 5272 | 6002668 | 2026216 |
2332 | 3580 | 4532480 | 1538472 |
2414 | 3944 | 4862464 | 1648742 |
3172 | 4266 | 5661952 | 1914009 |
2168 | 4514 | 5101824 | 1728545 |
3092 | 4698 | 5922048 | 2000312 |
2978 | 3968 | 5297664 | 1792959 |
2744 | 4420 | 5459456 | 1845502 |
2430 | 4762 | 5479424 | 1854446 |
2636 | 3600 | 4771840 | 1617670 |
2659.2 | 4302.4 | 5309182 | 1796687 |
Artin Length | MSP430 | LPC1768 | |
2626 | 5272 | 6002668 | 2026216 |
2332 | 3580 | 4532480 | 1538472 |
2414 | 3944 | 4862464 | 1648742 |
3172 | 4266 | 5661952 | 1914009 |
2168 | 4514 | 5101824 | 1728545 |
3092 | 4698 | 5922048 | 2000312 |
2978 | 3968 | 5297664 | 1792959 |
2744 | 4420 | 5459456 | 1845502 |
2430 | 4762 | 5479424 | 1854446 |
2636 | 3600 | 4771840 | 1617670 |
2659.2 | 4302.4 | 5309182 | 1796687 |
Artin Length | MSP430 | LPC1768 | CC2650 48Mhz | ||
25MHz | 48MHz | (SST 5) | (SST 2) | ||
2626 | 5272 | 240.1 | 42.2 | 42 | 42 |
2332 | 3580 | 181.3 | 32.2 | 32 | 32 |
2414 | 3944 | 194.5 | 34.3 | 34 | 35 |
3172 | 4266 | 226.5 | 39.9 | 40 | 40 |
2168 | 4514 | 204.1 | 36.0 | 36 | 36 |
3092 | 4698 | 236.9 | 41.2 | 42 | 42 |
2978 | 3968 | 211.9 | 37.4 | 37 | 37 |
2744 | 4420 | 218.4 | 38.4 | 38 | 39 |
2430 | 4762 | 219.2 | 38.6 | 39 | 39 |
2636 | 3600 | 190.9 | 33.7 | 34 | 34 |
2659.2 | 4302.4 | 212.4 | 37.4 | 37.4 | 37.6 |
Artin Length | MSP430 | LPC1768 | CC2650 48Mhz | ||
25MHz | 48MHz | (SST 5) | (SST 2) | ||
2626 | 5272 | 240.1 | 42.2 | 42 | 42 |
2332 | 3580 | 181.3 | 32.2 | 32 | 32 |
2414 | 3944 | 194.5 | 34.3 | 34 | 35 |
3172 | 4266 | 226.5 | 39.9 | 40 | 40 |
2168 | 4514 | 204.1 | 36.0 | 36 | 36 |
3092 | 4698 | 236.9 | 41.2 | 42 | 42 |
2978 | 3968 | 211.9 | 37.4 | 37 | 37 |
2744 | 4420 | 218.4 | 38.4 | 38 | 39 |
2430 | 4762 | 219.2 | 38.6 | 39 | 39 |
2636 | 3600 | 190.9 | 33.7 | 34 | 34 |
2659.2 | 4302.4 | 212.4 | 37.4 | 37.4 | 37.6 |
[1] |
Alberto Ibort, Alberto López-Yela. Quantum tomography and the quantum Radon transform. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021021 |
[2] |
Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. |
[3] |
Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451 |
[4] |
Sergei Avdonin, Julian Edward. An inverse problem for quantum trees with observations at interior vertices. Networks & Heterogeneous Media, 2021, 16 (2) : 317-339. doi: 10.3934/nhm.2021008 |
[5] |
Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021070 |
[6] |
Xianjun Wang, Huaguang Gu, Bo Lu. Big homoclinic orbit bifurcation underlying post-inhibitory rebound spike and a novel threshold curve of a neuron. Electronic Research Archive, , () : -. doi: 10.3934/era.2021023 |
[7] |
Fang Li, Jie Pan. On inner Poisson structures of a quantum cluster algebra without coefficients. Electronic Research Archive, , () : -. doi: 10.3934/era.2021021 |
[8] |
Yongming Luo, Athanasios Stylianou. On 3d dipolar Bose-Einstein condensates involving quantum fluctuations and three-body interactions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3455-3477. doi: 10.3934/dcdsb.2020239 |
[9] |
José Luis López. A quantum approach to Keller-Segel dynamics via a dissipative nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2601-2617. doi: 10.3934/dcds.2020376 |
2019 Impact Factor: 0.734
Tools
Metrics
Other articles
by authors
[Back to Top]