Subquadratic zero-knowledge

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Subquadratic zero-knowledge

Full text

Pdf (1.91 MB)

Source

Journal of the ACM (JACM) archive
Volume 42 , Issue 6 (November 1995) table of contents

Pages: 1169 - 1193

Year of Publication: 1995

ISSN:0004-5411

Authors

Joan Boyar	Odense Univ., Odense, Denmark
Gilles Brassard	Univ. of Montreal, Montreal, P.Q., Canada
René Peralta	Univ. of Wisconsin at Milwaukee

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 21, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/227683.227686 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	~At.o~, N., GOLDREICH, O., H.~STAD, J., AND PERALTA, R. 1992. Simple constructions of almost ~k-wise independent random variables. Ran. Struct. Algorithms 3, 3, 289-304.
	2	~ARORA, S., Lu~qo, C., MOTWA~I, R., SUVAN, M., AND SZEGEDY, M. 1992. Proof verification and ~hardness of approximation problems. In Proceedings of the 33rd IEEE Annual Symposium on ~Foundations of Computer Science. (Pittsburgh, Pa., Oct. 24-27). IEEE Computer Society Press, ~Los Alamitos, Calif., pp. 14-23.
	3	László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
	4	Eric Bach, Realistic analysis of some randomized algorithms, Journal of Computer and System Sciences, v.42 n.1, p.30-53, Feb. 1991 [doi>10.1016/0022-0000(91)90038-7]
	5	~BLUM, M. 1987. How to prove a theorem so that no one else can claim it. In Proceedings of the ~1986 International Congress of Mathematicians (Berkeley, Calif., Aug. 3-11). American Mathe- ~matical Society, Providence, R.I., pp. 1444-1451.
	6	Manuel Blum , Paul Feldman , Silvio Micali, Non-interactive zero-knowledge and its applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.103-112, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62222]
	7	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	8	~BOYAR, J., AND DAMG.~.RD, I.B. 1990. A discrete logarithm blob for noninteractive XOR gates. ~Tech. Rep. DAIMI PB-327 (Aug.). Computer Science Dept., Aarhus Univ., Denmark.
	9	Joan Boyar , Faith Fich , Kim S. Larsen, Bounds on certain multiplications of affine combinations, Discrete Applied Mathematics, v.52 n.2, p.155-167, Aug. 15, 1994 [doi>10.1016/0166-218X(94)90079-5]
	10	Joan F. Boyar , Stuart A. Kurtz, A discrete logarithm implementation of perfect zero-knowledge blobs, Journal of Cryptology, v.2 n.2, p.63-76, 1990
	11	~BOY^R, J., LUND, C., AND PERALTA, R. 1993. On the communication complexity of zero-knowl- ~edge proofs. J. Crypt. 6, 2, 65-85.
	12	Joan Boyar , Rene Peralta, Efficient Non-Interactive Zero-Knowledge Proofs of Circuit Satisfiability, University of Southern Denmark, 1994
	13	Gilles Brassard, How convincing is your protocol?, ACM SIGACT News, v.22 n.1, p.5-12, Winter 1991 [doi>10.1145/122413.122414]
	14	Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
	15	~BRASSARD, G., ANy CR~.PEAU, C. 1986. Non-transitive transfer of confidence: A perfect zero- ~knowledge interactive protocol for SAT and beyond. In Proceedings of the 27th IEEE Annual ~Symposium on Foundations of Computer Science. (Toronto, Ontario, Canada, Oct. 27-29). IEEE ~Computer Society Press, Los Alamitos, Calif., pp. 188-195.
	16	Gilles Brassard , Claude Crépeau, Zero-knowledge simulation of Boolean circuits, Proceedings on Advances in cryptology---CRYPTO '86, p.223-233, January 1987, Santa Barbara, California, United States
	17	Gilles Brassard , Claude Crepeau, Sorting out zero-knowledge, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.181-191, November 1990, Houthalen, Belgium
	18	David Chaum, Demonstrating that a public predicate can be satisfied without revealing any information about how, Proceedings on Advances in cryptology---CRYPTO '86, p.195-199, January 1987, Santa Barbara, California, United States
	19	David Chaum , Ivan Damgård , Jeroen van de Graaf, Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.87-119, August 16-20, 1987
	20	Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
	21	I. B. Damgård, On the randomness of Legendre and Jacobi sequences, Proceedings on Advances in cryptology, p.163-172, February 1990, Santa Barbara, California, United States
	22	~D~MGARD, 1. B. 1993. Non-interactive circuit based proofs and non-interactive perfect zero- ~knowledge with preprocessing. In Advances in Cryptology--Proceedings of Eurocrypt '92 (Bal- ~atonfured, Hungary, May 24-28, 1992). Springer-Verlag, Berlin, Germany, pp. 341-355.
	23	A. De Santis , S. Micali , G. Persiano, Non-interactive zero-knowledge with preprocessing, Proceedings on Advances in cryptology, p.269-282, February 1990, Santa Barbara, California, United States
	24	U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
	25	~FEIGE, U., LAPIDOT, D., AND SHAMIR, A. 1990. Multiple non-interactive zero-knowledge proofs ~based on a single random string. In Proceedings of the 31st Annual IEEE Symposium on ~Foundations of Computer Science (St. Louis, Missouri, Oct. 22-24). IEEE Computer Society ~Press, Los Alamitos, Calif., pp. 308-317.
	26	~FREIVALDS, R. 1979. Fast probabilistic algorithms. In Proceedings of the 8th Symposium on the ~Mathematical Foundations of Computer Science (Olomouc, Czechoslovakia, Sept. 3-7). ~Springer-Verlag, Berlin, Germany, pp. 57-69.
	27	Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
	28	~GOLDWASSER, S., AND MICALI, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, ~270-299.
	29	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	30	Joe Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.723-732, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129782]
	31	~trdLIAN, J. 1994. On the complexity of bounded-interaction and noninteractive zero-knowledge ~proofs. In Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science ~(Santa Fe, New Mexico, Nov. 20-22). IEEE Computer Society Press, Los Alamitos, ~Calif., pp. 466-477.
	32	~KILIAN, J., MICALI, S., AND OSTROVSKY, R. 1989. Minimum resource zero-knowledge proofs. In ~Proceedings of the 30th IEEE Annual Symposium on Foundations of Computer Science (Research ~Triangle Park, North Carolina, Oct. 30-Nov. 1). IEEE Computer Society Press, Los Alamitos, ~Calif., pp. 474-479.
	33	~MOSER, L. 1953. On non-averaging sets of integers. Can. J. Math. 5, 245-252.
	34	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
	35	~NAOR, M. 1991. Bit commitment using pseudo-randomness. J. Crypt. 4, 2, 151-158.
	36	~PERALTA, R. 1990. On the randomness complexity of algorithms. Computer Science Res. Rep. ~TR 90-1. Univ. of Wisconsin-Milwaukee, Milwaukee, Wis.
	37	~PERALTA, R. 1992. On the distribution of quadratic residues and non-residues modulo a prime ~number. Math. Comput. 58, 433-440.
	38	~SALEM, R., AND SPENCER, D.C. 1942. On sets of integers which contain no three terms in ~arithmetical progression. Proc. Nat. Acad. Sci. U.S.A. 28, 561-563.
	39	Jeroen van de Graaf , René Peralta, A Simple and Secure Way to Show the Validity of Your Public Key, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.128-134, August 16-20, 1987
	40	~YAO, A. 1982. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE ~Annual Symposium on Foundations of Computer Science (Chicago, Ill., Nov. 3-5). IEEE ~Computer Society Press, Los Alamitos, Calif., pp. 80-91.

CITED BY 2

	Ronald Cramer , Ivan Damgård, Linear zero-knowledge—a note on efficient zero-knowledge proofs and arguments, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.436-445, May 04-06, 1997, El Paso, Texas, United States
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Zero-knowledge from secure multiparty computation, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA