# Round and Communication Balanced Protocols for Oblivious Evaluation of Finite State Machines

arXiv: https://arxiv.org/abs/2103.11240 · HTML: https://mlsanity.com/paper/2103.11240/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 37 references that are in the map.
- First posted on arXiv 20 Mar 2021.

## Builds on (most cited first, 12 of 12)

- [CrypTFlow2: Practical 2-Party Secure Inference](https://mlsanity.com/paper/2010.06457/) (2020)
- [CrypTFlow: Secure TensorFlow Inference](https://mlsanity.com/paper/1909.07814/) (2019)
- [XONN: XNOR-based Oblivious Deep Neural Network Inference](https://mlsanity.com/paper/1902.07342/) (2019)
- [QUOTIENT: Two-Party Secure Neural Network Training and Prediction](https://mlsanity.com/paper/1907.03372/) (2019)
- [Secure Evaluation of Quantized Neural Networks](https://mlsanity.com/paper/1910.12435/) (2019)
- [Protecting Privacy of Users in Brain-Computer Interface Applications](https://mlsanity.com/paper/1907.01586/) (2019)
- [Privacy-Preserving Feature Selection with Secure Multiparty Computation](https://mlsanity.com/paper/2102.03517/) (2021)
- [Privacy-Preserving Video Classification with Convolutional Neural Networks](https://mlsanity.com/paper/2102.03513/) (2021)
- [High Performance Logistic Regression for Privacy-Preserving Genome Analysis](https://mlsanity.com/paper/2002.05377/) (2020)
- [Privacy-Preserving Classification of Personal Text Messages with Secure Multi-Party Computation: An Application to Hate-Speech Detection](https://mlsanity.com/paper/1906.02325/) (2019)
- [Fast Privacy-Preserving Text Classification based on Secure Multiparty Computation](https://mlsanity.com/paper/2101.07365/) (2021)
- [Private Speech Classification with Secure Multiparty Computation](https://mlsanity.com/paper/2007.00253/) (2020)

## Abstract (arXiv)

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.