Cryptology ePrint Archive: Report 2018/1222

Implementing Token-Based Obfuscation under (Ring) LWE

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

Abstract: 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.

Category / Keywords: implementation / implementation; lattice techniques; token-based program obfuscation

Original Publication (with major differences): WAHC 2020 – 8th Workshop on Encrypted Computing & Applied Homomorphic Cryptography

Date: received 20 Dec 2018, last revised 30 Nov 2020

Contact author: polyakov at njit edu

Available format(s): PDF | BibTeX Citation

Version: 20201201:031655 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]