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

[3]

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

[4]

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

[5]

M. E. Hellman, An overview of public key cryptography,, IEEE Commun. Soc. M., 16 (1978), 24.  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), (1998), 267.  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), 98.   Google Scholar

[8]

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

[9]

G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions,, Adv. Math. Commun., 1 (2007), 489.  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.   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.   Google Scholar

[12]

D. Naccache and J. Stern, New public key cryptosystem,, in Proceedings of Eurocrypt 97, (1997), 27.  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, (2000), 147.  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.   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.  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.  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.  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.   Google Scholar

[3]

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

[4]

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

[5]

M. E. Hellman, An overview of public key cryptography,, IEEE Commun. Soc. M., 16 (1978), 24.  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), (1998), 267.  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), 98.   Google Scholar

[8]

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

[9]

G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions,, Adv. Math. Commun., 1 (2007), 489.  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.   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.   Google Scholar

[12]

D. Naccache and J. Stern, New public key cryptosystem,, in Proceedings of Eurocrypt 97, (1997), 27.  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, (2000), 147.  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.   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.  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.  doi: 10.2307/2008704.  Google Scholar

[1]

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

Wenjun Liu, Yukun Xiao, Xiaoqing Yue. Classification of finite irreducible conformal modules over Lie conformal algebra $ \mathcal{W}(a, b, r) $. Electronic Research Archive, , () : -. doi: 10.3934/era.2020123
[3]

Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111
[4]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053
[5]

Peter H. van der Kamp, D. I. McLaren, G. R. W. Quispel. Homogeneous darboux polynomials and generalising integrable ODE systems. Journal of Computational Dynamics, 2021, 8 (1) : 1-8. doi: 10.3934/jcd.2021001
[6]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[7]

He Zhang, John Harlim, Xiantao Li. Estimating linear response statistics using orthogonal polynomials: An RKHS formulation. Foundations of Data Science, 2020, 2 (4) : 443-485. doi: 10.3934/fods.2020021
[8]

Ágota P. Horváth. Discrete diffusion semigroups associated with Jacobi-Dunkl and exceptional Jacobi polynomials. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021002
[9]

Jianfeng Huang, Haihua Liang. Limit cycles of planar system defined by the sum of two quasi-homogeneous vector fields. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 861-873. doi: 10.3934/dcdsb.2020145
[10]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[11]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363
[12]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178
[13]

Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020122
[14]

Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020121
[15]

Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095
[16]

Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020127
[17]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[18]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[19]

Bin Wang, Lin Mu. Viscosity robust weak Galerkin finite element methods for Stokes problems. Electronic Research Archive, 2021, 29 (1) : 1881-1895. doi: 10.3934/era.2020096
[20]

Xiu Ye, Shangyou Zhang, Peng Zhu. A weak Galerkin finite element method for nonlinear conservation laws. Electronic Research Archive, 2021, 29 (1) : 1897-1923. doi: 10.3934/era.2020097

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences