Generalizing cryptosystems based on the subset sum problem

被引：25

作者：

Kate, Aniket ^{[2
]}

Goldberg, Ian ^{[1
]}

机构：

[1] Univ Waterloo, Cheriton Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

[2] Max Planck Inst Software Syst MPI SWS, D-66111 Saarbrucken, Germany

来源：

INTERNATIONAL JOURNAL OF INFORMATION SECURITY | 2011年 / 10卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Public-key cryptography; Subset-sum problem; Damgard-Jurik; RFID security and privacy; Okamoto-Tanaka-Uchiyama; DENSITY ATTACK;

D O I：

10.1007/s10207-011-0129-2

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

080201 [机械制造及其自动化];

摘要：

We identify a generic construction of cryptosystems based on the subset sum problem and characterize the required homomorphic map. Using the homomorphism from the DamgAyenrd-Jurik cryptosystem, we then eliminate the need for a discrete logarithm oracle in the key generation step of the Okamoto et al. scheme to provide a practical cryptosystem based on the subset sum problem. We also analyze the security of our cryptosystem and show that with proper parameter choices, it is computationally secure against lattice-based attacks. Finally, we present a practical application of this system for RFID security and privacy.

引用

页码：189 / 199

页数：11

共 33 条

[1]

[Anonymous], 1955, C THEOR NOMBR BRUX

[2]

[Anonymous], LNCS

[3]

Avoine G., 2008, Security and Privacy in RFID Systems

[4]

Bose Raj C, 1962, Comment. Math. Helv, V37, P141, DOI DOI 10.1007/BF02566968

[5]

Brickell E.F., 1983, CRYPTO, P25

[6]

A KNAPSACK-TYPE PUBLIC KEY CRYPTOSYSTEM BASED ON ARITHMETIC IN FINITE-FIELDS [J].

CHOR, B ;

RIVEST, RL .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1988, 34 (05) :901-909

[7]

CHOR B, 1985, ADV CRYPTOLOGY, P54

[8]

COSTER MJ, 1991, LECT NOTES COMPUT SC, V547, P54

[9]

COVER TM, 1973, IEEE T INFORM THEORY, V19, P73, DOI 10.1109/TIT.1973.1054929

[10]

Lightweight asymmetric privacy-preserving authentication protocols secure against active attack [J].

Cui, Yang ;

Kobara, Kazukuni ;

Matsuura, Kanta ;

Imai, Hideki .

FIFTH ANNUAL IEEE INTERNATIONAL CONFERENCE ON PERVASIVE COMPUTING AND COMMUNICATIONS WORKSHOPS, PROCEEDINGS, 2007, :223-+

← 1 2 3 4 →