Non-Interactive Zero Knowledge

Abstract

We investigate the possibility of disposing of interaction between Prover and Verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, we prove that non-interactive zero- knowledge proofs exist for some number theoretic languages for which no efficient algorithm is known. If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, we show that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1990
Accession Number
ADA222698

Entities

People

  • Alfredo De Santis
  • Giuseppe Persiano
  • Manuel Blum
  • Silvio Micali

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Classification
  • Composite Materials
  • Computations
  • Computer Science
  • Cryptography
  • Information Processing
  • Language
  • New York
  • Notation
  • Number Theory
  • Numbers
  • Probability
  • Random Variables
  • Simulators
  • Square Roots

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Mathematical Modeling and Probability Theory.
  • Theoretical Analysis.