Keeping Automata States Private

Consider a party that holds an automaton and an agent that executes that automaton on an unbounded sequence of external inputs. The execution may begin at any state and upon termination its output will be the current state of the automaton. Assume that at any point of the execution an adversary may appear (not knowing anything about the inputs so far) and decide to expose the entire memory of the agent. We say that a scheme to execute an automaton maintains state privacy if a single instance of such memory exposure does not reveal any information about the current state of the Automaton. We present a scheme based on Krohn-Rhodes decomposition that allows an unbounded execution for which the current state can be reconstructed only by the party that initially held the automaton. Our scheme maintains information-theoretic privacy and always returns a correct state as output. The scheme is then extended to the case of distributed execution by several agents that ensure that any qualified set of agents can reveal the current state of the automaton. Both the single agent and the distributed variants require communication only in the set-up and reconstruction phases, without any communication during the phase of automata execution.