Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
5 Probabilistic Algorithms for Defeating Adversaries
5 Probabilistic Algorithms for Defeating Adversaries
Pages 53-64
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 53... ...
· A is a computing workstation, and B is a file server. If there is no direct hardware connection between A and B
|
From page 54... ...
, even if he deviates from the legitimate behavior of A, should be able to convince B to accept x with more than negligible probability. The more general notion of a multiprover interactive proof system was put forth by Ben-Or et al.
|
From page 55... ...
The second type of scenario concerns private use of sharer} resources. A community of users shares a valuable computing resource, and each member of the community would like to use the resource without revealing his private data.
|
From page 56... ...
The effectiveness of the scheme is based on the assumption that it is computationaIly infeasible to compute square roots module a large composite integer with unknown factorization; this is provably equivalent to the assumption that factoring large integers is difficult. Modulus Generation.
|
From page 57... ...
These identity proofs require only a few modular multiplications and can be implemented on smart cards. 5.2.2 Computing with Encrypted Data In our first ex~ruple of computation with encrypted data, the hard-tocompute function is the discrete logarithm module primes.
|
From page 58... ...
In any case, a discrete logarithm box would be a valuable resource, and many mutually suspicious users would want access to it. Abadi et al.
|
From page 59... ...
In isolation, however, Bj and its other users learn nothing about A's private input x from the random query yj. 5.3 Zero-Knowledge Proof Systems ant} InstanceHiding Schemes In this section, we give a brief, informal summary of the known results on zer~knowledge proof systems and instance-hiding schemes.
|
From page 60... ...
The scheme for the multivariate polynomial is an example of a multi-oracle instance-hiding scheme. The first basic question here is to determine exactly which sets have instance-hiding schemes that leak no information about x to the oracles.
|
From page 61... ...
(1991) formalize this notion and prove the following positive result: Theorem 5.6 Every set recognizable an nondeterministic exponential time has a multiprover interactive proof system that is both instance-hiding and zero-knowledge.
|
From page 62... ...
, Hiding instances in multioracle queries, in Proc. 7th Annual Symposium on Theoretical Aspects of Computer Science, I.ecture Notes in Computer Science no.
|
From page 63... ...
, Algebraic methods for interactive proof systems, in Proc. 31st Annual Symposium on Foundation~s of Computer Science, {EKE Computer Science Press, Los Alamitos, Calif., 2-10.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.