Paper 2018/210

A Simple Obfuscation Scheme for Pattern-Matching with Wildcards

Allison Bishop, Lucas Kowalczyk, Tal Malkin, Valerio Pastro, Mariana Raykova, and Kevin Shi

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 provided less efficient constructions based on multilinear maps or LWE.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
obfuscationgeneric groupvirtual black box
Contact author(s)
luke @ cs columbia edu
History
2018-06-04: last of 2 revisions
2018-02-26: received
See all versions
Short URL
https://ia.cr/2018/210
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/210,
      author = {Allison Bishop and Lucas Kowalczyk and Tal Malkin and Valerio Pastro and Mariana Raykova and Kevin Shi},
      title = {A Simple Obfuscation Scheme for Pattern-Matching with Wildcards},
      howpublished = {Cryptology ePrint Archive, Paper 2018/210},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/210}},
      url = {https://eprint.iacr.org/2018/210}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.