Obfuscating Straight Line Arithmetic Programs∗Srivatsan NarayananDept. of Computer Scienceand EngineeringIndian Institute of [email protected] RaghunathanDept. of Computer Scienceand EngineeringIndian Institute of TechnologyMadrasananthr@cse.iitm.ac.inRamarathnamVenkatesanMicrosoft Research India,Bangalore and [email protected] Obfuscation that renders any given program essen-tially equivalent to a black box, while desirable, is impossible[4] in the general polynomial time adversary models. It isnatural to search for positive results under restricted pro-grams (e.g., point functions [20, 2], POBDDs[10], crypto-graphic primitives [17, 12, 13]). Here we study straight linearithmetic programs.Our model of obfuscation requires an attacker to producethe entire code only by looking at the obfuscated program.We show that obfuscation is possible, assuming factoring ishard and we have access to a tamper-resistant hardware (orsecure token). We also assume that the programs can besampled from some distribution. Our results are based onextending a result due to Shamir [19] on generation of hardto factor polynomials to straight line programs.Categories and Subject DescriptorsE.3 [Data Encryption]: Obfuscation of Polynomials; F.m [Theory of Computation]: MiscellaneousGeneral TermsAlgorithms, Security, TheoryKeywordsDRM, Hard-to-factor Polynomials, Obfuscation, Secure Hard-ware, Straight Line Arithmetic Programs, Software Protec-tion∗Part of this work was done at Microsoft Research India,Bangalore, where the first and the second authors were in-terns with the Cryptography, Security and Applied Mathe-matics research group.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.DRM’09, November 9, 2009, Chicago, Illinois, USA.Copyright 2009 ACM 978-1-60558-779-0/09/11 ...$10.00.1. INTRODUCTIONProgram obfuscation has become quite prevalent in prac-tice, often with weak security guarantees and performance,and they employ various heuristic techniques to defend againstknown attacks (for a survey see [6]). It would be useful tohave rigorous solutions that are secure against polynomialtime adversaries. If one requires a general purpose solutionthat is suitable for all programs, and a transformation thatrenders a given program essentially equivalent to a blackbox, then one suffers from a setback from the negative re-sult of Barak et. al [4]. Thus a natural approach is to lookat restricted class of attack models and programs (or prim-itives) that would admit useful positive results [17, 12, 13].In this vein we mention obfuscation of point functions in thestandard model [20] and Polynomial-sized Ordered BinaryDecision Diagrams (POBDDs) in the best possible obfus-cation model: in this model a given obfuscation is at leastas good as it gets, since no matter what the algorithm forobfuscation is used, one can infer the program in a canon-ical way [10]. To the question as to how auxiliary inputsaffect the possibility and scope of obfuscation, the reader isdirected to [8, 9].Here we consider straight line arithmetic program on manyvariables which is a large class, since they contain all multi-variate polynomials of possibly exponential degree, but thatcan be computed by a polynomially long straight line pro-gram. They have been studied in connection with modelingthe current attacks and reducibility to factoring from RSA[5].Thus given a straight line program (here on in denotedby slp) P let fP∈ R[x1, ..., xn] be the corresponding poly-nomial computed by it. We take the ring R = Z in thispaper, although our obfuscation methods use R = Fp. Allour functions will be represented by slps that run in poly-nomial time. Let O(P ) be the obfuscated version (where Odenotes the obfuscating algorithm). We ask the question:what can be learnt from O(P )? Based on Kaltofen’s results[15, 16], we observe that that we can always construct anequivalent slp Q (with at most a polynomial blow up) suchthat fQ= fP, if we can obtain the values at polynomiallymany random points.Next, assume that we have access to a secure “tamper-proof” piece of hardware referred to as the token. We allowour obfuscated program O(P ), while computing f, to querythe token a small only number of times—proportional to a47security parameter (rather than compute entire f with to-ken); this can allow oblivious execution [7]). Then we canask what can be gleaned from the obfuscated straight lineprogram O(P )?At this stage, we contrast our model with the early and im-portant model of software protection proposed in [7] wherethe authors assume the presence of a “protected” CPU thatruns programs obliviously. Our “tamper-proof” hardware(or token) serves the same purpose as the CPU, but with2 important differences. Firstly, it is stateless (i.e., it doesnot carry any information from one query to another). Thismodels a real world scenario with several (perhaps concur-rent) accesses by different obfuscated programs to a centralsecure or protected token. Secondly, the CPU in [7] initiatesand drives the execution of the program, but in our case, weassume that the execution and computation is done by theuser. The token is queried minimally, and does not requirethe token to initiate the execution.1.1 Attack scenariosWe distinguish three types of attacks:1. Program-Only attacks: Here, the adversary sees theO(P ) but does not have access to T .2. Token access with equality testing: The attacker hasoracle access to T , but the outputs are encrypted usingsemantically secure public key encryption that allowsequality testing. This comes naturally in encryptedsearching which is along the lines of remote executionexcept that we use Enc(P (x)) to search an encryptedstream for the occurrences of P (x) [18].3. Token access without equality testing: The attackeronce again has oracle access to the token T , but theencryption is probabilistic, and equality testing is notallowed. This scenario naturally arises when a remotemachine given x (such as a registration key) must runOT(P ) to obtain Enc(P (x)) and send the result to acentral server.With regard to an adversary