Zero Knowledge Proofs

Overview

This study explores the feasibility and effectiveness of Zero Knowledge Proofs of Identity in an ad hoc wireless environment. We take a largely adaptive approach to the development of a node identity paradigm. As such, a great deal of effort has been dedicated to the research and critical analysis of existing zero knowledge algorithms. The desired outcome of this study is a prototypical implementation of an authentication subsystem for M2MI. Subsequent work will be dedicated to the testing, tailoring, and rigorous analysis of this implementation.

What are Zero Knowledge Proofs?

Zero Knowledge Proofs allow one party to prove its knowledge of a secret to another party without ever revealing the secret itself. For example, consider a scenario where A wishes to prove to B that she knows the root password to a very secure machine X. A doesn't want to tell B what the password is, so she asks B to login in machine X as himself. A then logs into X as root. B asks A to create a file named proof in his home directory. A creates proof in B's home directory. B checks to see that proof has been created in his directory with the user id root. If it has, B is convinced that A knows the root password because no one else could create a file in her directory with the username root. Nonetheless, B still does not know the root password.

In practice, ZKPs are much more complicated. The general protocol works as follows: There is a prover who knows the secret and a verfier who wishes to know if the prover knows the secret. In the above example, A is the prover and B is the verifier. The prover proposes a "hard" problem to the verifier. The verifier asks one or more questions about the problem until she or he is convinced that the prover really knows the answer to the problem. Classic examples of the "hard" problem include factoring the product of large primes, graph isomorphism, and discrete logarithms. Problems that are well-suited for ZKPs are typically NP-complete.

The number and format of challenge/response sequences used is protocol dependent. In our simple example, the format of the challenge was a sentence, the response was a UNIX file, and one round sufficiently proved that A knew the root password. The rounds are typically a bit more complicated, though: the challenge may be a specific bit position, the response the value of that bit; or the challenge may be a graph edge, the response the color of that edge. In any case, the verifier must challenge the prover until he or she is satisfied that the prover truly knows the solution to the problem.

One very important characteristic of zero knowledge proofs is that the verifier learns nothing from the prover except that he or she knows the secret. That is, the verifier should not be able to convince anyone that it knows the prover's secret.

Lastly, it is important that different instances of the "hard" problem are used each time the ZKP is performed. (In some algorithms, a new instance is selected in every round.) This is necessary so that an eavesdropper cannot use the transcript between the prover and verifier to later prove to someone else that he knows the secret.

Why are we studying them?

In theory, Zero Knowledge Proofs (ZKPs) provide an elegant solution to one of the most challenging aspects of security in ad hoc wireless networks--node identification. In addition, ZKPs typically require significantly less computing power than traditional identification paradigms, which makes them especially appealing for small wireless devices. Unfortunately, little work has been done to implement ZKP algorithms and validate their completeness and soundness on a practical level.

Schedule and Milestones

Milestone	Weeks	Description
1	1-5	Read and discuss the most prominent and relevant papers in the Zero Knowledge arena. Each paper will be assessed based on its completeness, soundness, efficiency (i.e., the amount of bandwidth and computational resources required), and complexity. Following a survey of the most prominent papers and authors in the field, we will refine our focus to algorithms that have been designed and/or adapted to small devices.
2	6-9	These weeks are reserved for the implementation and testing of one or more of the algorithms discussed in the papers. The implementation will be integrated into the M2MI architecture. Tests will measure resource consumption, bandwidth, and robustness.
3	10-11	Compile and assess our findings in a formal paper, which will be submitted to conferences that express an interest in wireless security. Before submission, the paper will be presented and reviewed within RIT.

Deliverables

Final Report: PS

Reading List

This is a list of the papers we are currently researching. We will update it as our work continues and focus is refined.

ARONSSON00:

