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.