English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the problem of private “swarm” computing,  n  agents wish to securely and distributively perform a computation on common inputs, in such a way that even if the entire memory contents of some of them are exposed, no information is revealed about the state of the computation. Recently, Dolev, Garay, Gilboa and Kolesnikov [Innov. Comput. Sci. (2011), 32–44] considered this problem in the setting of information-theoretic security, showing how to perform such computations on input streams of unbounded length. However, the cost of their solution is exponential in the size of the  finite state automaton  (FSA) computing the function. In this work we are interested in an efficient (i.e., polynomial time) computation of the above model, at the expense of minimal additional assumptions. Relying on the existence of one-way functions, we show how to process unbounded inputs (polynomial in the security parameter) at a cost linear in  m , the number of FSA states. In particular, our algorithms achieve the following: In the case of ( n , n )-reconstruction (i.e., in which all  n  agents participate in the reconstruction of the distributed computation) and at most  n  - 1 agents are corrupted, the time required to process each input symbol and the time complexity for reconstruction areO  (  m  n  )    $O(mn)$   , while agent storage isO  (  m  +  n  )    $O(m+n)$   . In the case of(  n  -  t  ,  n  )    $(n-t,n)$   -reconstruction (where onlyn  -  t    $n-t$    agents take part in the reconstruction) and at most  t  agents are corrupted, the agents' storage isO  (n  -  1    n  -  t+  m  )    $O(\binom{n-1}{n-t}+m)$   , the time required to process each input symbol isO  (  mn  -  1    n  -  t)    $O(m\binom{n-1}{n-t})$    and the time complexity of reconstruction isO  (  m  t  )    $O(mt)$   . We achieve the above through a carefully orchestrated use of pseudo-random generators and secret-sharing, and in particular a novel share re-randomization technique which might be of independent interest.

Towards efficient private distributed computation on unbounded input streams