Gesellschaft fr Informatik e.V.

Lecture Notes in Informatics

SICHERHEIT 2005, Sicherheit - Schutz und Zuverlässigkeit, Beiträge der 2. Jahrestagung des Fachbereichs Sicherheit der Gesellschaft für Informatik e.V. (GI), 5.-8. April 2005 in Regensburg. GI 2005 P-62, 41-52 (2005).

GI, Gesellschaft für Informatik, Bonn


Hannes Federrath (ed.)

Copyright © GI, Gesellschaft für Informatik, Bonn


Secure multi-party computation with security modules

Z. Benenson , F. C. Gärtner and D. Kesdogan


We consider the problem of secure multi-party computation (SMC) in a new model where individual processes contain a tamper-proof security module. Security modules can be trusted by other processes and can establish secure channels between each other. However, their availability is restricted by their host, i.e., a corrupted party can stop the computation of its own security module as well as drop any message sent by or to its security module. In this model we show that SMC is solvable if and only if a majority of processes is correct. We prove this by relating SMC to the problem of Uniform Interactive Consistency among security modules (a variant of the Byzantine Generals Problem from the area of fault-tolerance). The obtained solutions to SMC for the first time allow to compute any function securely with a complexity which is polynomial only in the number of processes (i.e., the complexity does not depend on the function which is computed). We conclude that adding secure hardware does not improve the resilience of SMC but can effectively improve the efficiency.

Full Text: PDF

GI, Gesellschaft für Informatik, Bonn
ISBN 3-88579-391-1

Last changed 24.01.2012 21:48:50