Simultaneous approximation problems of p-adic numbers and p-adic knapsack cryptosystems - Alice in p-adic numberland

被引：2

作者：

Inoue H. ^{[1
]}

Kamada S. ^{[1
]}

Naito K. ^{[1
]}

机构：

[1] Department of Applied Mathematics, Graduate School of Science and Technology Kumamoto University, Kurokami 2-39-1, Kumamoto

来源：

P-Adic Numbers, Ultrametric Analysis, and Applications | 2016年 / 8卷 / 4期

基金：

日本学术振兴会;

关键词：

cryptography; LLL algorithm; p-adic theory; simultaneous homogeneous approximation;

D O I：

10.1134/S207004661604004X

中图分类号：

学科分类号：

摘要：

In this paper we construct the multi-dimensional p-adic approximation lattices by using simultaneous approximation problems (SAP) of p-adic numbers and we estimate the l∞ norm of the p-adic SAP solutions theoretically by applying Dirichlet’s principle and numerically by using the LLL algorithm. By using the SAP solutions as private keys, the security of which depends on NP-hardness of SAP or the shortest vector problems (SVP) of p-adic lattices, we propose a p-adic knapsack cryptosystem with commitment schemes, in which the sender Alice prepares ciphertexts and the verification keys in her p-adic numberland. © 2016, Pleiades Publishing, Ltd.

引用

页码：312 / 324

页数：12

共 14 条

[1]

Anashin V., Khrennikov A., Applied Algebraic Dynamics, (2009)

[2]

Anashin V., Khrennikov A., Yurova E., T-functions revisited: New criteria for bijectivity/transitivity, Designs Codes Crypt., 71, pp. 383-407, (2014)

[3]

Bugeaud Y., Approximation by Algebraic Numbers, (2004)

[4]

Coster M.J., Joux A., Lamacchia B.A., Odlyzko A.M., Schnorr C.P., Stern J., Improved low-density subset sum algorithms, Comput. Compl., 2, pp. 111-128, (1992)

[5]

Gama N., Nguyen P.Q., Predicting lattice reduction, EUROCRYPT, LectureNotes in Comp. Sci., 4965, pp. 31-51, (2008)

[6]

The shortest vector problems in p-adic lattices and simultaneous approximation problems of p-adic numbers, (2014)

[7]

Lagarias J.C., The computational complexity of simultaneous Diophantine approximation problems, SIAM J. Computing, 14, pp. 196-209, (1985)

[8]

Lagarias J.C., Odlyzko A.M., Solving low-density subset sum problems, Journal ACM, 32, pp. 229-246, (1985)

[9]

Complexity of lattice problems, a cryptographic perspective, Series in Engineering and Computer Science 671 (Springer, (2002)

[10]

van de Pol J., Smart N.P., Estimating key sizes for high dimensional lattice-based systems, IMA Int. Conf., Lecture Notes in Computer Science, 8308, pp. 290-303, (2013)

← 1 2 →