Title | ||
---|---|---|
A Low Communication Competitive Interactive Proof System for Promised Quadratic Residuosity. |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
1996 | 10.1007/s001459900005 | J. Cryptology |
Keywords | Field | DocType |
Competitive interactive proof systems,Communication complexity,Quadratic residuosity,Promise problems,Residue classes | Log-log plot,Discrete mathematics,Interactive proof system,Existential quantification,Quadratic equation,Communication complexity,Moduli,Mathematics | Journal |
Volume | Issue | ISSN |
9 | 2 | 0933-2790 |
ISBN | Citations | PageRank |
0-387-57766-1 | 1 | 0.35 |
References | Authors | |
13 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Toshiya Itoh | 1 | 604 | 101.29 |
Masafumi Hoshi | 2 | 1 | 0.35 |
Shigeo Tsujii | 3 | 598 | 131.15 |