International Association for Cryptologic Research

International Association
for Cryptologic Research


A Simple Obfuscation Scheme for Pattern-Matching with Wildcards

Allison Bishop
Lucas Kowalczyk
Tal Malkin
Valerio Pastro
Mariana Raykova
Kevin Shi
DOI: 10.1007/978-3-319-96878-0_25 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
Abstract: We give a simple and efficient method for obfuscating pattern matching with wildcards. In other words, we construct a way to check an input against a secret pattern, which is described in terms of prescribed values interspersed with unconstrained “wildcard” slots. As long as the support of the pattern is sufficiently sparse and the pattern itself is chosen from an appropriate distribution, we prove that a polynomial-time adversary cannot find a matching input, except with negligible probability. We rely upon the generic group heuristic (in a regular group, with no multilinearity). Previous work [9, 10, 32] provided less efficient constructions based on multilinear maps or LWE.
Video from CRYPTO 2018
  title={A Simple Obfuscation Scheme for Pattern-Matching with Wildcards},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  author={Allison Bishop and Lucas Kowalczyk and Tal Malkin and Valerio Pastro and Mariana Raykova and Kevin Shi},