{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T10:15:57Z","timestamp":1777371357861,"version":"3.51.4"},"reference-count":49,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T00:00:00Z","timestamp":1550707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key R&amp;D Program of China","award":["2017YFB0802000"],"award-info":[{"award-number":["2017YFB0802000"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1736111"],"award-info":[{"award-number":["U1736111"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100018607","name":"Plan For Scientific Innovation Talent of Henan Province","doi-asserted-by":"publisher","award":["184100510012"],"award-info":[{"award-number":["184100510012"]}],"id":[{"id":"10.13039\/501100018607","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Program for Science&amp;Technology Innovation Talents in Universities of He\u2019nan Province","award":["18HASTIT022"],"award-info":[{"award-number":["18HASTIT022"]}]},{"name":"Key Technologies R&amp;D Program of He'nan Province","award":["182102210123"],"award-info":[{"award-number":["182102210123"]}]},{"name":"Foundation of He'nan Educational Committee","award":["16A520025 and 18A520047"],"award-info":[{"award-number":["16A520025 and 18A520047"]}]},{"name":"Foundation for University Key Teacher of He'nan Province","award":["2016GGJS-141"],"award-info":[{"award-number":["2016GGJS-141"]}]},{"DOI":"10.13039\/501100013082","name":"Open Project Foundation of Information Technology Research Base of Civil Aviation Administration of China","doi-asserted-by":"publisher","award":["CAAC-ITRB-201702"],"award-info":[{"award-number":["CAAC-ITRB-201702"]}],"id":[{"id":"10.13039\/501100013082","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>By introducing an easy knapsack-type problem, a probabilistic knapsack-type public key cryptosystem (PKCHD) is proposed. It uses a Chinese remainder theorem to disguise the easy knapsack sequence. Thence, to recover the trapdoor information, the implicit attacker has to solve at least two hard number-theoretic problems, namely integer factorization and simultaneous Diophantine approximation problems. In PKCHD, the encryption function is nonlinear about the message vector. Under the re-linearization attack model, PKCHD obtains a high density and is secure against the low-density subset sum attacks, and the success probability for an attacker to recover the message vector with a single call to a lattice oracle is negligible. The infeasibilities of other attacks on the proposed PKCHD are also investigated. Meanwhile, it can use the hardest knapsack vector as the public key if its density evaluates the hardness of a knapsack instance. Furthermore, PKCHD only performs quadratic bit operations which confirms the efficiency of encrypting a message and deciphering a given cipher-text.<\/jats:p>","DOI":"10.3390\/info10020075","type":"journal-article","created":{"date-parts":[[2019,2,22]],"date-time":"2019-02-22T03:49:44Z","timestamp":1550807384000},"page":"75","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["PKCHD: Towards a Probabilistic Knapsack Public-Key Cryptosystem with High Density"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7703-4637","authenticated-orcid":false,"given":"Yuan","family":"Ping","sequence":"first","affiliation":[{"name":"School of Information Engineering, Xuchang University, Xuchang 461000, China"},{"name":"Information Technology Research Base of Civil Aviation Administration of China, Civil Aviation University of China, Tianjin 300300, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baocang","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Information Engineering, Xuchang University, Xuchang 461000, China"},{"name":"Key Laboratory of Computer Networks and Information Security, Ministry of Education, Xidian University, Xi\u2019an 710071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shengli","family":"Tian","sequence":"additional","affiliation":[{"name":"School of Information Engineering, Xuchang University, Xuchang 461000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingxian","family":"Zhou","sequence":"additional","affiliation":[{"name":"Information Technology Research Base of Civil Aviation Administration of China, Civil Aviation University of China, Tianjin 300300, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hui","family":"Ma","sequence":"additional","affiliation":[{"name":"School of Information Engineering, Xuchang University, Xuchang 461000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,2,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New Directions in Cryptography","volume":"IT-22","author":"Diffie","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A Method for Obtaining Digital Signature and Public Key Cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms","volume":"IT-31","author":"ElGamal","year":"1985","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1109\/TIT.1978.1055927","article-title":"Hiding Information and Signatures in Trapdoor Knapsacks","volume":"IT-24","author":"Merkle","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1109\/18.21214","article-title":"A Knapsack-Type Public Key Cryptosystem Based on Arithmetic in Finite Fields","volume":"IT-34","author":"Chor","year":"1988","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s001450010005","article-title":"Cryptanalysis of The Chor\u2013Rivest Cryptosystem","volume":"14","author":"Vaudenay","year":"2001","journal-title":"J. Cryptol."},{"key":"ref_7","first-page":"112","article-title":"A Multiple-Iterated Trapdoor for Dense Compact Knapsacks","volume":"Volume 950","author":"Orton","year":"1995","journal-title":"Advances in Cryptology\u2013Eurocrypt 1994 (LNCS)"},{"key":"ref_8","first-page":"448","article-title":"New Public Key Cryptosystem Using Discrete Logarithm Over GF(p)","volume":"J71-D","author":"Morii","year":"1988","journal-title":"IEICE Trans. Fund."},{"key":"ref_9","first-page":"27","article-title":"A New Public-Key Cryptosystem","volume":"Volume 1233","author":"Naccache","year":"1997","journal-title":"Advances in Cryptology\u2013Eurocrypt 1997 (LNCS)"},{"key":"ref_10","first-page":"282","article-title":"New Trapdoor-Knapsack Public-Key Cryptosystem","volume":"132","author":"Goodman","year":"1985","journal-title":"IEE Proc."},{"key":"ref_11","first-page":"405","article-title":"A New Trapdoor in Knapsacks","volume":"Volume 473","author":"Niemi","year":"1990","journal-title":"Advances in Cryptology\u2013Eurocrypt 1990 (LNCS)"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Janardan, R., and Lakshmanan, K.B. (1983). A Public-Key Cryptosystem based on The Matrix Cover NP-Complete Problem. Advances in Cryptology\u2013Crypto 1982, Plenum.","DOI":"10.1007\/978-1-4757-0602-4_3"},{"key":"ref_13","first-page":"50","article-title":"Weaknesses of A Public Key Cryptosystem based on Factorization of Finite Groups","volume":"Volume 765","author":"Blackburn","year":"1994","journal-title":"Advances in Cryptology\u2013Eurocrypt 1993 (LNCS)"},{"key":"ref_14","first-page":"198","article-title":"Merkle-Hellman Revisited: A cryptanalysis of The Qu-Vanstone Cryptosystem based on Group Factorizations","volume":"Volume 1294","author":"Nguyen","year":"1997","journal-title":"Advances in Cryptology\u2013Crypto 1997 (LNCS)"},{"key":"ref_15","first-page":"73","article-title":"On Public-Key Cryptosystems Built Using Polynomial Rings","volume":"Volume 219","author":"Pieprzyk","year":"1985","journal-title":"Advances in Cryptology\u2013Eurocrypt 1985 (LNCS)"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1109\/12.368013","article-title":"A New Public-Key Cipher System based upon The Diophantine Equations","volume":"44","author":"Lin","year":"1995","journal-title":"IEEE Trans. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1080\/0161-119291866865","article-title":"A Public Key Cryptosystem based on Complementing Sets","volume":"XVI","author":"Webb","year":"1992","journal-title":"Cryptologia"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Brickell, E.F. (1984). Solving Low Density Knapsacks. Advances in Cryptology\u2013Crypto 1983, Plenum.","DOI":"10.1007\/978-1-4684-4730-9_2"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/2455.2461","article-title":"Solving Low-Density Subset Sum Problems","volume":"32","author":"Lagarias","year":"1985","journal-title":"J. ACM"},{"key":"ref_20","first-page":"54","article-title":"An Improved Low-Density Subset Sum Algorithm","volume":"Volume 547","author":"Coster","year":"1991","journal-title":"Advances in Cryptology\u2013Eurocrypt 1991 (LNCS)"},{"key":"ref_21","unstructured":"Brickell, E.F., and Odlyzko, A.M. (1992). Cryptanalysis: A Survey of Recent Results. Contemporary Cryptology, The Science of Information Integrity, IEEE Press."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Lagarias, J.C. (1984). Knapsack Public Key Cryptosystems and Diophantine Approximation. Advances in Cryptology\u2013Crypto 1983, Plenum.","DOI":"10.1007\/978-1-4684-4730-9_1"},{"key":"ref_23","unstructured":"Lai, M.K. (2003, December 20). Knapsack Cryptosystems: The Past and The Future. Available online: http:\/\/www.ics.uci.edu\/~{}mingl\/knapsack.html."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1090\/psapm\/042\/1095552","article-title":"The Rise and Fall of Knapsack Cryptosystems","volume":"42","author":"Odlyzko","year":"1990","journal-title":"Am. Math. Soc. Proc. Symp. Appl. Math"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/BF01457454","article-title":"Factoring Polynomials with Rational Coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref_26","first-page":"1564","article-title":"Density Attack to The Knapsack Cryptosystems with Enumerative Source Encoding","volume":"E84-A","author":"Omura","year":"2001","journal-title":"IEICE Trans. Fund."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/11593447_3","article-title":"Adapting Density Attacks to Low-Weight Knapsacks","volume":"Volume 3788","author":"Nguyen","year":"2005","journal-title":"Advances in Cryptology\u2013Asiacrypt 2005 (LNCS)"},{"key":"ref_28","first-page":"25","article-title":"Diophantine Approximation Attack on A Fast Public Key Cryptosystem","volume":"Volume 3903","author":"Wang","year":"2006","journal-title":"The 2nd Information Security Practice and Experience Conference\u2013ISPEC 2006 (LNCS)"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems","volume":"66","author":"Schnorr","year":"1994","journal-title":"Math. Progr."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Ajtai, M., and Dwork, C. (1997, January 4\u20136). A Public-Key Cryptosystem with Worst-Case\/Average-Case Equivalence. Proceedings of the 29th ACM STOC, El Paso, TX, USA.","DOI":"10.1145\/258533.258604"},{"key":"ref_31","first-page":"112","article-title":"Public-Key Cryptosystems from Lattice Reduction Problems","volume":"Volume 1294","author":"Goldreich","year":"1997","journal-title":"Advances in Cryptology\u2013Crypto 1997 (LNCS)"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BFb0054868","article-title":"NTRU: A New High Speed Public Key Cryptosystem","volume":"Volume 1423","author":"Hoffstein","year":"1998","journal-title":"Proceedings of the Algorithm Number Theory\u2013ANTS III (LNCS)"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1006\/inco.1998.2762","article-title":"A lattice-based Public-Key Cryptosystem","volume":"151","author":"Cai","year":"1999","journal-title":"Inf. Comput."},{"key":"ref_34","first-page":"570","article-title":"A Progress Report on Lattice-based Public-Key Cryptosystems\u2014Theoretical Security Versus Practical Cryptanalysis","volume":"E83-D","author":"Sakurai","year":"2000","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/3-540-44670-2_12","article-title":"The Two Faces of Lattices in Cryptology","volume":"Volume 2146","author":"Nguyen","year":"2001","journal-title":"Proceedings of the Cryptography and Lattices\u2013CaLC (LNCS)"},{"key":"ref_36","unstructured":"Shamir, A. (May, January 30). On The Cryptocomplexity of Knapsack Systems. Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, Atlanta, GA, USA."},{"key":"ref_37","first-page":"2482","article-title":"A New Product-Sum Public-Key Cryptosystem Using Message Extension","volume":"E84-A","author":"Katayangi","year":"2001","journal-title":"IEICE Trans. Fund."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/3-540-44598-6_9","article-title":"Quantum Public-Key Cryptosystems","volume":"Volume 1880","author":"Okamoto","year":"2000","journal-title":"Advances in Cryptology\u2013Crypto 2000 (LNCS)"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1049\/ip-com:20045278","article-title":"Public Key Cryptosystem based on Two Cryptographic Assumptions","volume":"152","author":"Wang","year":"2005","journal-title":"IEE Proc. Commun."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1109\/TIT.1980.1056197","article-title":"On The Security of The Merkle-Hellman Cryptographic Scheme","volume":"26","author":"Shamir","year":"1980","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1109\/12.588074","article-title":"Cryptanalysis of A Diophantine Equation Oriented Public Key Cryptosystem","volume":"46","author":"Laih","year":"1997","journal-title":"IEEE Trans. Comput."},{"key":"ref_42","first-page":"316","article-title":"Trapdoors in Knapsack Cryptosystems","volume":"Volume 149","author":"Eier","year":"1982","journal-title":"Cryptography\u2013EUROCRYPT 1982 (LNCS)"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"3981","DOI":"10.1016\/j.ins.2007.03.010","article-title":"A Knapsack-based Probabilistic Encryption Scheme","volume":"177","author":"Wang","year":"2007","journal-title":"Inf. Sci."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Koblitz, N. (1998). Algebraic Aspects of Cryptography, Springer-Verlag.","DOI":"10.1007\/978-3-662-03642-6"},{"key":"ref_45","unstructured":"Wolf, C. (2005). Multivariate Quadratic Polynomials in Public Key Cryptography. [Ph.D. Thesis, Katholieke Universiteit Leuven]. Available online: http:\/\/eprint.iacr.org\/2005\/393."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00145-005-0432-z","article-title":"Another Look at \u201cProvable Security\u201d","volume":"20","author":"Koblitz","year":"2007","journal-title":"J. Cryptol."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1016\/S0304-3975(99)00297-2","article-title":"Non-Injective Knapsack Public-Key Cryptosystems","volume":"255","author":"Koskinen","year":"2001","journal-title":"Theor. Comput. Sci."},{"key":"ref_48","unstructured":"Han, S., Chang, E., and Dillon, T. (2006, August 22). Knapsack Diffie-Hellman: A New Family of Diffie-Hellman. Available online: http:\/\/eprint.iacr.org\/2005\/347."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.amc.2004.08.027","article-title":"A Knapsack Public-Key Cryptosystem based on Elliptic Curve Discrete Logarithm","volume":"168","author":"Su","year":"2005","journal-title":"Appl. Math. Comput."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/10\/2\/75\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:33:57Z","timestamp":1760186037000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/10\/2\/75"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,21]]},"references-count":49,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,2]]}},"alternative-id":["info10020075"],"URL":"https:\/\/doi.org\/10.3390\/info10020075","relation":{},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,21]]}}}