Abstract
Consider a center possessing a trusted (tamper proof) device that wishes
to securely compute a public function over private inputs that are
contributed by some network nodes. In network scenarios that support
direct communication of nodes with the center, the computation can be
done by the nodes encrypting their inputs under the device’s public key
and sending the ciphertexts to the center which, in turn, feeds them to
the trusted device that computes the function. In many modern networking
scenarios, however, the center and the contributing nodes are not
directly connected/connectable, in which case the discovery and
collection of inputs can only be performed by an agent (or agents)
released to the network by the center. This introduces a new set of
issues for secure computation. In this work we consider an agent that is
released, sweeps the network once and then returns to its origin. The
direct solution, in this case, is for the agent to possess a certified
public key of the trusted device and for the nodes to contribute their
inputs as ciphertexts under this key; once the agent collects all inputs
it reconnects with the center for function computation. The above
single-sweep simple collection requires the agent to store a linear
number of ciphertexts. The goal of this work is to formalize and solve
the above problem for a general set of functions by an agent that
employs sub-linear storage while maintaining input privacy (an important
technical requirement akin of that of “Private Information Retrieval”
protocols).
Original language | English |
---|---|
Title of host publication | Automata, Languages and Programming |
Subtitle of host publication | 36th Internatilonal Collogquium, ICALP 2009, Rhodes, greece, July 5-12, 2009, Proceedings, Part II |
Editors | Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, Wolfgang Thomas |
Place of Publication | Berlin, Heidelberg |
Publisher | Springer Berlin Heidelberg |
Pages | 534-545 |
Number of pages | 12 |
ISBN (Electronic) | 978-3-642-02930-1 |
ISBN (Print) | 978-3-642-02929-5 |
DOIs | |
Publication status | Published - 2009 |