Uses of randomness in algorithms and protocols

摘要: "Uses of Randomness in Algorithms and Protocols" makes fundamental contributions to two different fields complexity theory: computational number theory cryptography. The most famous result is Goldwasser Kilian's invention a new approach distinguish prime numbers from composites, using methods the elliptic curves over finite fields.The Goldwasser-Kilian algorithm first yield polynomial size proof its assertions, ensuring correctness while still provably running fast on inputs. This primality test implies for time without any assumptions that large certified primes can be generated expected under distribution close uniform. It provides provocative link between algebraic geometry testing, one ancient algorithmic problems theory. Heuristic implementations are currently considered fastest existing certify primes.Kilian also elegant original theoretical He shows how base general two-party protocols simple protocol, known as "oblivious transfer," proving completeness this kind. introduces generalization interactive systems, "multi-prover systems," anything provable model zero knowledge.Joe Kilian National Science Foundation Postdoctoral Fellow at MIT Harvard.Contents: Introduction. New Techniques Primality Testing. Committing Bits Using Oblivious Transfer. Circuit Evaluation Transfer: NC1 Base. ObliviousEvaluation Arbitrary Circuits. Interactive Proof Systems with Multiple Provers.