Zero knowledge proofs and secret sharing problems

A topic of major importance in the field of modern cryptography is the design of provably secure cryptographic protocols. These protocols are important for solving problems that arise in communications involving adversaries, such as secret ballot elections. Zero knowledge interactive proofs and secret sharing schemes are both useful in the design of secure protocols.; In this thesis the notion of a zero knowledge interactive proof of possession of information is defined and the intrinsic "power" of such a proof is explored from two different directions. First, two important classes, random self-reducible and strongly random self-reducible problems, are identified. It is shown that every random self-reducible problem has a zero knowledge interactive proof of possession of information, and every strongly random self-reducible problem has a related zero knowledge interactive proof of language nonmembership. New perfect zero knowledge interactive proofs are exhibited for possession of the factorization of an integer, membership in the set of generators of {dollar}{lcub}cal Z{rcub}sbsp{lcub}p{rcub}{lcub}*{rcub}{dollar} (the multiplicative group of integers modulo a prime p), and nonmembership in {dollar}langle aranglesb{lcub}p{rcub}{dollar} (the set of integers generated by {dollar}a{dollar} {dollar}in{dollar} {dollar}{lcub}cal Z{rcub}sbsp{lcub}p{rcub}{lcub}*{rcub}{dollar}). None of the proofs mentioned above relies on any unproven assumptions.; Another direction of exploration is to try to characterize all proofs of possession of information. A canonical form for such proofs is conjectured and partial results, involving a notion of generalized average reducibility between relations, are obtained. The existence and structure of such a canonical form seems to be directly related to the existence of one-way functions, and the "power" of the random bits used by verifiers in such proofs.; The second part of this thesis focuses on two variations of the (n,k)-threshold secret sharing problem, secret sharing with cheaters and verifiable secret sharing. Two communication primitives, a committed broadcast and a special kind of distribution, are defined and shown to be easily implemented in two different settings of interest in cryptography. Solutions to the two secret sharing problems that use only these primitives for communication are presented. The correctness of the solutions depends only on the correctness of the implementations of the primitives.