Information Technology Reference
In-Depth Information
of many different cryptographic protocols. The scheme here proposed constitutes
an elegant model in order to solve the identification problem. So, the distNP-
completeness is here suggested as a useful source of problems that guarantees
the security of zero-knowledge proof in a more real and practical sense than
worst-case NP-completeness.
In general it is not recommended to adopt a cryptographic scheme for actual
use too early. This remains true for the algorithm described here, although a
priori it seems of truly practical value. Experts in cryptanalysis and/or combi-
natorics are invited to search for ecient algorithms to solve the problem behind
the proposed scheme.
When parameter are adequately chosen, the new scheme's communication
complexity and computational costs are affordable. Anyway, we hope that a
forthcoming work will include a concrete comparison with other previous
schemes, the range of parameters that guarantees security and ecient perfor-
mance, and an analysis of minimal assumptions for the implementations. Finally,
such as mentioned before, one of the subjects that are object of work in progress
is the design of possible similar zero-knowledge proofs based on other combi-
natorial average-case NP-complete problems such as the Distributional Graph
Edge Coloring Problem.
References
1. Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive
Proof Systems. SIAM Journal on Computing
18
(1989) 186-208
2. Goldreich, O., Micali, S., Wigderson, A.: How to Solve any Protocol Problem. In:
Proceedings of the 19th STOC. (1987) 218-229
3. Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification
and signature problems. In Odlyzko, A.M., ed.: Advances in Cryptology - Crypto
'86, Berlin, Springer-Verlag (1986) 186-194 Lecture Notes in Computer Science
Volume 263
4. Guillou, L.C., Quisquater, J.J.: A practical zero-knowledge protocol fitted to se-
curity microprocessor minimizing both transmission and memory. In Gunther,
C.G., ed.: Advances in Cryptology - EuroCrypt '88, Berlin, Springer-Verlag (1988)
123-128 Lecture Notes in Computer Science Volume 330
5. Ohta, K., Okamoto, T.: A modification of the Fiat-Shamir scheme. In Goldwasser,
S., ed.: Advances in Cryptology - Crypto '88, Berlin, Springer-Verlag (1989) 232-
243 Lecture Notes in Computer Science Volume 403
6. Ong, H., Schnorr, C.P.: Fast signature generation with a Fiat Shamir - like scheme.
In Damg ard, I.B., ed.: Advances in Cryptology - EuroCrypt '90, Berlin, Springer-
Verlag (1990) 432-440 Lecture Notes in Computer Science Volume 473
7. Schnorr, C.P.: Ecient identification and signatures for smart cards. In Brassard,
G., ed.: Advances in Cryptology - Crypto '89, Berlin, Springer-Verlag (1989) 239-
252 Lecture Notes in Computer Science Volume 435
8. Shamir, A.: An ecient identification scheme based on permuted kernels (extended
abstract). In Brassard, G., ed.: Advances in Cryptology - Crypto '89, Berlin,
Springer-Verlag (1989) 606-609 Lecture Notes in Computer Science Volume 435
