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

International Journal of Information Security

Outsourced pattern matching

Sebastian Faust, Carmit Hazay, Daniele Venturi

Published May 2, 2017• 16 citations
Publisher
DOI
10.1007/s10207-017-0374-0

Related papers

Outsourced Pattern Matching

Sebastian Faust, Carmit Hazay, Daniele Venturi

Lecture notes in computer science•Jan 1, 2013•27 citations

Outsourced Pattern Matching.

Sebastian Faust, Carmit Hazay, Daniele Venturi

Abstract. In secure delegatable computation, computationally weak devices (or clients) wish to outsource their computation and data to an untrusted server in the cloud. While most earlier work considers the general question of how to securely outsource any computation to the cloud server, we focus on concrete and important functionalities and give the first protocol for the pattern matching problem in the cloud. Loosely speaking, this problem considers a text T that is outsourced to the cloud S by a client CT. In a query phase, clients C1,...,Cl runanefficientprotocol with the server S and the client CT in order to learn the positions at which a pattern of length m matches the text (and nothing beyond that). This is called the outsourced pattern matching problem and is highly motivated in the context of delegatable computing since it offers storage alternatives for massive databases that contain confidential data (e.g., health related data about patient history). Our constructions offer simulation-based security in the presence of semi-honest and malicious adversaries (in the random oracle model) and limit the communication in the query phase to O(m) bits plus the number of occurrences — which is optimal. In contrast to generic solutions for delegatable computation, our schemes do not rely on fully homomorphic encryption but instead uses novel ideas for solving pattern matching, based on efficiently solvable instances of the subset sum problem. 1

•Jan 1, 2014•0 citations

Error-correcting Codes

Franz Lemmermeyer

•Jan 1, 2005•1 citation

Error-Correcting Codes

P. Vijay Kumar

Springer eBooks•Jan 1, 1991•17 citations

Permutable Cut-and-Choose Oblivious Transfer and Its Application

Xiaochao Wei, Lin Xu, Hao Wang +1 more

Oblivious transfer (OT) is a significant primitive with wide use in secure two-party computation, private set intersection private and other cryptographic schemes. In the past ten years, different variants of OT primitive like cut-and-choose OT (CCOT) and outsourced OT (OOT), have been proposed so as to satisfy various emerging models. In this paper, we firstly propose and formalize a new primitive called permutable cut-and-choose OT (PCCOT) which generalizes the original CCOT functionality. Furthermore, we construct an efficient PCCOT protocol in the presence of malicious adversaries using the Decisional Diffie-Hellman (DDH) hard assumption. It is worth mentioning that we apply the PCCOT primitive to the efficient construction of secure wildcard pattern matching (WPM) protocol. The WPM functionality allows a party to determine the locations of its pattern with wildcard characters occurs in a long text of another party while revealing nothing to either party in addition to the length of their own inputs. Our proposed secure WPM protocol via PCCOT is secure against semi-honest adversary with 2 rounds and has identical communication cost as the the state-of-the-art scheme.

IEEE Access•Jan 1, 2020•5 citations

Quantum jumbled pattern matching

Julio Juárez-Xochitemol, Edgar Chávez

Let $S_1, S_2 \in Σ^*$ strings, we say that $S_1$ {\em jumble match} $S_2$ if they are permutations of each other. Given a text $T$ of size $N$ and a string $S \in Σ^*$, the problem of \emph{Jumbled Pattern Matching} (JPM) is to determine all substrings in $T$ jumbled matching $S$. In classical computing, a widespread conjecture is that JPM requires $Ω(N^{2-ε})$ preprocessing time and space for $O(1)$ query time, or $Ω(N^{1-δ})$ query time in the online version, with $ε, δ>0$. In this paper, we present a quantum algorithm for the online JPM in $O(\sqrt{N})$ time.

arXiv:2203.00164•Mar 1, 2022•2 citations
Abstract. In secure delegatable computation, computationally weak devices (or clients) wish to outsource their computation and data to an untrusted server in the cloud. While most earlier work considers the general question of how to securely outsource any computation to the cloud server, we focus on concrete and important functionalities and give the first protocol for the pattern matching problem in the cloud. Loosely speaking, this problem considers a text T that is outsourced to the cloud S by a client CT. In a query phase, clients C1,...,Cl runanefficientprotocol with the server S and the client CT in order to learn the positions at which a pattern of length m matches the text (and nothing beyond that). This is called the outsourced pattern matching problem and is highly motivated in the context of delegatable computing since it offers storage alternatives for massive databases that contain confidential data (e.g., health related data about patient history). Our constructions offer simulation-based security in the presence of semi-honest and malicious adversaries (in the random oracle model) and limit the communication in the query phase to O(m) bits plus the number of occurrences — which is optimal. In contrast to generic solutions for delegatable computation, our schemes do not rely on fully homomorphic encryption but instead uses novel ideas for solving pattern matching, based on efficiently solvable instances of the subset sum problem. 1
Oblivious transfer (OT) is a significant primitive with wide use in secure two-party computation, private set intersection private and other cryptographic schemes. In the past ten years, different variants of OT primitive like cut-and-choose OT (CCOT) and outsourced OT (OOT), have been proposed so as to satisfy various emerging models. In this paper, we firstly propose and formalize a new primitive called permutable cut-and-choose OT (PCCOT) which generalizes the original CCOT functionality. Furthermore, we construct an efficient PCCOT protocol in the presence of malicious adversaries using the Decisional Diffie-Hellman (DDH) hard assumption. It is worth mentioning that we apply the PCCOT primitive to the efficient construction of secure wildcard pattern matching (WPM) protocol. The WPM functionality allows a party to determine the locations of its pattern with wildcard characters occurs in a long text of another party while revealing nothing to either party in addition to the length of their own inputs. Our proposed secure WPM protocol via PCCOT is secure against semi-honest adversary with 2 rounds and has identical communication cost as the the state-of-the-art scheme.
Let S1,S2∈Σ∗S_1, S_2 \in Σ^*S1​,S2​∈Σ∗ strings, we say that S1S_1S1​ {\em jumble match} S2S_2S2​ if they are permutations of each other. Given a text TTT of size NNN and a string S∈Σ∗S \in Σ^*S∈Σ∗, the problem of \emph{Jumbled Pattern Matching} (JPM) is to determine all substrings in TTT jumbled matching SSS. In classical computing, a widespread conjecture is that JPM requires Ω(N2−ε)Ω(N^{2-ε})Ω(N2−ε) preprocessing time and space for O(1)O(1)O(1) query time, or Ω(N1−δ)Ω(N^{1-δ})Ω(N1−δ) query time in the online version, with ε,δ>0ε, δ>0ε,δ>0. In this paper, we present a quantum algorithm for the online JPM in O(N)O(\sqrt{N})O(N​) time.