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 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, ranging from special-purpose linear functions to general branching programs.

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 based on an exisiting construction for constrained-hiding constrained PRF, 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, including VBB and Indistinguishability Obfuscation.

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

Date: received 20 Dec 2018, last revised 12 Mar 2019

Contact author: polyakov at njit edu

Available format(s): PDF | BibTeX Citation

Version: 20190312:170033 (All versions of this report)

Short URL: ia.cr/2018/1222


[ Cryptology ePrint archive ]