New Conditions for Secure Knapsack Schemes against Lattice Attack

Noboru KUNIHIRO

doi:10.1587/transfun.E93.A.1058

New Conditions for Secure Knapsack Schemes against Lattice Attack

Noboru KUNIHIRO

Full Text Views

0

Cite this

Summary :

Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of their low density. To prevent the lattice attack, Chor and Rivest proposed a low weight knapsack scheme, which made the density higher than critical density. In Asiacrypt2005, Nguyen and Stern introduced pseudo-density and proved that if the pseudo-density is low enough (even if the usual density is not low enough), the knapsack scheme can be broken by a single call to SVP/CVP oracle. However, the usual density and the pseudo-density are not sufficient to measure the resistance to the lattice attack individually. In this paper, we first introduce the new notion of density D, which naturally unifies the previous two density. Next, we derive conditions for our density so that a knapsack scheme is secure against lattice attack. We obtain a critical bound of density which depends only on the rate of the message length and its Hamming weight. Furthermore, we show that if D<0.8677, the knapsack scheme is solved by lattice attack. Next, we show that the critical bound goes to 1 if the Hamming weight decreases, which means that it is (almost) impossible to construct a low weight knapsack scheme which is supported by an argument of density.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.6 pp.1058-1065

Publication Date: 2010/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E93.A.1058

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category: Cryptography and Information Security

Cite this

Copy

Noboru KUNIHIRO, "New Conditions for Secure Knapsack Schemes against Lattice Attack" in IEICE TRANSACTIONS on Fundamentals, vol. E93-A, no. 6, pp. 1058-1065, June 2010, doi: 10.1587/transfun.E93.A.1058.
Abstract: Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of their low density. To prevent the lattice attack, Chor and Rivest proposed a low weight knapsack scheme, which made the density higher than critical density. In Asiacrypt2005, Nguyen and Stern introduced pseudo-density and proved that if the pseudo-density is low enough (even if the usual density is not low enough), the knapsack scheme can be broken by a single call to SVP/CVP oracle. However, the usual density and the pseudo-density are not sufficient to measure the resistance to the lattice attack individually. In this paper, we first introduce the new notion of density D, which naturally unifies the previous two density. Next, we derive conditions for our density so that a knapsack scheme is secure against lattice attack. We obtain a critical bound of density which depends only on the rate of the message length and its Hamming weight. Furthermore, we show that if D<0.8677, the knapsack scheme is solved by lattice attack. Next, we show that the critical bound goes to 1 if the Hamming weight decreases, which means that it is (almost) impossible to construct a low weight knapsack scheme which is supported by an argument of density.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.1058/_p

Copy

@ARTICLE{e93-a_6_1058,
author={Noboru KUNIHIRO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={New Conditions for Secure Knapsack Schemes against Lattice Attack},
year={2010},
volume={E93-A},
number={6},
pages={1058-1065},
abstract={Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of their low density. To prevent the lattice attack, Chor and Rivest proposed a low weight knapsack scheme, which made the density higher than critical density. In Asiacrypt2005, Nguyen and Stern introduced pseudo-density and proved that if the pseudo-density is low enough (even if the usual density is not low enough), the knapsack scheme can be broken by a single call to SVP/CVP oracle. However, the usual density and the pseudo-density are not sufficient to measure the resistance to the lattice attack individually. In this paper, we first introduce the new notion of density D, which naturally unifies the previous two density. Next, we derive conditions for our density so that a knapsack scheme is secure against lattice attack. We obtain a critical bound of density which depends only on the rate of the message length and its Hamming weight. Furthermore, we show that if D<0.8677, the knapsack scheme is solved by lattice attack. Next, we show that the critical bound goes to 1 if the Hamming weight decreases, which means that it is (almost) impossible to construct a low weight knapsack scheme which is supported by an argument of density.},
keywords={},
doi={10.1587/transfun.E93.A.1058},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - New Conditions for Secure Knapsack Schemes against Lattice Attack
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1058
EP - 1065
AU - Noboru KUNIHIRO
PY - 2010
DO - 10.1587/transfun.E93.A.1058
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2010
AB - Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of their low density. To prevent the lattice attack, Chor and Rivest proposed a low weight knapsack scheme, which made the density higher than critical density. In Asiacrypt2005, Nguyen and Stern introduced pseudo-density and proved that if the pseudo-density is low enough (even if the usual density is not low enough), the knapsack scheme can be broken by a single call to SVP/CVP oracle. However, the usual density and the pseudo-density are not sufficient to measure the resistance to the lattice attack individually. In this paper, we first introduce the new notion of density D, which naturally unifies the previous two density. Next, we derive conditions for our density so that a knapsack scheme is secure against lattice attack. We obtain a critical bound of density which depends only on the rate of the message length and its Hamming weight. Furthermore, we show that if D<0.8677, the knapsack scheme is solved by lattice attack. Next, we show that the critical bound goes to 1 if the Hamming weight decreases, which means that it is (almost) impossible to construct a low weight knapsack scheme which is supported by an argument of density.
ER -