American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Sets of frequency hopping sequences under aperiodic Hamming correlation: Upper bound and optimal constructions
  • AMC Home
  • This Issue
  • Next Article
    How to obtain division algebras used for fast-decodable space-time block codes
August  2014, 8(3): 343-358. doi: 10.3934/amc.2014.8.343

A general construction for monoid-based knapsack protocols

Giacomo Micheli 1, and  Michele Schiavina 1,

1. 

Institut für Mathematik, Winterthurerstrasse 190, Zürich, CH8057, Switzerland, Switzerland

Received  November 2013 Revised  February 2014 Published  August 2014

We present a generalized version of the knapsack protocol proposed by D. Naccache and J. Stern at the Proceedings of Eurocrypt (1997). Our new framework will allow the construction of other knapsack protocols having similar security features. We will outline a very concrete example of a new protocol using extension fields of a finite field of small characteristic instead of the prime field $\mathbb{Z}/p\mathbb{Z}$, but more efficient in terms of computational costs for asymptotically equal information rate and similar key size.
Keywords: polynomials over finite fields, Naccache-Stern protocol., monoids, Public key encryption, knapsack protocols.
Mathematics Subject Classification: Primary: 94A60; Secondary: 11T7.
Citation: Giacomo Micheli, Michele Schiavina. A general construction for monoid-based knapsack protocols. Advances in Mathematics of Communications, 2014, 8 (3) : 343-358. doi: 10.3934/amc.2014.8.343
References:
[1]

B. Chevallier-Mames, D. Naccache and J. Stern, Linear bandwidth Naccache-Stern encryption, in Security and Cryptography for Networks, 2008, 337-339. doi: 10.1007/978-3-540-85855-3_22.  Google Scholar

[2]

W. Diffie and M. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory, 22 (1976), 644-654.  Google Scholar

[3]

T. ElGamal, A public-key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inf. Theory, 31 (1985), 469-472. doi: 10.1109/TIT.1985.1057074.  Google Scholar

[4]

P. Erdös, Ramanujan and I, Resonance, 3 (1998), 81-92. Google Scholar

[5]

M. E. Hellman, An overview of public key cryptography, IEEE Commun. Soc. M., 16 (1978), 24-32. doi: 10.1109/MCOM.1978.1089772.  Google Scholar

[6]

J. Hoffstein, J. Pipher and J. H. Silverman, A ring based public key cryptosystem, in Algorithmic Number Theory (ANTS III), (ed. J.P. Buhler), Springer-Verlag, Berlin, 1998, 267-288. doi: 10.1007/BFb0054868.  Google Scholar

[7]

S. Kiuchi, Y. Murakami and M. Kasahara, High rate mulitiplicative knapsack cryptosystem (in Japanese), IEICE Tech. Report, ISEC98-26 (1998), 43-50. Google Scholar

[8]

S. Kiuchi, Y. Murakami and M. Kasahara, New mulitiplicative knapsack-type public key cryptosystems, IEICE Trans., E84-A (2001), 188-196. Google Scholar

[9]

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.  Google Scholar

[10]

R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report, 114 (1978), 42-44. Google Scholar

[11]

M. Morii and M. Kasahara, New public key cryptosystem using discrete logarithms over GF(P) (in Japanese), IEICE Trans., J71-D (1988), 448-453. Google Scholar

[12]

D. Naccache and J. Stern, New public key cryptosystem, in Proceedings of Eurocrypt 97, Springer-Verlag, 1997, 27-36. doi: 10.1007/3-540-69053-0_3.  Google Scholar

[13]

T. Okamoto, K. Tamaka and S. Uchiyama, Quantum public key cryptosystem, in Advances in cryptology - CRYPTO 2000, Springer, 2000, 147-165. doi: 10.1007/3-540-44598-6_9.  Google Scholar

[14]

J. Patarin, Hidden field equations HFE and isomorphisms of polynomials IP: two new families of asymmetric algorithms, in Advances in Cryptology - EUROCRYPT '96, 1996, 33-48. Google Scholar

[15]

R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120-126. doi: 10.1145/359340.359342.  Google Scholar

[16]

M. Rosen, Number Theory in Function Fields, Springer, 2002. doi: 10.1007/978-1-4757-6046-0.  Google Scholar

[17]

A. Salomaa, Public Key Cryptography, Springer-Verlag, 1990 doi: 10.1007/978-3-662-02627-4.  Google Scholar

[18]

V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comput., 54 (1990), 435-447. doi: 10.2307/2008704.  Google Scholar

show all references

References:
[1]

B. Chevallier-Mames, D. Naccache and J. Stern, Linear bandwidth Naccache-Stern encryption, in Security and Cryptography for Networks, 2008, 337-339. doi: 10.1007/978-3-540-85855-3_22.  Google Scholar

[2]

W. Diffie and M. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory, 22 (1976), 644-654.  Google Scholar

[3]

T. ElGamal, A public-key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inf. Theory, 31 (1985), 469-472. doi: 10.1109/TIT.1985.1057074.  Google Scholar

[4]

P. Erdös, Ramanujan and I, Resonance, 3 (1998), 81-92. Google Scholar

[5]

