IACR News item: 13 August 2014
Shlomi Dolev, Niv Giboa, Ximing Li
ePrint ReportConsider 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.
Additional news items may be found on the IACR news page.