The concept of the Zero-Knowledge Interactive Proof (ZKIP) scheme was first proposed by Goldwasser, Micali and Rackoff in 1985. Since then, many practical ZKIP schemes have been proposed. One common feature among all these schemes is that the security of the schemes is based on factoring or the discrete logarithm. In 1991, Simmons proposed an alternative practical ZKIP scheme whose security is based on the subset sum problem. However, there is a very strong assumption in the scheme; i.e., Simmons’s scheme would be secure under the assumption that an indistinguishable box exists. Unfortunately, nobody, including Simmons, has explained how to implement the indistinguishable box. In this paper, we propose two methods for implementing the indistinguishable box. It is shown that the proposed indistinguishable box is very simple, flexible and secure in the applications of ZKIP schemes.

Keywords: ZKIP protocols, identification, cryptography, digital signature, subset sum problem

Retrieve PDF document (199909_06.pdf : 105,576 bytes)

Received January 20, 1997; accepted October 15, 1997.
Communicated by Jean-Lien C. Wu.
^*An earlier version of this paper was presented at the International Conference on Cryptology and Information Security, which was a joint Conference of the International Computer Symposium (ICS '96)