The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Banyak sistem kripto ransel telah dicadangkan tetapi hampir semua skim terdedah kepada serangan kekisi kerana ketumpatannya yang rendah. Untuk mengelakkan serangan kekisi, Chor dan Rivest mencadangkan skim ransel berat rendah, yang menjadikan ketumpatan lebih tinggi daripada ketumpatan kritikal. Dalam Asiacrypt2005, Nguyen dan Stern memperkenalkan pseudo-density dan membuktikan bahawa jika pseudo-density cukup rendah (walaupun jika ketumpatan biasa tidak cukup rendah), skema knapsack boleh dipecahkan dengan satu panggilan ke SVP/CVP oracle. Walau bagaimanapun, ketumpatan biasa dan ketumpatan pseudo tidak mencukupi untuk mengukur rintangan kepada serangan kekisi secara individu. Dalam makalah ini, kami mula-mula memperkenalkan tanggapan baru ketumpatan D, yang secara semula jadi menyatukan dua ketumpatan sebelumnya. Seterusnya, kami memperoleh syarat untuk ketumpatan kami supaya skema ransel selamat daripada serangan kekisi. Kami memperoleh batas ketumpatan kritikal yang bergantung hanya pada kadar panjang mesej dan berat Hammingnya. Tambahan pula, kami menunjukkan bahawa jika D<0.8677, skema ransel diselesaikan dengan serangan kekisi. Seterusnya, kami menunjukkan bahawa sempadan kritikal pergi ke 1 jika berat Hamming berkurangan, yang bermaksud bahawa adalah (hampir) mustahil untuk membina skema beg beg berat rendah yang disokong oleh hujah ketumpatan.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
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
Salinan
@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},}
Salinan
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 -