One-Round Secure Computation and Secure Autonomous Mobile Agents
Christian Cachin, Jan Camenisch, Joe Kilian, Joy M\"uller
IBM Zurich Research Laboratory
CH-8803 R\"uschlikon, Switzerland
{cca,jca,jmu}@zurich.ibm.com
and
NEC Research Institute
Princeton, NJ 08540, USA
joe@research.nj.nec.com
ABSTRACT
This work 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 information-theoretic security for Alice.
It is shown that
* 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;
* 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.