Hannu A. Aronsson. Zero knowledge protocols and small systems. Technical report, Helsinki University of Technology, http://www.tml.hut.fi/Opinnot/Tik-110.501/1995/zeroknowledge.html, 2000. \\Aptly titled, Aronsson's article provides cursory coverage of zero knowledge protocols, including the dominating paradigms of our time, then discusses how they apply to small systems.

BOYAR90:

Joan Boyar, Katalin Friedl, and Carsten Lund. Practical zero-knowledge proofs: Giving hints and using deficiencies. Lecture Notes in Computer Science, 434:155-, 1990. \\This article provides practical insights into dominant zero knowledge paradigms.

CRAMER98:

Ronald Cramer and Victor Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. Lecture Notes in Computer Science, 1462:13-, 1998.

DANA02:

Frank Dana. Elliptic curve cryptosystems for palmos. Master's thesis, Rochester Institute of Technology, 2002. \\A potentially useful, homegrown thesis. More important than the actual implementation are the author's findings. \emph{Also note: this project is not yet complete!}

DESMEDT99:

Desmedt and Kurosawa. Practical and proven zero-knowledge constant round variants of GQ and schnorr. TIEICE: IEICE Transactions on Communications/Electronics/Information and Systems, 1999.

FEIGE87:

Uriel Feige, Amos Fiat, and Adi Shamir. Zero knowledge proofs of identity. In Proceedings of the 19th ACM Symp. on Theory of Computing, pages 210-217, May 1987. \\Many of the contemporary zero knowledge systems in existence today are based on the work of Feige, et al, as described in this article.

GOLDREICH97:

Oded Goldreich. On the foundations of modern cryptography. Lecture Notes in Computer Science, 1294:46-74, 1997. \\Although this mini-text only provides brief coverage of zero knowledge proofs, its insights and clarifications regarding misconceptions in modern cryptography are quite useful.

KELSEY97:

John Kelsey, Bruce Schneier, and David Wagner. Protocol interactions and the chosen protocol attack. In Security Protocols Workshop, pages 91-104, 1997. \\Should a hybrid protocol be chosen, it is likely that this paper will prove valuable, as it exposes many problems that occur when two independently strong protocols are combined.

LIN00:

Hung-Yu Lin, Lein Harn, and Vijay Kumar. Authentication protocols in wireless communications.

MENEZES93:

Alfred J. Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publishers, 1993. \\Regarded as a fundamental text for elliptic curve cryptosystems.

MENEZES93-2:

Alfred J. Menezes. Elliptic curve cryptosystems and their implementation. Journal of Cryptology, pages 209-224, 1993. \\A practical analysis of elliptic curve implementation.

MENEZES96:

Scott A. Vanstone Alfred J. Menezes, Paul C. van Oorschot. Handbook of Applied Cryptography. CRC Press, 1996. \\A core cryptography text, with detailed coverage of elliptical curves and zero knowledge.

PIETILAINEN00:

Henna Pietilainen. Elliptic curve cryptography on smart cards. Master's thesis, Helsinki University of Technology, 2000. \\Although not directly applicable, the limited resources of smart cards are comparable to those of small wireless devices; so the findings listed here may be insightful into our work.

STINSON95:

Douglas R. Stinson. Crytpography: Theory and Practice. CRC Press, 1995. \\Arguably \emph{the} textbook on cryptography. This edition was chosen over its successor because it contains more in-depth coverage of elliptical curves and zero knowledge proofs-roughly one chapter for each.

YEE02:

Bennet Yee. bsy's explanation of zero knowledge proofs. Technical report, University of California, San Diego, http://www-cse.ucsd.edu/users/bsy/, 2002. \\A brief but helpful overview of zero knowledge proofs.

Contacts

If you would like more information on this study, please contact Joe Binder (jsb7384@cs.rit.edu) or Hans-Peter Bischof (hpb@cs.rit.edu).

The Anhinga Project Department of Computer Science Rochester Institute of Technology

Home Page

Copyright © 2002 Rochester Institute of Technology. All rights reserved. Last updated 08-Jul-2002. Please send comments to anhinga@cs.rit.edu.