Paper 2018/1222

Implementing Token-Based Obfuscation under (Ring) LWE

Cheng Chen, Nicholas Genise, Daniele Micciancio, Yuriy Polyakov, and Kurt Rohloff


Token-based obfuscation (TBO) is an interactive approach to cryptographic program obfuscation that was proposed by Goldwasser et al. (STOC 2013) as a potentially more practical alternative to conventional non-interactive security models, such as Virtual Black Box (VBB) and Indistinguishability Obfuscation. We introduce a query-revealing variant of TBO, and implement in PALISADE several optimized query-revealing TBO constructions based on (Ring) LWE covering a relatively broad spectrum of capabilities: linear functions, conjunctions, and branching programs. Our main focus is the obfuscation of general branching programs, which are asymptotically more efficient and expressive than permutation branching programs traditionally considered in program obfuscation studies. Our work implements read-once branching programs that are significantly more advanced than those implemented by Halevi et al. (ACM CCS 2017), and achieves program evaluation runtimes that are two orders of magnitude smaller. Our implementation introduces many algorithmic and code-level optimizations, as compared to the original theoretical construction proposed by Chen et al. (CRYPTO 2018). These include new trapdoor sampling algorithms for matrices of ring elements, extension of the original LWE construction to Ring LWE (with a hardness proof for non-uniform Ring LWE), asymptotically and practically faster token generation procedure, Residue Number System procedures for fast large integer arithmetic, and others. We also present efficient implementations for TBO of conjunction programs and linear functions, which significantly outperform prior implementations of these obfuscation capabilities, e.g., our conjunction obfuscation implementation is one order of magnitude faster than the VBB implementation by Cousins et al. (IEEE S&P 2018). We also provide an example where linear function TBO is used for classifying an ovarian cancer data set. All implementations done as part of this work are packaged in a TBO toolkit that is made publicly available.

Available format(s)
Publication info
Published elsewhere. Major revision. WAHC 2020 – 8th Workshop on Encrypted Computing & Applied Homomorphic Cryptography
implementationlattice techniquestoken-based program obfuscation
Contact author(s)
polyakov @ njit edu
2020-12-01: last of 6 revisions
2018-12-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Cheng Chen and Nicholas Genise and Daniele Micciancio and Yuriy Polyakov and Kurt Rohloff},
      title = {Implementing Token-Based Obfuscation under (Ring) LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1222},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.