Cryptanalysis of a Knapsack Based Two-Lock Cryptosystem

摘要

In this paper we break a knapsack based two-lock cryp-tosystem proposed at ICICS'03 , The two-lock cryptosystem is a commutative encryption algorithm that is very useful for the construction of the general t-out-of-n oblivious transfers and millionaire protocol. However, our analysis shows that the proposed knapsack based two-lock cryptosystem is extremely insecure. The serious flaw is that the sender in the two-lock cryptosystem can retrieve the secret key of the receiver fairly easily. We have implemented the attack on a Pentium 4 2.5 GHz processor. For the parameters given in [7], it takes only several minutes to break that knapsack based two-lock cryptosystem.