International Association
for Cryptologic Research

The world of U.S. equities trading is highly competitive, involves many participants, and has significant global impact. Traders in this arena are responsible for overseeing the movement of billions of dollars, often on behalf of others, and thereby have a responsibility to develop reliable and well-performing trading strategies. “Controlling information leakage” is widely considered fundamental to high-quality, competitive trading strategies. In other words, good trading strategies maintain a level of privacy from an outside market observer. However important and highly valued this information leakage control property may seem, to our knowledge there exists no formal definition for this property in the context of equities trading strategies. Our work addresses this and creates a strong foundation for theoretical and practical work in this domain.

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.