BACKGROUND:  Non-interactive zero-knowledge (NIZK) proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. Lack of efficiency has prevented these proofs from practical implementation in the past. However, the innovation disclosed here includes a general methodology for constructing very simple and efficient witness-indistinguishable proofs (which also can be reduced to NIZK proofs) that work directly for groups with a bilinear map, such as those in widely used ECC schemes. Such proofs form the foundation for verification schemes based on the underlying algebraic properties of these groups. Examples include simple signature schemes, but also second generation technologies based on limited information revelation. Practical implementations follow in a straightforward manner for ECC systems and other systems constructed with groups with a bilinear map.

INNOVATION:  The invention discloses a new non-interactive witness-indistinguishable proof that works directly for groups with a bilinear map.

POTENTIAL APPLICATIONS 

• Digital signatures, privacy-preserving and e-voting protocols, and other cryptographic protocols

ADVANTAGES

• Reduced computational complexity compared to other cryptographic proofs
• Better security compared to other proofs
• Works directly for groups with a bilinear map, which are common to many cryptographic protocols (such as ECC)
• Works without needing a reduction to Circuit SAT

DEVELOPMENT-TO-DATE:  The invention has been mathematically proven. Implementation is straightforward for those skills in cryptographic systems.

Reference: UCLA Case No. 2007-252