Abstract
We consider a new model for online secure computation on encrypted inputs in the presence of malicious adversaries. The inputs are independent of the circuit computed in the sense that they can be contributed by separate third parties. The model attempts to emulate as closely as possible the model of “Computing with Encrypted Data” that was put forth in 1978 by Rivest, Adleman and Dertouzos which involved a single online message. In our model, two parties publish their public keys in an offline stage, after which any party (i.e., any of the two and any third party) can publish encryption of their local inputs. Then in an on-line stage, given any common input circuit C and its set of inputs from among the published encryptions, the first party sends a single message to the second party, who completes the computation.
Chapter PDF
Similar content being viewed by others
References
Aiello, W., Ishai, Y., Reingold, O.: Priced oblivious transfer: How to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135. Springer, Heidelberg (2001)
Beaver, D.: Minimal-latency secure function evaluation. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 335–350. Springer, Heidelberg (2000)
Boneh, D., Lipton, R.: Algorithms for black-box fields and their application to cryptography. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 283–297. Springer, Heidelberg (1996)
Cachin, C., Camensich, J., Kilian, J., Müller, A.J.: One-round secure computation and secure autonomous mobile agents. In: Proc. 27th International Colloquium on Automata, Languages and Programming (ICALP) (2000)
Camenisch, J., Michels, M.: Proving that a number is the product of two safe primes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 107–122. Springer, Heidelberg (1999)
Camenisch, J., Shoup, V.: Practical verifiable encryption and decryption of discrete logarithms. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 126–144. Springer, Heidelberg (2003)
Camenisch, J., Stadler, M.: Efficient group signature schemes for large groups. In: Sommer, G., Daniilidis, K., Pauli, J. (eds.) CAIP 1997. LNCS, vol. 1296, pp. 410–424. Springer, Heidelberg (1997)
Cramer, R., Genaro, R., Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 103–118. Springer, Heidelberg (1997)
Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. on Information Theory, IT 22(6), 644–654 (1976)
ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31, 469–472 (1985)
Even, S., Goldreich, O., Micali, S.: On-line/off-line digital schemes. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 263–275. Springer, Heidelberg (1990)
Feigenbaum, J., Merritt, M.: Open questions, talk abstracts, and summary of discussions. In: DIMACS. Series in Discrete Mathematics and Theoretical Computer Science, pp. 1–45 (1991)
Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Massey, J.L. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Furukawa, J., Sako, K.: An efficient scheme for proving a shuffle. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 368–387. Springer, Heidelberg (2001)
Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 151–160 (1998)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proc. 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 218–229. ACM Press, New York (1987)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984)
Horvitz, O., Katz, J.: Universally-composable two-party computation in two rounds. In: Advances in Cryptology — (CRYPTO 2007), pp. 111–129 (2007)
Jarecki, S., Shmatikov, V.: Efficient two-party secure computation on committed inputs. In: Advances in Cryptology — (EUROCRYPT 2007) (2007)
Lindell, Y., Pinkas, B.: An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Advances in Cryptology — (EUROCRYPT 2007) (2007)
Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: 1st ACM Conference on Electronic Commerce, ACM Press, New York (1999)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 107–122. Springer, Heidelberg (1999)
Rivest, R., Adelman, L., Dertouzos, M.L.: On data banks and privacy homomorphisms. In: DeMillo, R.A., Dobkin, D.P., Jones, A.K., Lipto, R.J. (eds.) Foundations of Secure Computation, pp. 169–17. Academic Press, London (1978)
Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 543–553 (1999)
Sander, T., Tschudin, C.F.: Protecting mobile agents against malicious hosts. In: Vigna, G. (ed.) Mobile Agents and Security. LNCS, vol. 1419, pp. 44–61. Springer, Heidelberg (1998)
Sander, T., Young, A., Yung, M.: Non-interactive cryptocomputing for NC1. In: Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 554–567 (1999)
De Santis, A., Persiano, G.: Zero-knowledge proofs of knowledge without interaction. In: Proc. 33rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 427–437 (1992)
De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M.: On monotone formula closure of SZK. In: Proc. 35th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 454–465. IEEE Computer Society Press, Los Alamitos (1994)
Schnorr, C.P.: Efficient signature generation by smart cards. Journal of Cryptology 4, 161–174 (1991)
Valiant, L.: Universal circuits. In: Proc. 8th Annual ACM Symposium on Theory of Computing (STOC), pp. 196–203 (1976)
Yao, A.C.: How to generate an exchange secrets. In: Proc. 27th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 162–167 (1986)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Choi, S.G., Elbaz, A., Juels, A., Malkin, T., Yung, M. (2007). Two-Party Computing with Encrypted Data. In: Kurosawa, K. (eds) Advances in Cryptology – ASIACRYPT 2007. ASIACRYPT 2007. Lecture Notes in Computer Science, vol 4833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76900-2_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-76900-2_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76899-9
Online ISBN: 978-3-540-76900-2
eBook Packages: Computer ScienceComputer Science (R0)