The knowledge complexity of quadratic residuosity languages

DOI10.1016/0304-3975(94)90237-2zbMath0799.68102OpenAlexW1965163152WikidataQ127991124 ScholiaQ127991124MaRDI QIDQ1334668

Giuseppe Persiano, Alfredo De Santis, Giovanni Di Crescenzo

Publication date: 25 September 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90237-2

zbMATH Keywords

zero-knowledge proofgraph nonisomorphismquadratic residuosityquadratic nonresiduosity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

Efficient Non-interactive Range Proof ⋮ Randomness-efficient non-interactive zero knowledge ⋮ On server trust in private proxy auctions ⋮ Practical proofs of knowledge without relying on theoretical proofs of membership on languages ⋮ On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes ⋮ Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages ⋮ How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge ⋮ How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constant-round perfect zero-knowledge computationally convincing protocols
• Probabilistic encryption
• Does co-NP have short interactive proofs ?
• Minimum disclosure proofs of knowledge
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Practic zero-knowledge proofs: Giving hints and using deficiencies
• How to share a secret
• Noninteractive Zero-Knowledge
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• The knowledge complexity of interactive proof-systems
• The Lattice Point Covering Theorem for Rectangles

This page was built for publication: The knowledge complexity of quadratic residuosity languages