Decryption method for differential knapsack PKC

摘要

Murakami and Kasahara proposed the differential knapsack scheme at SCIS2011 and ICCIT2011. The decryption of this scheme requires to solve the small subset sum problem. The space-time tradeoff method(STT) can be applied to solve the subset sum problem(SSP). We presented an implementation of STT for SSP at ICCIT2011. We presented the decryption method with STT for differential knapsack scheme at SCIS2012. In this paper, we present a method for implementing the decryption process with STT method for differential knapsack scheme. Moreover, we point out a problem of the multiple solutions when performing decryption in this scheme and deliberate upon such multiple solutions.