Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Secure Deterministic Automata Evaluation: Completeness and Efficient 2-party Protocols

Giovanni Di Crescenzo, Brian Coan, Jonathan Kirsch

Published Jan 1, 2020• 0 citations
Publisher
DOI
10.1007/978-3-030-41025-4_4

Related papers

Engineering Secure Two-Party Computation Protocols: Design, Optimization, and Applications of Efficient Secure Function Evaluation

Thomas H. Schneider

•Aug 4, 2012•25 citations

Engineering Secure Two-Party Computation Protocols: Design, Optimization, and Applications of Efficient Secure Function Evaluation

Thomas H. Schneider

Springer eBooks•Jan 1, 2012•12 citations

Automata Evaluation and Text Search Protocols with Simulation-Based Security

Rosario Gennaro, Carmit Hazay, Jeffrey S. Sorensen

Journal of Cryptology•Feb 11, 2015•6 citations

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

Privacy-Preserving Deterministic Automata Evaluation with Encrypted Data Blocks

Giovanni Di Crescenzo, Brian Coan, Jonathan Kirsch

Lecture notes in computer science•Jan 1, 2017•3 citations

A Zero-One Law for Deterministic 2-Party Secure Computation.

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

We use security in the Universal Composition framework as a means to study the “cryptographic complexity ” of 2-party secure computation tasks (functionalities). We say that a functionality F reduces to another functionality G if there is a UC-secure protocol for F using ideal access to G. This reduction is a natural and fine-grained way to compare the relative complexities of cryptographic tasks. There are two natural “extremes ” of complexity under the reduction: the trivial functionalities, which can be reduced to any other functionality; and the complete functionalities, to which any other functionality can be reduced. In this work we show that under a natural computational assumption (the existence of a protocol for oblivious transfer secure against semi-honest adversaries), there is a zero-one law for the cryptographic complexity of 2-party deterministic functionalities. Namely, every such functionality is either trivial or complete. No other qualitative distinctions exist among functionalities, under this computational assumption. While nearly all previous work classifying multi-party computation functionalities has been restricted to the case of secure function evaluation, our results are the first to consider completeness of arbitrary reactive functionalities, which receive input and give output repeatedly throughout several rounds of interaction. One important technical contribution in this work is to initiate the comprehensive study of the cryptographic properties of reactive functionalities. We model these functionalities as finite automata and develop an automata-theoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic non-triviality.

•Jan 1, 2010•1 citation
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.
We use security in the Universal Composition framework as a means to study the “cryptographic complexity ” of 2-party secure computation tasks (functionalities). We say that a functionality F reduces to another functionality G if there is a UC-secure protocol for F using ideal access to G. This reduction is a natural and fine-grained way to compare the relative complexities of cryptographic tasks. There are two natural “extremes ” of complexity under the reduction: the trivial functionalities, which can be reduced to any other functionality; and the complete functionalities, to which any other functionality can be reduced. In this work we show that under a natural computational assumption (the existence of a protocol for oblivious transfer secure against semi-honest adversaries), there is a zero-one law for the cryptographic complexity of 2-party deterministic functionalities. Namely, every such functionality is either trivial or complete. No other qualitative distinctions exist among functionalities, under this computational assumption. While nearly all previous work classifying multi-party computation functionalities has been restricted to the case of secure function evaluation, our results are the first to consider completeness of arbitrary reactive functionalities, which receive input and give output repeatedly throughout several rounds of interaction. One important technical contribution in this work is to initiate the comprehensive study of the cryptographic properties of reactive functionalities. We model these functionalities as finite automata and develop an automata-theoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic non-triviality.