caa a22 4500 477063691 CHVBK 20180405111407.0 cr unu---uuuuu 170330e19960301xx s 000 0 eng 10.1007/BF00190804 doi (NATIONALLICENCE)springer-10.1007/BF00190804 A low communication competitive interactive proof system for promised quadratic residuosity [Elektronische Daten] [Toshiya Itoh, Masafumi Hoshi, Shigeo Tsujii] Bellare and Goldwasser showed that if the modulus N is guaranteed to be the product of O(log log ¦N¦) distinct odd primes, then quadratic residuosity has a competitive interactive proof system (with reasonably large communication complexity). In this paper we show that if the modulus N is guaranteed to be the product of O(log ¦N¦) distinct odd primes, then quadratic residuosity has a competitive interactive proof system with low communication complexity. International Association for Cryptologic Research, 1996 Competitive interactive proof systems nationallicence Communication complexity nationallicence Quadratic residuosity nationallicence Promise problems nationallicence Residue classes nationallicence Itoh Toshiya Department of Information Processing, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259 Nagatsuta, Midori-ku, 226, Yokohama, Japan aut Hoshi Masafumi Department of Information Processing, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259 Nagatsuta, Midori-ku, 226, Yokohama, Japan aut Tsujii Shigeo Department of Computer Science, Faculty of Science and Engineering, Chuo University, 1-13-27 Kasuga, Bunkyo-ku, 112, Tokyo, Japan aut Journal of Cryptology Springer-Verlag 9/2(1996-03-01), 101-109 0933-2790 9:2<101 1996 9 145 https://doi.org/10.1007/BF00190804 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00190804 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Itoh Toshiya Department of Information Processing, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259 Nagatsuta, Midori-ku, 226, Yokohama, Japan aut NATIONALLICENCE 700 1- Hoshi Masafumi Department of Information Processing, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259 Nagatsuta, Midori-ku, 226, Yokohama, Japan aut NATIONALLICENCE 700 1- Tsujii Shigeo Department of Computer Science, Faculty of Science and Engineering, Chuo University, 1-13-27 Kasuga, Bunkyo-ku, 112, Tokyo, Japan aut NATIONALLICENCE 773 0- Journal of Cryptology Springer-Verlag 9/2(1996-03-01), 101-109 0933-2790 9:2<101 1996 9 145 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer