Abstract | ||
---|---|---|
We investigate structural properties of statistical zero knowledge (SZK) both in the interactive and in the non-interactive model. Specifically, we look into the closure properties of SZK languages under monotone logical formula composition. This gives rise to new protocol techniques. We show that interactive SZK for random self reducible languages (RSR) (and for co-RSR) is closed under monotone Boolean operations. Namely, we give SZK proofs for monotone Boolean formulae whose atoms are statements about an SZK language which is RSR (or a complement of RSR). All previously known languages in SZK are in these classes. We then show that if a language L has a non-interactive SZK proof system then honest-verifier interactive SZK proof systems exist for all monotone Boolean formulae whose atoms are statements about the complement of L. We also discuss extensions and generalizations |
Year | DOI | Venue |
---|---|---|
1994 | 10.1109/SFCS.1994.365745 | Santa Fe, NM |
Keywords | Field | DocType |
high performance computing,communication system,admission control,monotone formula closure,numerous application,virtual circuit routing,virtual circuit,theorem proving,computer science,cryptography,boolean operations,protocols,boolean functions | Boolean function,Discrete mathematics,Combinatorics,Generalization,Automated theorem proving,Boolean operations in computer-aided design,Mathematical proof,Zero-knowledge proof,Monotone polygon,Mathematics | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-8186-6580-7 | 102 |
PageRank | References | Authors |
11.27 | 22 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alfredo De Santis | 1 | 4049 | 501.27 |
Giovanni Di Crescenzo | 2 | 194 | 19.28 |
G. Persiano | 3 | 173 | 20.19 |
Moti Yung | 4 | 12080 | 1152.41 |