Abstract
We introduce a novel approach to general secure multiparty computation that avoids the intensive use of verifiable secret sharing characterizing nearly all previous protocols in the literature. Instead, our scheme involves manipulation of ciphertexts for which the underlying private key is shared by participants in the computation. The benefits of this protocol include a high degree of conceptual and structural simplicity, low message complexity, and substantial flexibility with respect to input and output value formats. We refer to this new approach as mix and match. While the atomic operations in mix and match are logical operations, rather than full field operations as in previous approaches, the techniques we introduce are nonetheless highly practical for computations involving intensive bitwise manipulation. One application for which mix and match is particularly well suited is that of sealed-bid auctions. Thus, as another contribution in this paper, we present a practical, mix-and-match-based auction protocol that is fully private and non-interactive and may be readily adapted to a wide range of auction strategies.
Chapter PDF
Similar content being viewed by others
References
M. Abe. Universally verifiable mix-net with verification work independent of the number of mix-servers. In K. Nyberg, ed., EUROCRYPT’ 98, pages 437–447. Springer-Verlag, 1998. LNCS no. 1403.
M. Abe. A mix-network on permutation networks. In K.Y. Lam, C. Xing, and E. Okamoto, eds., ASIACRYPT’ 99, pages 258–273, 1999. LNCS no. 1716.
M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In ACM CCS’ 93, pages 62–73. ACM, 1993.
M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for noncryptographic fault-tolerant distributed computations. In STOC’ 88, pages 1–10. ACM, 1988.
C. Cachin. Efficient private bidding and auctions with an oblivious third party. In G. Tsudik, ed., ACM CCS’ 99, pages 120–127. ACM, 1999.
J. Camenisch and M. Michels. Proving that a number is the product of two safe primes. In J. Stern, ed., EUROCRYPT’ 99, pages 107–122. Springer-Verlag, 1999. LNCS no. 1592.
R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143–202, 2000.
R. Canetti, R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Adaptive security for threshold cryptosystems. In M. Weiner, ed., CRYPTO’ 99, pages 98–115. Springer-Verlag, 1999. LNCS no. 1166.
R. Canetti, R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. The (in)security of distributed key generation in dlog-based cryptosystems. In J. Stern, ed., EUROCRYPT’ 99, pages 295–310. Springer-Verlag, 1999. LNCS no. 1592.
D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2):84–88, 1981.
D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols. In STOC’ 88, pages 11–19. ACM, 1988.
D. Chaum, I. Damgård, and J. van de Graaf. Multiparty computations ensuring privacy of each party’s input and correctness of the result. In C. Pomerance, ed., CRYPTO’ 87, pages 87–119. Springer-Verlag, 1987. LNCS no. 293.
D. Chaum and T.P. Pedersen. Wallet databases with observers. In E.F. Brickell, ed., CRYPTO’ 92, pages 89–105. Springer-Verlag, 1992. LNCS no. 740.
B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults. In FOCS’ 85, pages 383–395. IEEE Computer Society, 1985.
R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, and T. Rabin. Efficient multiparty computations secure against an adaptive adversary. In J. Stern, ed., EUROCRYPT’ 99, pages 311–326. Springer-Verlag, 1999. LNCS no. 1592.
R. Cramer, I. Damgård, and J.B. Nielsen. Multiparty computation from threshold homomorphic encryption, 2000. IACR ePrint archive manuscript.
R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Y.G. Desmedt, ed., CRYPTO’ 94, pages 174–187. Springer-Verlag, 1994. LNCS no. 839.
R. Cramer and V. Shoup. A practical public-key cryptosystem provably secure against adaptive chosen ciphertext attack. In H. Krawczyk, ed., CRYPTO’ 98, pages 13–25. Springer-Verlag, 1998. LNCS no. 1462.
G. Di Crescenzo. Private selective payment protocols. In P. Syverson, ed., Financial Cryptography’ 00, 2000. To appear.
A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In J. L. Massey, ed., EUROCRYPT’ 86, pages 186–194. Springer-Verlag, 1986. LNCS no. 263.
M. Franklin and M. Reiter. The design and implementation of a secure auction server. IEEE Transactions on Software Engineering, 22(5):302–312, 1996.
M.K. Franklin and S. Haber. Joint encryption and message-efficient secure computation. Journal of Cryptology, 9(4):217–232, 1996.
A. Fujioka, T. Okamoto, and K. Ohta. A practical secret voting scheme for large scale elections. In J. Seberry and Y. Zheng, eds., AUSCRYPT’ 92, pages 244–251. Springer-Verlag, 1992. LNCS no. 718.
T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31:469–472, 1985.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS signatures. In U. Maurer, ed., EUROCRYPT’ 96, pages 354–371. Springer-Verlag, 1996. LNCS no. 1070.
R. Gennaro, M. Rabin, and T. Rabin. Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In PODC’ 98, pages 101–111. ACM, 1998.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In STOC’ 87, pages 218–229. ACM, 1987.
S. Goldwasser and S. Micali. Probabilistic encryption. J. Comp. Sys. Sci, 28(1):270–299, 1984.
M. Harkavy, J.D. Tygar, and H. Kikuchi. Electronic auctions with private bids. In 3rd USENIX Workshop on Electronic Commerce, pages 61–73, 1999.
M. Hirt, U. Maurer, and B. Przydatek. Efficient secure multi-party computation. In T. Okamoto, ed., ASIACRYPT’ 00, 2000. To appear.
P. Horster, M. Michels, and H. Petersen. Some remarks on a receipt free and universally verifiable mix-type voting scheme. In K. Kim and T. Matsumoto, eds., ASIACRYPT’ 96, pages 125–132. Springer-Verlag, 1996. LNCS no. 1163.
M. Jakobsson. A practical mix. In K. Nyberg, ed., EUROCRYPT’ 98, pages 448–461. Springer-Verlag, 1998. LNCS no. 1403.
M. Jakobsson. Flash mixing. In PODC’ 99, pages 83–89. ACM, 1999.
M. Jakobsson and A. Juels. Millimix: Mixing in small batches, June 1999. DIMACS Technical Report 99-33.
A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.
M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design. In 1st ACM Conf. on Electronic Commerce, pages 129–139. ACM, 1999.
W. Ogata, K. Kurosawa, K. Sako, and K. Takatani. Fault tolerant anonymous channel. In ICICS’ 97, pages 440–444. Springer-Verlag, 1997. LNCS no. 1334.
C. Park, K. Itoh, and K. Kurosawa. All/nothing election scheme and anonymous channel. In T. Helleseth, ed., EUROCRYPT’ 93. Springer-Verlag, 1993. LNCS no. 921.
T. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, ed., CRYPTO’ 91, pages 129–140. Springer-Verlag, 1991. LNCS no. 576.
K. Sako. An auction protocol which hides bids of losers. In H. Imai and Y. Zheng, editors, PKC’ 00, pages 422–432. Springer-Verlag, 2000. LNCS no. 1751.
K. Sako and J. Kilian. Receipt-free mix-type voting scheme-a practical solution to the implementation of a voting booth. In L.C. Guillou and J.-J. Quisquater, eds., EUROCRYPT’ 95. Springer-Verlag, 1995. LNCS no. 921.
C.P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4:161–174, 1991.
Y. Tsiounis and M. Yung. On the security of ElGamal-based encryption. In H. Imai and Y. Zheng, eds., PKC’ 98, pages 117–134. Springer-Verlag, 1998. LNCS no. 1431.
A.C. Yao. Protocols for secure computations (extended abstract). In FOCS’ 82, pages 160–164. IEEE Computer Society, 1982.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jakobsson, M., Juels, A. (2000). Mix and Match: Secure Function Evaluation via Ciphertexts. In: Okamoto, T. (eds) Advances in Cryptology — ASIACRYPT 2000. ASIACRYPT 2000. Lecture Notes in Computer Science, vol 1976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44448-3_13
Download citation
DOI: https://doi.org/10.1007/3-540-44448-3_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41404-9
Online ISBN: 978-3-540-44448-0
eBook Packages: Springer Book Archive