Paper 2014/611

Accumulating Automata and Cascaded Equations Automata for Communicationless Information Theoretically Secure Multi-Party Computation

Shlomi Dolev, Niv Gilboa, and Ximing Li


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 {\em accumulating automata} and {\em cascaded equations automata} which may be of an independent interest. As an application of {\em accumulating automata} and {\em cascaded equations automata}, secure and private repeated computations on a secret shared file among communicationless clouds are presented.

Note: minor change in tile

Available format(s)
Publication info
Preprint. MINOR revision.
Secret sharingAutomataTheoretically secureMulti-Party ComputationCommunicationless clouds
Contact author(s)
liximing cn @ gmail com
2014-08-14: revised
2014-08-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shlomi Dolev and Niv Gilboa and Ximing Li},
      title = {Accumulating Automata and Cascaded Equations Automata for Communicationless Information Theoretically Secure Multi-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/611},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.