Abstract
This paper investigates one-round secure computation between two distrusting parties: Alice and Bob each have private inputs to a common function, but only Alice, acting as the receiver, is to learn the output; the protocol is limited to one message from Alice to Bob followed by one message from Bob to Alice. A model in which Bob may be computationally unbounded is investigated, which corresponds to informationtheoretic security for Alice. It is shown that
-
1.
for honest-but-curious behavior and unbounded Bob, any function computable by a polynomial-size circuit can be computed securely assuming the hardness of the decisional Diffie-Hellman problem;
-
2.
for malicious behavior by both (bounded) parties, any function computable by a polynomial-size circuit can be computed securely, in a public-key framework, assuming the hardness of the decisional Diffie-Hellman problem.
The results are applied to secure autonomous mobile agents, which migrate between several distrusting hosts before returning to their originator. A scheme is presented for protecting the agent’s secrets such that only the originator learns the output of the computation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
M. Abadi and J. Feigenbaum, “Secure circuit evaluation: A protocol based on hiding information from an oracle,” Journal of Cryptology, vol. 2, pp. 1–12, 1990.
M. Abadi, J. Feigenbaum, and J. Kilian, “On hiding information from an oracle,” Journal of Computer and System Sciences, vol. 39, pp. 21–50, 1989.
D. Beaver, “Foundations of secure interactive computing,” in Proc. CRYPTO’ 91 (J. Feigenbaum, ed.), LNCS 576, 1992.
M. Bellare and S. Micali, “Non-interactive oblivious transfer and applications,” in Proc. CRYPTO’ 89 (G. Brassard, ed.), LNCS435, pp. 547–557, 1990.
M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” in Proc. 20th STOC, pp. 1–10, 1988.
M. Blum, P. Feldman, and S. Micali, “Non-interactive zero-knowledge proof systems and its applications,” in Proc. 20th STOC, pp. 103–112, 1988.
D. Boneh and R. J. Lipton, “Searching for elements in black box fields and applications,” in Proc. CRYPTO’ 96, LNCS 1109, 1996.
G. Brassard, C. Crépeau, and J.-M. Robert, “Information theoretic reductions among disclosure problems,” in Proc. 27th FOCS, 1986.
R. Canetti, “Security and composition of multi-party cryptographic protocols,” Journal of Cryptology, vol. 13, no. 1, pp. 143–202, 2000.
R. Canetti, O. Goldreich, S. Goldwasser, and S. Micali, “Resettable zero-knowledge,” in Proc. 32nd STOC, 2000.
D. Chaum, I. Damgård, and J. van deGraaf, “Multiparty computations ensuring privacy of each party’s input and correctness of the result,” in Proc. CRYPTO’ 87 (C. Pomerance, ed.), LNCS 293, 1988.
R. Cramer, I. Damgård, and B. Schoemakers, “Proofs of partial knowledge and simplified design of witness hiding protocols,” in Proc. CRYPTO’ 94 (Y. G. Desmedt, ed.), LNCS 839, 1994.
U. Feige, J. Kilian, and M. Naor, “A minimal model for secure computation (extended abstract),” in Proc. 26th STOC, pp. 554–563, 1994.
U. Feige, D. Lapidot, and A. Shamir, “Multiple noninteractive zero knowledge proofs under general assumptions,” SI AM Journal on Computing, vol. 29, no. 1, pp. 1–28, 1999.
J. Feigenbaum and M. Merritt, “Open questions, talk abstracts, and summary of discussions,” in Distributed Computing and Cryptography, AMS, 1991.
O. Goldreich, S. Goldwasser, and S. Micali, “How to construct random functions,” Journal of the ACM, vol. 33, pp. 792–807, Oct. 1986.
O. Goldreich, S. Micali, and A. Wigderson, “How to play any mental game or a completeness theorem for protocols with honest majority,” in Proc. 19th STOC, pp. 218–229, 1987.
S. Micali and P. Rogaway, “Secure computation,” in Proc. CRYPTO’ 91 (J. Feigenbaum, ed.), LNCS 576, pp. 392–404, 1992.
M. Naor and O. Reingold, “Number-theoretic constructions of efficient pseudorandom functions,” in Proc. 38th FOCS, 1997.
R. Ostrovsky, R. Venkatesan, and M. Yung, “Fair games against an all-powerful adversary,” in Advances in Computational Complexity Theory, AMS, 1993.
C. Rackoff and D. R. Simon, “Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack,” in Proc. CRYPTO’ 91 (J. Feigenbaum, ed.), LNCS 576, pp. 433–444, 1992.
R. L. Rivest, L. Adleman, and M. L. Dertouzos, “On data banks and privacy homomorphisms,” in Foundations of Secure Computation (R. A. DeMillo, D. P. Dobkin, A. K. Jones, and R. J. Lipton, eds.), pp. 169–177, Academic Press, 1978.
P. Rogaway, The Round Complexity of Secure Protocols. PhD thesis, MIT, 1991.
T. Sander and C. F. Tschudin, “Protecting mobile agents against malicious hosts,” in Mobile Agents and Security (G. Vigna, ed.), LNCS 1419, 1998.
T. Sander, A. Young, and M. Yung, “Non-interactive CryptoComputing for NC1,” in Proc. 40th FOCS, 1999.
A. C. Yao, “How to generate and exchange secrets,” in Proc. 27th FOCS, pp. 162–167, 1986.
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
Cachin, C., Camenisch, J., Kilian, J., Müller, J. (2000). One-Round Secure Computation and Secure Autonomous Mobile Agents. In: Montanari, U., Rolim, J.D.P., Welzl, E. (eds) Automata, Languages and Programming. ICALP 2000. Lecture Notes in Computer Science, vol 1853. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45022-X_43
Download citation
DOI: https://doi.org/10.1007/3-540-45022-X_43
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67715-4
Online ISBN: 978-3-540-45022-1
eBook Packages: Springer Book Archive