Date Added: Apr 2012
The first Zero-Knowledge schemes were based on the factorization problem (for example Fischer-Micali-Racko in 1984, or Fiat-Shamir in 1986) or the Graph Isomorphism Problem. However the factorization problem is not expected to be a NP complete problem (since it is in NP and Co NP) and it has sub-exponential algorithms (such as NFS) and even polynomial algorithms on quantum computers (Shor algorithm). Then, it was proved in 1991 by O. Goldreich, S. Micali and A. Widgerson that any problem of NP has a Zero-Knowledge proof. But the general construction (cf) of Zero-Knowledge proofs from any problem of NP is usually not very efficient.