We propose protocols for obliviously evaluating finite-state machines, i.e.,
the evaluation is shared between the provider of the finite-state machine and
the provider of the input string in such a manner that neither party learns the
other’s input, and the states being visited are hidden from both. For alphabet
size $|Sigma|$, number of states $|Q|$, and input length $n$, previous
solutions have either required a number of rounds linear in $n$ or
communication $Omega(n|Sigma||Q|log|Q|)$. Our solutions require 2 rounds
with communication $O(n(|Sigma|+|Q|log|Q|))$. We present two different
solutions to this problem, a two-party one and a setting with an untrusted but
non-colluding helper.

Go to Source of this post
Author Of this post: <a href="http://arxiv.org/find/cs/1/au:+Dowsley_R/0/1/0/all/0/1">Rafael Dowsley</a>, <a href="http://arxiv.org/find/cs/1/au:+Horst_C/0/1/0/all/0/1">Caleb Horst</a>, <a href="http://arxiv.org/find/cs/1/au:+Nascimento_A/0/1/0/all/0/1">Anderson C. A. Nascimento</a>

By admin