Empirical exploration of lattice attacks for building secure knapsack cryptosystems

Shang Ming Jen, Chia Yu Lu, Tse Lin Lai, Jar-Ferr Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Pending the possible realization of quantum computers, the RSA algorithm face critical challenges because of weaknesses under quantum cryptanalysis. A possible replacement may be knapsack cryptosystems, which do not yield any weaknesses to quantum computation. At present, the most significant challenge against knapsack cryptosystems is lattice attack, and public key density has historically been used to measure the security of knapsack cryptosystems against it. In this paper, we demonstrate the compromise of an acceptably dense knapsack cryptosystem using lattice attack. In order to quantify the security of knapsack cryptosystems under lattice attacks, we design experiments to analyze possible affecting factors. We demonstrate that it is not appropriate to assess the security of a knapsack cryptosystem by only considering density. Instead, there exist some other factors in literature which have more significance than density. Building on these results, we develop an empirically secure knapsack cryptosystem which explores possible directions for improving knapsack cryptosystems.

Original languageEnglish
Title of host publication2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012
DOIs
Publication statusPublished - 2012 Dec 11
Event2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012 - Taipei, Taiwan
Duration: 2012 Aug 242012 Aug 26

Publication series

NameProceedings of the International Conference on Anti-Counterfeiting, Security and Identification, ASID
ISSN (Print)2163-5048
ISSN (Electronic)2163-5056

Other

Other2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012
CountryTaiwan
CityTaipei
Period12-08-2412-08-26

Fingerprint

Cryptography
Quantum computers
Experiments

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design
  • Computer Science Applications
  • Computer Vision and Pattern Recognition
  • Software

Cite this

Jen, S. M., Lu, C. Y., Lai, T. L., & Yang, J-F. (2012). Empirical exploration of lattice attacks for building secure knapsack cryptosystems. In 2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012 [6325281] (Proceedings of the International Conference on Anti-Counterfeiting, Security and Identification, ASID). https://doi.org/10.1109/ICASID.2012.6325281
Jen, Shang Ming ; Lu, Chia Yu ; Lai, Tse Lin ; Yang, Jar-Ferr. / Empirical exploration of lattice attacks for building secure knapsack cryptosystems. 2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012. 2012. (Proceedings of the International Conference on Anti-Counterfeiting, Security and Identification, ASID).
@inproceedings{06ce21bdc1404655b269f3e3b259b6e0,
title = "Empirical exploration of lattice attacks for building secure knapsack cryptosystems",
abstract = "Pending the possible realization of quantum computers, the RSA algorithm face critical challenges because of weaknesses under quantum cryptanalysis. A possible replacement may be knapsack cryptosystems, which do not yield any weaknesses to quantum computation. At present, the most significant challenge against knapsack cryptosystems is lattice attack, and public key density has historically been used to measure the security of knapsack cryptosystems against it. In this paper, we demonstrate the compromise of an acceptably dense knapsack cryptosystem using lattice attack. In order to quantify the security of knapsack cryptosystems under lattice attacks, we design experiments to analyze possible affecting factors. We demonstrate that it is not appropriate to assess the security of a knapsack cryptosystem by only considering density. Instead, there exist some other factors in literature which have more significance than density. Building on these results, we develop an empirically secure knapsack cryptosystem which explores possible directions for improving knapsack cryptosystems.",
author = "Jen, {Shang Ming} and Lu, {Chia Yu} and Lai, {Tse Lin} and Jar-Ferr Yang",
year = "2012",
month = "12",
day = "11",
doi = "10.1109/ICASID.2012.6325281",
language = "English",
isbn = "9781467321440",
series = "Proceedings of the International Conference on Anti-Counterfeiting, Security and Identification, ASID",
booktitle = "2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012",

}

Jen, SM, Lu, CY, Lai, TL & Yang, J-F 2012, Empirical exploration of lattice attacks for building secure knapsack cryptosystems. in 2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012., 6325281, Proceedings of the International Conference on Anti-Counterfeiting, Security and Identification, ASID, 2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012, Taipei, Taiwan, 12-08-24. https://doi.org/10.1109/ICASID.2012.6325281

Empirical exploration of lattice attacks for building secure knapsack cryptosystems. / Jen, Shang Ming; Lu, Chia Yu; Lai, Tse Lin; Yang, Jar-Ferr.

2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012. 2012. 6325281 (Proceedings of the International Conference on Anti-Counterfeiting, Security and Identification, ASID).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Empirical exploration of lattice attacks for building secure knapsack cryptosystems

AU - Jen, Shang Ming

AU - Lu, Chia Yu

AU - Lai, Tse Lin

AU - Yang, Jar-Ferr

PY - 2012/12/11

Y1 - 2012/12/11

N2 - Pending the possible realization of quantum computers, the RSA algorithm face critical challenges because of weaknesses under quantum cryptanalysis. A possible replacement may be knapsack cryptosystems, which do not yield any weaknesses to quantum computation. At present, the most significant challenge against knapsack cryptosystems is lattice attack, and public key density has historically been used to measure the security of knapsack cryptosystems against it. In this paper, we demonstrate the compromise of an acceptably dense knapsack cryptosystem using lattice attack. In order to quantify the security of knapsack cryptosystems under lattice attacks, we design experiments to analyze possible affecting factors. We demonstrate that it is not appropriate to assess the security of a knapsack cryptosystem by only considering density. Instead, there exist some other factors in literature which have more significance than density. Building on these results, we develop an empirically secure knapsack cryptosystem which explores possible directions for improving knapsack cryptosystems.

AB - Pending the possible realization of quantum computers, the RSA algorithm face critical challenges because of weaknesses under quantum cryptanalysis. A possible replacement may be knapsack cryptosystems, which do not yield any weaknesses to quantum computation. At present, the most significant challenge against knapsack cryptosystems is lattice attack, and public key density has historically been used to measure the security of knapsack cryptosystems against it. In this paper, we demonstrate the compromise of an acceptably dense knapsack cryptosystem using lattice attack. In order to quantify the security of knapsack cryptosystems under lattice attacks, we design experiments to analyze possible affecting factors. We demonstrate that it is not appropriate to assess the security of a knapsack cryptosystem by only considering density. Instead, there exist some other factors in literature which have more significance than density. Building on these results, we develop an empirically secure knapsack cryptosystem which explores possible directions for improving knapsack cryptosystems.

UR - http://www.scopus.com/inward/record.url?scp=84870618817&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84870618817&partnerID=8YFLogxK

U2 - 10.1109/ICASID.2012.6325281

DO - 10.1109/ICASID.2012.6325281

M3 - Conference contribution

SN - 9781467321440

T3 - Proceedings of the International Conference on Anti-Counterfeiting, Security and Identification, ASID

BT - 2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012

ER -

Jen SM, Lu CY, Lai TL, Yang J-F. Empirical exploration of lattice attacks for building secure knapsack cryptosystems. In 2012 International Conference on Anti-Counterfeiting, Security and Identification, ASID 2012. 2012. 6325281. (Proceedings of the International Conference on Anti-Counterfeiting, Security and Identification, ASID). https://doi.org/10.1109/ICASID.2012.6325281