M. E. Hellman, An overview of public key cryptography, IEEE Commun. Soc. M., 16 (1978), 24-32. doi: 10.1109/MCOM.1978.1089772.  Google Scholar

[6]

J. Hoffstein, J. Pipher and J. H. Silverman, A ring based public key cryptosystem, in Algorithmic Number Theory (ANTS III), (ed. J.P. Buhler), Springer-Verlag, Berlin, 1998, 267-288. doi: 10.1007/BFb0054868.  Google Scholar

[7]

S. Kiuchi, Y. Murakami and M. Kasahara, High rate mulitiplicative knapsack cryptosystem (in Japanese), IEICE Tech. Report, ISEC98-26 (1998), 43-50. Google Scholar

[8]

S. Kiuchi, Y. Murakami and M. Kasahara, New mulitiplicative knapsack-type public key cryptosystems, IEICE Trans., E84-A (2001), 188-196. Google Scholar

[9]

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.  Google Scholar

[10]

R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report, 114 (1978), 42-44. Google Scholar

[11]

M. Morii and M. Kasahara, New public key cryptosystem using discrete logarithms over GF(P) (in Japanese), IEICE Trans., J71-D (1988), 448-453. Google Scholar

[12]

D. Naccache and J. Stern, New public key cryptosystem, in Proceedings of Eurocrypt 97, Springer-Verlag, 1997, 27-36. doi: 10.1007/3-540-69053-0_3.  Google Scholar

[13]

T. Okamoto, K. Tamaka and S. Uchiyama, Quantum public key cryptosystem, in Advances in cryptology - CRYPTO 2000, Springer, 2000, 147-165. doi: 10.1007/3-540-44598-6_9.  Google Scholar

[14]

J. Patarin, Hidden field equations HFE and isomorphisms of polynomials IP: two new families of asymmetric algorithms, in Advances in Cryptology - EUROCRYPT '96, 1996, 33-48. Google Scholar

[15]

R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120-126. doi: 10.1145/359340.359342.  Google Scholar

[16]

M. Rosen, Number Theory in Function Fields, Springer, 2002. doi: 10.1007/978-1-4757-6046-0.  Google Scholar

[17]

A. Salomaa, Public Key Cryptography, Springer-Verlag, 1990 doi: 10.1007/978-3-662-02627-4.  Google Scholar

[18]

V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comput., 54 (1990), 435-447. doi: 10.2307/2008704.  Google Scholar

[1]

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
[2]

Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459
[3]

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
[4]

Stefania Fanali, Massimo Giulietti, Irene Platoni. On maximal curves over finite fields of small order. Advances in Mathematics of Communications, 2012, 6 (1) : 107-120. doi: 10.3934/amc.2012.6.107
[5]

Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203-227. doi: 10.3934/amc.2012.6.203
[6]

Francis N. Castro, Carlos Corrada-Bravo, Natalia Pacheco-Tallaj, Ivelisse Rubio. Explicit formulas for monomial involutions over finite fields. Advances in Mathematics of Communications, 2017, 11 (2) : 301-306. doi: 10.3934/amc.2017022
[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]

Fatma-Zohra Benahmed, Kenza Guenda, Aicha Batoul, Thomas Aaron Gulliver. Some new constructions of isodual and LCD codes over finite fields. Advances in Mathematics of Communications, 2019, 13 (2) : 281-296. doi: 10.3934/amc.2019019
[12]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[13]

Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101
[14]

Nian Li, Qiaoyu Hu. A conjecture on permutation trinomials over finite fields of characteristic two. Advances in Mathematics of Communications, 2019, 13 (3) : 505-512. doi: 10.3934/amc.2019031
[15]

Liren Lin, Hongwei Liu, Bocong Chen. Existence conditions for self-orthogonal negacyclic codes over finite fields. Advances in Mathematics of Communications, 2015, 9 (1) : 1-7. doi: 10.3934/amc.2015.9.1
[16]

Lei Lei, Wenli Ren, Cuiling Fan. The differential spectrum of a class of power functions over finite fields. Advances in Mathematics of Communications, 2021, 15 (3) : 525-537. doi: 10.3934/amc.2020080
[17]

László Mérai, Igor E. Shparlinski. Unlikely intersections over finite fields: Polynomial orbits in small subgroups. Discrete & Continuous Dynamical Systems, 2020, 40 (2) : 1065-1073. doi: 10.3934/dcds.2020070
[18]

Uwe Helmke, Jens Jordan, Julia Lieb. Probability estimates for reachability of linear systems defined over finite fields. Advances in Mathematics of Communications, 2016, 10 (1) : 63-78. doi: 10.3934/amc.2016.10.63
[19]

David Grant, Mahesh K. Varanasi. Duality theory for space-time codes over finite fields. Advances in Mathematics of Communications, 2008, 2 (1) : 35-54. doi: 10.3934/amc.2008.2.35
[20]

Amin Sakzad, Mohammad-Reza Sadeghi, Daniel Panario. Cycle structure of permutation functions over finite fields and their applications. Advances in Mathematics of Communications, 2012, 6 (3) : 347-361. doi: 10.3934/amc.2012.6.347

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (77)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences