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

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Empirical exploration of lattice attacks for building secure knapsack cryptosystems'. Together they form a unique fingerprint.

Cite this