| Título: |
3-round weak zero-knowledge proofs for [Nu] [Rho] Three-round weak ZK proofs for [Nu] [Rho] |
| Autores: | Lim, Dah-Yoh, 1978- |
| Fecha: |
2005-09-27 2005-09-27 2004 2004 |
| Publicador: | MIT |
| Fuente: |
 |
| Tipo: | Thesis |
| Tema: | Electrical Engineering and Computer Science. |
| Descripción: |
(cont.) to the verifier. We consider an implementation of a weakened notion of zero-knowledge (weak ZK) where the simulator is also allowed to depend on the distinguisher as well, so this type of ZK entails exhibiting an efficient simulator for every efficient (Verifier, Distinguisher) pair. This notion is interesting because in many applications of ZK protocols, weak ZK is actually enough. In addition, Goldreich and Krawczyk's proof (SICOMP 1996) of the non-existence 1 of 3-round black-box ZK protocols carries over to weak ZK directly, so we know that 3-round black-box weak ZK protocols do not exist. In this thesis we are concerned with 3-round proofs for hP: under the standard computational Diffie-Hellman assumption, we construct a 3-round weak ZK proof for NP [nu rho] with inverse-polynomial soundness error. To the best of our knowledge, there have been two constructive results, of Hada and Tanaka (Crypto 1998) and Lepinski (MIT Master's thesis 2001) respectively, stating that assuming some non-standard assumptions, 3-round (traditional) ZK protocols (arguments or proofs respectively) for NP [nu rho] with negligible soundness error do exist. We use the idea of intertwining Oblivious Transfer with a ZK protocol given by Lepinski to prove our result. For every verifier and distinguisher, we construct a different simulator. The technique of simulation is novel and we believe it will have future uses. For instance, our protocol is actually WI with negligible soundness error, by virtue of Feige and Shamir's result (STOC 1990) that WI protocols do compose in parallel. Furthermore, since the first two rounds of our protocol are actually independent of the theorem to be proven, we can think of these two rounds as an interactive setup phase after which the prover can non-interactively prove by Dah-Yoh Lim. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004. In title on t.p., "[Nu]" and "[Rho]" appear as upper-case Greek letters. Includes bibliographical references (p. 57-61). |
| Idioma: | Inglés |
1 Problem Investigation in High-Hazard Industries: Creating and Negotiational Learning por Hatakenaka, Sachi,Rudolph, Jenny,Carroll, John S. | 6 Trade Linkages and Output-Multiplier Effects: A Structural VAR por Forbes, Kristin J.,Abeysinghe, Tilak |
2 Global sourcing in the automotive supply chain:The case of Fiat Auto por Volpato, Giuseppe,Camuffo, Arnaldo | 7 Description Of Procedures In Automotive Engine Plants por Artzner, Denis,Whitney, Dr. Daniel |
3 Reading Courtesy Amounts on Handwritten Paper Checks por Palacios, Rafael,Wang, Patrick S.P.,Gupta, Amar | 8 Mobility Issues in the Developing World por Gakenheimer, Ralph |
4 On Trees and Logs por Pavlova, Anna,Cass, David | 9 Saturn, The GM/UAW Partnership por Rubinstein, Saul,Kochan, Thomas |
5 Academic Earmarks and the Returns to Lobbying por De Figueiredo, John M.,Silverman, Brian S. | 10 Toward a Stakeholder Theory of the Firm: The Case of the Saturn Partnership por Kochan, Thomas,Rubinstein, Saul |