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. as a potentially more practical alternative to conventional non-interactive security models, such as Virtual Black Box (VBB) and Indistinguishability Obfuscation. We implement in PALISADE several optimized TBO constructions based on (Ring) LWE covering a relatively broad spectrum of capabilities, ranging from special-purpose linear functions to general branching programs. To the best of our knowledge, these are first implementations of TBO constructions based on lattices.

The linear-function construction is first proposed in our work, and can be used to efficiently obfuscate binary classifiers by utilizing the token-based model where the number and format of queries can be restricted by the token generator. Our implementation can evaluate obfuscated binary classifiers in less than 1 millisecond and requires a program size of only 8MB for the case of 16 2-byte features. We also present an optimized TBO implementation for conjunctions, which outperforms the prior recent implementation of distributional VBB conjunction obfuscator by one order of magnitude and reduces the program size by a factor of 3. The token-based model also provides protection against exhaustive search attacks the VBB implementation is prone to. The last group of TBO constructions implemented in our work deals with obfuscating permutation and general branching programs.

To enable efficient implementation of all these constructions, we developed many algorithmic and code-level optimizations that can also be applied to other lattice-based cryptography primitives.

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

Date: received 20 Dec 2018

Contact author: polyakov at njit edu

Available format(s): PDF | BibTeX Citation

Version: 20181230:125214 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]