A general construction for monoid-based knapsack protocols

Giacomo Micheli; Michele Schiavina

doi:10.3934/amc.2014.8.343

Article Contents

2014, Volume 8, Issue 3: 343-358. Doi: 10.3934/amc.2014.8.343

This issue Previous Article How to obtain division algebras used for fast-decodable space-time block codes Next Article Sets of frequency hopping sequences under aperiodic Hamming correlation: Upper bound and optimal constructions

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

Received: November 2013

Revised: February 2014

Published: August 2014

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94A60; Secondary: 11T71.

Citation:

Related Papers

Cited by

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.
[2]	W. Diffie and M. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory, 22 (1976), 644-654.
[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.
[4]	P. Erdös, Ramanujan and I, Resonance, 3 (1998), 81-92.
[5]	M. E. Hellman, An overview of public key cryptography, IEEE Commun. Soc. M., 16 (1978), 24-32.doi: 10.1109/MCOM.1978.1089772.
[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.
[7]	S. Kiuchi, Y. Murakami and M. Kasahara, High rate mulitiplicative knapsack cryptosystem (in Japanese), IEICE Tech. Report, ISEC98-26 (1998), 43-50.
[8]	S. Kiuchi, Y. Murakami and M. Kasahara, New mulitiplicative knapsack-type public key cryptosystems, IEICE Trans., E84-A (2001), 188-196.
[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.
[10]	R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report, 114 (1978), 42-44.
[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.
[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.
[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.
[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.
[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.
[16]	M. Rosen, Number Theory in Function Fields, Springer, 2002.doi: 10.1007/978-1-4757-6046-0.
[17]	A. Salomaa, Public Key Cryptography, Springer-Verlag, 1990doi: 10.1007/978-3-662-02627-4.
[18]	V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comput., 54 (1990), 435-447.doi: 10.2307/2008704.