Paper 2019/056

Obfuscating simple functionalities from knowledge assumptions

Ward Beullens and Hoeteck Wee


This paper shows how to obfuscate several simple functionalities from a new Knowledge of OrthogonALity Assumption (KOALA) in cyclic groups which is shown to hold in the Generic Group Model. Specifically, we give simpler and stronger security proofs for obfuscation schemes for point functions, general-output point functions and pattern matching with wildcards. We also revisit the work of Bishop et al. (CRYPTO 2018) on obfuscating the pattern matching with wildcards functionality. We improve upon the construction and the analysis in several ways: - attacks and stronger guarantees: We show that the construction achieves virtual black-box security for a simulator that runs in time roughly $2^{n/2}$, as well as distributional security for larger classes of distributions. We give attacks that show that our results are tight. - weaker assumptions: We prove security under KOALA - better efficiency: We also provide a construction that outputs $n+1$ instead of 2n group elements. We obtain our results by first obfuscating a simpler "big subset functionality", for which we establish full virtual black-box security; this yields a simpler and more modular analysis for pattern matching. Finally, we extend our distinguishing attacks to a large class of simple linear-in-the-exponent schemes.

Available format(s)
Publication info
Published by the IACR in PKC 2019
ObfuscationVBBpattern matchinggeneric group
Contact author(s)
ward beullens @ esat kuleuven be
wee @ di ens fr
2019-01-25: received
Short URL
Creative Commons Attribution


      author = {Ward Beullens and Hoeteck Wee},
      title = {Obfuscating simple functionalities from knowledge assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2019/056},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.