Computing Without Learning: An Information-Theoretically Secure Multiparty Evaluation of Deterministic Pushdown Automata
Soumen Sarkar, Jaydeep Howlader
Multiparty computation allows a finite group of parties to jointly compute a known function of their combined inputs without revealing any individual’s input. This work presents a multiparty computation protocol for evaluating a private string on a deterministic pushdown automaton. The protocol takes as input both the automaton’s description and the string, and ensures that no party learns either the automaton or the string; they only learn whether the automaton accepts or rejects the string.This study emphasizes three main contributions. First, is it possible to compute a private function among a finite set of parties, where no party learns either the function or the inputs? We show that the answer is affirmative for computational models like pushdown automata. Second, our protocol provides a general framework for evaluating deterministic pushdown automata, thereby classifying a subclass of context-free languages that can be evaluated privately using multiparty computation. Finally, the proposed work is secure under the information-theoretic paradigm and inherently quantum safe.
IEEE Transactions on Computers•Sep 11, 2026•0 citations