The knowledge complexity of quadratic residuosity languages. (English) Zbl 0799.68102
Summary: Noninteractive perfect zero-knowledge (ZK) proofs are very elusive objects. In fact, since the introduction of the noninteractive model of Blum et al. (1988), the only perfect zero-knowledge proof known was the one for quadratic nonresiduosity of Blum et al. (1991). The situation is no better in the interactive case, where perfect zero- knowledge proofs are known only for a handful of particular languages.
In this work, we show that a large class of languages related to quadratic residuosity admits noninteractive perfect zero-knowledge proofs. More precisely, we give a protocol for the language of thresholds of quadratic residuosity.
Moreover, we develop a new technique for converting a noninteractive zero-knowledge proofs into round-optimal zero-knowledge proofs for an even wider class of languages. The transformation preserves perfect zero knowledge in the sense that, if the noninteractive proof we started with is a perfect zero-knowledge proof, then we obtain a round-optimal perfect zero-knowledge proof. The noninteractive perfect zero-knowledge proofs presented in this work can be transformed into 4-round (which is optimal) interactive perfect zero-knowledge proofs. Until now, the only known 4- round perfect ZK proof systems were the ones for quadratic nonresiduosity [Goldwasser et al., 1989] and for graph nonisomorphism [Goldreich et al., 1986] and no 4-round perfect zero-knowledge proof system was known for the simple case of the language of quadratic residues.
In this work, we show that a large class of languages related to quadratic residuosity admits noninteractive perfect zero-knowledge proofs. More precisely, we give a protocol for the language of thresholds of quadratic residuosity.
Moreover, we develop a new technique for converting a noninteractive zero-knowledge proofs into round-optimal zero-knowledge proofs for an even wider class of languages. The transformation preserves perfect zero knowledge in the sense that, if the noninteractive proof we started with is a perfect zero-knowledge proof, then we obtain a round-optimal perfect zero-knowledge proof. The noninteractive perfect zero-knowledge proofs presented in this work can be transformed into 4-round (which is optimal) interactive perfect zero-knowledge proofs. Until now, the only known 4- round perfect ZK proof systems were the ones for quadratic nonresiduosity [Goldwasser et al., 1989] and for graph nonisomorphism [Goldreich et al., 1986] and no 4-round perfect zero-knowledge proof system was known for the simple case of the language of quadratic residues.
MSC:
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68P25 | Data encryption (aspects in computer science) |
| 68Q45 | Formal languages and automata |
| 94A60 | Cryptography |
Keywords:
zero-knowledge proof; quadratic residuosity; quadratic nonresiduosity; graph nonisomorphismReferences:
| [1] | Angluin, D., Lecture notes on the complexity of some problems in number theory, (Tech. Report, 243 (1982), Yale Univ.) |
| [2] | Angluin, D.; Valiant, L., Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. Comput. System Sci., 18, 2, 155-193 (1979) · Zbl 0437.05040 |
| [3] | Bellare, M.; Micali, S.; Ostrovsky, R., Perfect zero knowledge in constant rounds, Proc. 22th Ann. Symp. on the Theory of Comput., 482-493 (1990) |
| [4] | M. Bellare and M. Yung, Certifying cryptographic tools: The case of trapdoor permutations, in: Proc. of CRYPTO’92; M. Bellare and M. Yung, Certifying cryptographic tools: The case of trapdoor permutations, in: Proc. of CRYPTO’92 · Zbl 0817.94011 |
| [5] | M. Ben-Or, O. Goldreich, S. Goldwasser, J. Hastad, S. Micali and P. Rogaway, Everything provable is provable in zero knowledge, in: S. Goldwasser, ed., Advances in Cryptology - CRYPTO 88; M. Ben-Or, O. Goldreich, S. Goldwasser, J. Hastad, S. Micali and P. Rogaway, Everything provable is provable in zero knowledge, in: S. Goldwasser, ed., Advances in Cryptology - CRYPTO 88 · Zbl 0718.68033 |
| [6] | Blackley, G. R., Safeguarding cryptographic keys, Proc. AFIPS 1979 National Computer Conf., 313-317 (1979) |
| [7] | Blum, M.; De Santis, A.; Micali, S.; Persiano, G., Non-interactive zero-knowledge, SIAM J. Comput., 20, 1084-1118 (1991) · Zbl 0738.68027 |
| [8] | Blum, M.; Feldman, P.; Micali, S., Non-interactive zero-knowledge and applications, Proc. 20th Ann. ACM Symp. on Theory of Comput., 103-112 (1988) |
| [9] | Boppana, R., Amplification of probabilistic boolean formulas, Adv. Comput. Res., 5, 27-45 (1989) |
| [10] | Boppana, R.; Hastad, J.; Zachos, S., Does co-NP has short interactive proofs?, Inform. Process Lett., 25, 127-132 (1987) · Zbl 0653.68037 |
| [11] | Boyar, J.; Friedl, K.; Lund, C., Practical zero-knowledge proofs: giving hints and using deficiencies, J. Cryptology, 4, 185-206 (1991) · Zbl 0755.68044 |
| [12] | Brassard, G.; Chaum, D.; Crépeau, C., Minimum disclosure proofs of knowledge, J. Comput. System Sci., 37, 2, 156-189 (1988), (Preliminary version in FOCS ’86) · Zbl 0656.68109 |
| [13] | Brassard, G.; Crépeau, C.; Yung, M., Perfect zero-knowledge computationally convincing proofs for NP in constant rounds, Theoret. Comput. Sci., 84, 23-52 (1991) · Zbl 0731.68032 |
| [14] | A. De Santis, S. Micali and G. Persiano, Non-interactive zero-knowledge proof-systems, in: Advances in Cryptology - CRYPTO 87; A. De Santis, S. Micali and G. Persiano, Non-interactive zero-knowledge proof-systems, in: Advances in Cryptology - CRYPTO 87 |
| [15] | A. De Santis, G. Persiano and M. Yung, Perfect zero-knowledge proofs for graph isomorphism languages, manuscript.; A. De Santis, G. Persiano and M. Yung, Perfect zero-knowledge proofs for graph isomorphism languages, manuscript. |
| [16] | Erdös, P.; Spencer, J., Probabilistic Methods in Combinatorics (1974), Academic Press: Academic Press New York · Zbl 0308.05001 |
| [17] | Feige, U.; Lapidot, D.; Shamir, A., Multiple noninteractive zero-knowledge proofs based on a single random string, Proc. 22nd Ann. Symp. on the Theory of Comput, 308-317 (1990) |
| [18] | Fortnow, L., The complexity of perfect zero knowledge, Proc. 19th Ann. ACM Symp. on Theory of Comput., 204-209 (1987) |
| [19] | Goldreich, O.; Krawczyk, H., On the composition of zero-knowledge proof systems, Proc. 17th Internat. Coll. on Automata, Languages and Programming, 174-187 (1986) |
| [20] | O. Goldreich and E. Kushilevitz, A perfect zero knowledge proof for a decision problem equivalent to discrete logarithm, in: S. Goldwasser, ed., Advances in Cryptology — CRYPTO 88; O. Goldreich and E. Kushilevitz, A perfect zero knowledge proof for a decision problem equivalent to discrete logarithm, in: S. Goldwasser, ed., Advances in Cryptology — CRYPTO 88 |
| [21] | Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity, or all languages in NP have zero-knowledge proofs, J. ACM, 38, 691-729 (1991) · Zbl 0799.68101 |
| [22] | O. Goldreich, S. Micali and A. Wigderson, How to play any mental game, in: Proc. 19th An. ACM Symp. on Theory of Comput.; O. Goldreich, S. Micali and A. Wigderson, How to play any mental game, in: Proc. 19th An. ACM Symp. on Theory of Comput. |
| [23] | Goldreich, O.; Petrank, E., Quantifying knowledge complexity, Proc. 32th IEEE Symp. on Foundations of Comput. Sci. (1991) |
| [24] | Goldwasser, S.; Micali, S., Probabilistic encryption, J. Comput. System. Sci., 28, 270-299 (1984) · Zbl 0563.94013 |
| [25] | Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof-systems, SIAM J. Comput., 18 (1989) · Zbl 0900.94025 |
| [26] | R. Impagliazzo and M. Yung, Direct minimum knowledge computations in: Advances in Cryptology - CRYPTO 87; R. Impagliazzo and M. Yung, Direct minimum knowledge computations in: Advances in Cryptology - CRYPTO 87 |
| [27] | Niven, I.; Zuckerman, H. S., An Introduction to the Theory of Numbers (1960), Wiley: Wiley New York · Zbl 0186.36601 |
| [28] | Shamir, A., How to share a secret, Comm. ACM, 22, 612-613 (1979) · Zbl 0414.94021 |
| [29] | Tompa, M.; Woll, H., Random self-reducibility and zero-knowledge interactive proofs of possession of information, Proc. 28th Symp. in Foundations of Comput. Sci., 472-482 (1987) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
