Accumulating Automata and Cascaded Equations Automata for
Communicationless Secure Multi-Party Computation
Prof. Shlomi Dolev
Dean of the Faculty of Natural Sciences, Ben-Gurion University of the Negev
Information theoretically secure multi-party computation implies severe communication overhead among the computing participants, as there is a need to reduce the polynomial degree after each multiplication. In particular, when the input is (practically) unbounded, the number of multiplications and therefore the communication bandwidth among the participants may be practically unbounded. In some scenarios the communication among the participants should better be avoided altogether, avoiding linkage among the secret share holders. For example, when processes in clouds operate over streaming secret shares without communicating with each other, they can actually hide their linkage and activity in the crowd. An adversary that is able to compromise processes in the cloud may need to capture and analyze a very large number of possible shares.
Consider a dealer that wants to repeatedly compute functions on a long file with the assistance of m servers. The dealer does not wish to leak either the input file or the result of the computation to any of the servers. We investigate this setting given two constraints. The dealer is allowed to share each symbol of the input file among the servers and is allowed to halt the computation at any point. However, the dealer is otherwise stateless. Furthermore, each server is not allowed any communication beyond the shares of the inputs that it receives and the information it provides to the dealer during reconstruction.
We present a protocol in this setting for generalized string matching, including wildcards. We also present solutions for identifying other regular languages, as well as particular context free and context sensitive languages. The results can be described by a newly defined accumulating automata and cascaded equations automata which may be of an independent interest. As an application of accumulating automata and cascaded equations automata, secure and private repeated computations on a secret shared file among communicationless clouds are also presented.
Joint work with Niv Gilboa and Ximing Li.
Bio: Shlomi Dolev received his B.Sc. in Engineering and B.A. in Computer Science in 1984 and 1985, and his M.Sc. and D.Sc. in computer Science in 1990 and 1992 from the Technion Israel Institute of Technology. From 1992 to 1995 he was at Texas A&M University postdoc of Jennifer Welch. In 1995 he joined the Department of Mathematics and Computer Science at Ben-Gurion University where he is now a full professor. He was a visiting researcher/professor at MIT, DIMACS, and LRI, for several periods during summers. Shlomi is the author of the book "self-stabilization" published by the MIT Press. He published more than two hundreds journal and conference scientific articles, and patents. Shlomi served in the program committee of more than 90 conferences, chairing the ACM Symposium on Principles of Distributed Computing, and the International Symposium on DIStributed Computing.
He is an associate editor of the IEEE Transactions on Computers. His research grants include IBM faculty awards, Intel academic grants, Verisign, ISF, US Airforce, EU and NSF grants. Shlomi is the founding chair of the computer science department at Ben-Gurion University, where he now holds the Rita Altura trust chair in computer science.
His current research interests include distributed computing, distributed systems, security and cryptography and communication networks; in particular the self-stabilization property of such systems. Recently, he is involved in optical computing and brain science research. Today, Prof. Dolev is the dean of the faculty of natural sciences and the head of (IUCC) the Inter University Computation Center of Israel.