×

Private computation using a PEZ dispenser. (English) Zbl 1059.68038

Summary: We show how a (big) PEZ dispenser can be used by two or more players to compute a function of their inputs while hiding the values of the inputs from each other. In contrast to traditional approaches for solving this problem, ours does not require any use of randomness.

MSC:

68P25 Data encryption (aspects in computer science)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Beaver, Precomputing oblivious transfer, in: D. Coppersmith (Ed.), Proc. 15th Annu. Internat. Cryptology Conf., Advances in Cryptology—CRYPTO ’95, Santa Barbara, CA, 1995, Lecture Notes in Computer Science, Vol. 963, Springer, Berlin, 1995, pp. 97-109.; D. Beaver, Precomputing oblivious transfer, in: D. Coppersmith (Ed.), Proc. 15th Annu. Internat. Cryptology Conf., Advances in Cryptology—CRYPTO ’95, Santa Barbara, CA, 1995, Lecture Notes in Computer Science, Vol. 963, Springer, Berlin, 1995, pp. 97-109. · Zbl 0876.94021
[2] M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in: Proc. 20th Annu. ACM Symp. on Theory of Computing (STOC ’88), Chicago, IL, 1988, pp. 1-10.; M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in: Proc. 20th Annu. ACM Symp. on Theory of Computing (STOC ’88), Chicago, IL, 1988, pp. 1-10.
[3] D. Chaum, C. Crépeau, I. Damgård, Multiparty unconditionally secure protocols (extended abstract), in: Proc. 20th Annu. ACM Symp. on Theory of Computing (STOC ’88), Chicago, IL, 1988, pp. 11-19.; D. Chaum, C. Crépeau, I. Damgård, Multiparty unconditionally secure protocols (extended abstract), in: Proc. 20th Annu. ACM Symp. on Theory of Computing (STOC ’88), Chicago, IL, 1988, pp. 11-19.
[4] C. Crépeau, J. Kilian, Discreet solitary games, in: D.R. Stinson (Ed.), Proc. 13th Annu. Internat. Cryptology Conf., Advances in Cryptology—CRYPTO ’93, Santa Barbara, CA, 1993, Lecture Notes in Computer Science, Vol. 773, Springer, Berlin, 1994, pp. 319-330.; C. Crépeau, J. Kilian, Discreet solitary games, in: D.R. Stinson (Ed.), Proc. 13th Annu. Internat. Cryptology Conf., Advances in Cryptology—CRYPTO ’93, Santa Barbara, CA, 1993, Lecture Notes in Computer Science, Vol. 773, Springer, Berlin, 1994, pp. 319-330.
[5] R. Fagin, M. Naor, P. Winkler, Comparing information without leaking it, Commun. ACM Vol. 39 (5) (1996) pp. 77-85.; R. Fagin, M. Naor, P. Winkler, Comparing information without leaking it, Commun. ACM Vol. 39 (5) (1996) pp. 77-85.
[6] M.J. Fischer, R.N. Wright, Multiparty secret key exchange using a random deal of cards, in: J. Feigenbaum (Ed.), Proc. 11th Annu. Internat. Cryptology Conf., Advances in Cryptology—CRYPTO ’91, Santa Barbara, CA, 1992, Lecture Notes in Computer Science, Vol. 576, Springer, 1992, pp. 141-155.; M.J. Fischer, R.N. Wright, Multiparty secret key exchange using a random deal of cards, in: J. Feigenbaum (Ed.), Proc. 11th Annu. Internat. Cryptology Conf., Advances in Cryptology—CRYPTO ’91, Santa Barbara, CA, 1992, Lecture Notes in Computer Science, Vol. 576, Springer, 1992, pp. 141-155. · Zbl 0763.94010
[7] O. Goldreich, S. Micali, A. Wigderson, How to play any mental game (extended abstract), in: Proc. 19th Annu. ACM Symp. on Theory of Computing (STOC ’87), New York, NY, 1987, pp. 218-229.; O. Goldreich, S. Micali, A. Wigderson, How to play any mental game (extended abstract), in: Proc. 19th Annu. ACM Symp. on Theory of Computing (STOC ’87), New York, NY, 1987, pp. 218-229.
[8] Kushilevitz, E.; Rosén, A., A randomness-rounds tradeoff in private computation, SIAM J. Discrete Math., 11, 1, 61-80 (1998) · Zbl 0907.68101
[9] M. Naor, Y. Naor, O. Reingold, Applied Kid Cryptography or How to convince your children you are not cheating, available online at http://www.wisdom.weizmann.ac.il/ naor/onpub.html; M. Naor, Y. Naor, O. Reingold, Applied Kid Cryptography or How to convince your children you are not cheating, available online at http://www.wisdom.weizmann.ac.il/ naor/onpub.html
[10] M. Naor, A. Shamir, Visual cryptography, in: A. De Santis (Ed.), Proc. Workshop on the Theory and Application of Cryptographic Techniques, Advances in Cryptology—EUROCRYPT ’94, Perugia, Italy, 1994, Lecture Notes in Computer Science, Vol. 950, Springer, 1995, pp. 1-12.; M. Naor, A. Shamir, Visual cryptography, in: A. De Santis (Ed.), Proc. Workshop on the Theory and Application of Cryptographic Techniques, Advances in Cryptology—EUROCRYPT ’94, Perugia, Italy, 1994, Lecture Notes in Computer Science, Vol. 950, Springer, 1995, pp. 1-12. · Zbl 0878.94048
[11] R. Rivest, Unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer, Manuscript, 1999.; R. Rivest, Unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer, Manuscript, 1999.
[12] A.C. Yao, How to generate and exchange secrets, in: Proc. 27th Annu. Symp. on Foundations of Computer Science (FOCS ’86), Toronto, Canada, 1986, pp. 162-167.; A.C. Yao, How to generate and exchange secrets, in: Proc. 27th Annu. Symp. on Foundations of Computer Science (FOCS ’86), Toronto, Canada, 1986, pp. 162-167.
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.