Report

Multilinear Maps and Obfuscation A Survey of Recent Results Shai Halevi – IBM Research PKC 2014 Prologue We are in the midst of (yet another) “quantum leap” in our cryptographic capabilities Things that were science fiction just two years ago are now plausible General-purpose functional encryption Crypto-strength code obfuscation … Fueled by new powerful building blocks Combination of Homomorphic Encryption (HE) and Cryptographic Multilinear Maps (MMAPs) This Talk Overview of the main new tool Constructing MMAPs using “HE techniques” And application to obfuscation There are many others Witness Encryption Full-Domain Hash Functional Encryption not today … Chapter One: Multilinear Maps Starting Point: DL-based Crypto “The DDH assumption is a gold mine” -- Boneh ‘98 Why is it so useful? Can “hide” values in Some tasks are still easy in this representation Compute any linear/affine function of the ’s Check if = 0 Other tasks are seemingly hard E.g., computing/checking quadratic functions (CDH/DDH) Starting Point: DL-based Crypto To use DH in applications, ensure that: legitimate parties only compute linear functions adversary needs to compute/check quadratics Some examples: Diffie-Hellman key exchange, ElGamal Encryption, Cramer-Shoup CCA-Secure Encryption, Naor-Reingold PRF, Efficient ZKPs, … Beyond DDH: Bilinear Maps [J00,SOK00,BF01] In bilinear-map groups you can compute quadratic functions in the exponent But computing/checking cubics is hard Now the legitimate parties can do a lot more Leads to new capabilities Identity-based encryption (IBE) Predicate encryption (for simple predicates) Efficient non-interactive zero-knowledge proofs … Why Stop at Two? Can we find groups that would let us compute cubics but not 4th powers? Or in general, upto degree but no more? Cryptographic multilinear maps (MMAPs) Even more useful than bilinear [BS’03] explored applications of MMAPs Also argued that they are unlikely to be constructed similarly to bilinear maps The [GGH’13] Approach to MMAPs Construct MMAPs from “HE techniques” By modifying the an existing HE scheme Recall “somewhat homomorphic” enc.(SWHE) Public-key encryption with usual (KeyGen,Enc,Dec) An additional procedure ′ ← Eval (, ) = (1 , … , ) encrypts = (1 , … , ) P is a low-degree polynomial ′ encrypts ′ = () This looks a little like what we want MMAPs vs. SWHE MMAPs SWHE “Encoding” = Encrypting c = E() Computing low-deg polynomials of the ’s is easy Computing low-deg polynomials of the ’s is easy Can test for zero Cannot test anything • But if you have skey you can recover itself Main Ingredient: Testing for Zero To be useful, must be able to test if two degree- expressions are equal Using homomorphism, that’s the same as testing if a degree- expression equals zero Our approach: augment a SWHE scheme with a “handicapped” secret key Can test if a ciphertext decrypts to zero, but cannot decrypt arbitrary cipehrtexts Assuming that the plaintext-space is large Called a “zero-test parameter” Bird-Eye View of [GGH’13] Start from the NTRU HE scheme NTRU ciphertexts naturally come in “levels” A level- cipehrtext encrypts degree- expression Modify NTRU to obscure the plaintext space Instead of /3 we use / for a secret Needed for security when publishing the “handicapped secret key” Publish a “shifted” level- secret key Can identify level- encryption of zero, not decrypt Another scheme along similar lines in [CLT’13] Graded Encoding Schemes Instance generation: , ← (1 , 1 ) Plaintext space implicit in , isomorphic to some Secret-key encoding: ← (, , ) is a level- encoding of is randomized Addition and multiplication + ← ⊞ , + = max , ⋅ ← ⊠ , ⋅ = + Zero-Test: use to check if a level- encoding encodes 0 Some Variants Optional public encoding: (, ) ← P(p) is uniform, is a level-1 encoding of Optional re-randomize: ′ ← (, ) ′ , encode the same element Distribution of ′ depends on , but not on Some instantiations come with security vulnerabilities An “asymmetric” variant Instead of levels 1,2, … , , encodings associated with subsets of = {1,2, … , } Can only multiply encodings relative to disjoint subsets Zero-test for encodings relative to itself Hardness Assumptions An “über-assumption” for graded-encodings: For any collection of encodings 1 , … , (at any level) is an encoding of some plaintext and polynomial (1 , … , ) of degree > Computation: Hard to compute a level-≤ encoding of (1 , … , ) when the are uniform Decision: Hard to distinguish if the are uniform, or chosen as a random root of An even more general assumption in [PST’14] Dubbed “Semantically-Secure Graded Encodings” A Few Words About Performance Currently mostly a plausibility argument “Somewhat practical” multilinearity for a small constant Best reported implementation in [CLT’13] 6-linear scheme with size ~ 2.5 GB, operations in less than one minute Quite aggressive choice of the security parameter Main road-block: obscured plaintext space Rules out all the optimizations that we have for FHE Leaves us with something similar to Gentry’s original 2009 scheme Take-Home from Chapter One MMAPs are similar to DL-based crypto Can compute “in the exponent” polynomials of deg ≤ But not degree + 1 or more Can be devised using “HE techniques” One difference: need sk to “exponentiate” There are variants without this limitation, but they have other shortcoming Chapter Two: Obfuscation Code Obfuscation Encrypting programs, maintaining functionality Only the functionality should be “visible” in the output Example of recreational obfuscation: @P=split//,".URRUU\c8R";@d=split//,"\nrekcah xinU / lreP rehtona tsuJ";sub p{ @p{"r$p","u$p"}=(P,P);pipe"r$p","u$p";++$p;($q*=2)+ =$f=!fork;map{$P=$P[$f^ord ($p{$_})&6];$p{$_}=/ ^$P/ix?$P:close$_}keys%p}p;p;p;p;p;map{$p{$_}=~/^[P .]/&& close$_}%p;wait until$?;map{/^r/&&<$_>}%p;$_=$d[$q];sleep rand(2)if/\S/;print -- Wikipedia, accessed Oct-2013 Rigorous treatment [Hada’00, BGIRSVY’01,…] Why Obfuscation? Hiding secrets in software Plaintext strutpatent.com AES encryption Ciphertext Why Obfuscation? Hiding secrets in software Plaintext @P=split//,".URRUU\c8R";@d=split//,"\nrekcah xinU / lreP rehtona tsuJ";sub p{ @p{"r$p","u$p"}=(P,P);pipe"r$p","u$p";++$p;($q* =2)+=$f=!fork;map{$P=$P[$f^ord ($p{$_})&6];$p{$_}=/ ^$P/ix?$P:close$_}keys%p}p;p;p;p;p;map{$p{$_}= ~/^[P.]/&& close$_}%p;wait until$?;map{/^r/&&<$_>}%p;$_=$d[$q];sleep rand(2)if/\S/;print Ciphertext AES encryption Public-key encryption Why Obfuscation? Hiding secrets in software http://www.arco-iris.com/George/images/game_of_go.jpg Game of Go Next move Uploading my expertise to the web Why Obfuscation? Hiding secrets in software Game of Go @P=split//,".URRUU\c8R";@d=split//,"\nrekcah xinU / lreP rehtona tsuJ";sub p{ @p{"r$p","u$p"}=(P,P);pipe"r$p","u$p";++$p;($q*=2)+=$ f=!fork;map{$P=$P[$f^ord ($p{$_})&6];$p{$_}=/ ^$P/ix?$P:close$_}keys%p}p;p;p;p;p;map{$p{$_}=~/^[P.]/ && close$_}%p;wait until$?;map{/^r/&&<$_>}%p;$_=$d[$q];sleep rand(2)if/\S/;print Next move Uploading my expertise to the web without revealing my strategies Defining Obfuscation Want the output to reveal only functionality E.g., If prog. depends on secrets that are not readily apparent in I/O, then the encrypted program does not reveal these secrets [B+01] show that this is impossible in general Thm: If secure encryption exists, then there are secure encryption schemes for which it is possible to recover the secret key from any program that encrypts. Such encryption schemes are unobfuscatable Defining Obfuscation Okay, some function are bad, but can we do “as well as possible” on every given function? [B+01] suggested the weaker notion of “indistinguishability obfuscation” (iO) Gives the “best-possible” guarantee [GR07] It turns out to suffice for many applications (examples in [GGH+13, SW13,…]) Defining Obfuscation [B+01] An efficient public procedure OBF(*) Takes as input a program E.g., encoded as a circuit Produce as output another program ′ ′ computes the same function as ′ at most polynomially larger than Indistinguishability-Obfuscation (iO) If 1 , 2 compute the same function (and |1 | = |2 |), then 1 ≈ 2 Obfuscation vs. HE F Encryption F + x F Obfuscation or x F(x) Result encrypted F + x F(x) Result in the clear Somewhat reminiscent of MMAPs vs. HE… Obfuscation from MMAPs, 1st Try MMAPs give us one function that we can get in the clear: equality-to-zero (at level ) Can we build on it to get more functions? Consider the “universal circuit” ′ : , × , → , , , = () Encode the bits of at level 1 For , provide level-1 encoding of both 0 and 1 Carry out the computation “in the exponent” Use zero-test to check if the result is zero 1st Try Does Not Work Attack: comparing intermediate values Checking if two intermediate wires carry same value Checking if the computation on two different inputs yield the same value on some intermediate wire If two equal intermediate values ever happen, they can be recognized using zero-test Must randomize all intermediate values in all the computations But such that the final result can still be recognized Construction Outline Describe Circuits as Branching Programs (BPs) using Barrington’s theorem [B86] Randomized BPs (RBPs) a-la-Kilian [K88] Additional randomization to counter “simple relations” Encode RBPs “in the exponent” using MMAPs Use zero-test to get the output This allows obfuscating shallow circuits (NC1) Another transformation (using FHE) to get all circuits (Oblivious) Branching Programs A specific way of describing a function This length-9 BP has 4-bit inputs A1,0 A2,0 A3,0 A4,0 A5,0 A6,0 A7,0 A8,0 A9,0 A1,1 A2,1 A3,1 A4,1 A5,1 A6,1 A7,1 A8,1 A9,1 0 The , ’s are square matrices Each position is controlled by one input bit (Oblivious) Branching Programs A specific way of describing a function This length-9 BP has 4-bit inputs A1,0 A2,0 A3,0 A4,0 A5,0 A6,0 A7,0 A8,0 A9,0 A1,1 A2,1 A3,1 A4,1 A5,1 A6,1 A7,1 A8,1 A9,1 0 1 (Oblivious) Branching Programs A specific way of describing a function This length-9 BP has 4-bit inputs A1,0 A2,0 A3,0 A4,0 A5,0 A6,0 A7,0 A8,0 A9,0 A1,1 A2,1 A3,1 A4,1 A5,1 A6,1 A7,1 A8,1 A9,1 0 1 1 0 Multiply the chosen 9 matrices together If product is output 1. Otherwise output 0. (Oblivious) Branching Programs A specific way of describing a function Length- BP with -bit input is a sequence 1 , 1,0 , 1,1 , 2 , 2,0 , 2,1 , … , ( , ,0 , ,1 ) ∈ {1, … , } are indexes, , ’s are matrices Input = (1 , … , ) chooses matrices , Compute the product = =1 , = 1 if = , else = 0 Barrington’s Theorem [B86]: Poly-length BPs can compute any function in NC1 Kilian’s Randomized BPs B1,0 A1,0 1 A1,1 B1,1 1−1 B2,0 B3,0 B4,0 B5,0 A2,0 A3,0 A4,0 A5,0 2 2−1 3 3−1 4 4−1 B6,0 5 A2,1 A3,1 A4,1 A5,1 B2,1 B3,1 B4,1 B5,1 5−1 A6,0 A6,1 B6,1 Choose random invertible matrices −1 , = −1 × , × (with 0 = +1 = ) Multiplying the B, ’s yields the same product as multiplying the corresponding A, ’s Kilian’s Randomized BPs B1,0 A1,0 1 A1,1 B1,1 1−1 B2,0 B3,0 B4,0 B5,0 A2,0 A3,0 A4,0 A5,0 2 2−1 3 3−1 4 4−1 B6,0 5 A2,1 A3,1 A4,1 A5,1 B2,1 B3,1 B4,1 B5,1 Each sequence of B, ’s ( = 1 … ) is uniformly random subject to having same product as A, ’s 5−1 A6,0 A6,1 B6,1 Kilian’s ProtocolBP-Obfuscation? Encode RBP for (, ) with the part fixed Publish only one , for the bits of , both , ’s for Can evaluates (, ) for any . “Simple relations” exist between the , ’s Since we give both , ’s for some ’s Enable some attacks “Partial-evaluation” attacks: Compare partial products across different evaluations “Mixed-Input” attacks: Compute products that do not respect the BP structure Countering “Simple Relations” Additional randomization steps Different works use slightly different forms of additional randomization “Multiplicative bundling” [GGHRHS’13, BR’13] “Straddling” [BGKPS’13, PTS’14] “Abelian component” [CV’13] Can conjecture [GGHRHS’13, BR’13] or prove [BGKPS’13, CV’13, PTS’14] that no simple relations exist Completing the construction Put randomized matrices “in the exponent” Set multi-linearity parameter to Encode all elements at level 1 Publish one matrix for the bits of , both for To compute () Choose the encoded matrices corresponding to Multiply matrices “in the exponent” using ⊞,⊠ Use zero-test to check if the result is the identity Security of Obfuscation No polynomial relation of degree ≤ , except those that involve the output matrix Output relations are the same when we obfuscate two circuits with identical functionality By (generalized) über-assumption, the two distributions over encodings are indistinguishable Mission Accomplished A Word About Performance Needs -linear maps for in the thousands Need I say more? Take-Home from Chapter Two We can obfuscate a computation by: 1. Randomizing the internal values 2. Putting the randomized values “in the exponent” and computing on them using MMAPs Future Directions We only have two MMAPs candidates, and just one approach for using them in obfuscation Hard to develop a theory from so few sample points We need better formal notions of obfuscation Current notions (such as iO) do not capture our intuition, not even for what the current constructions achieve Faster constructions Complexity of current constructions is scary Applications Already have a bunch, the sky is the limit… Thank You Questions? Witness Encryption [GGSW’13] A truly “keyless encryption” Can encrypt relative to any arbitrary “riddle” Defined here relative to exact-cover (XC) XC is NP-complete, so we can translate any “riddle” to it Recall Exact Cover Instance: universe [] and a collection of subsets ⊂ [], = 1, … , 1 2 {1,2,3} {2,4,5} 3 4 {1,4} 5 {2,3,5} A solution: sub-collection of the ’s that covers every element of [] exactly once Witness Encryption Message encrypted wrt to XC instance Encryptor need not know a solution Or even if a solution exists Anyone with a solution can decrypt Secrecy ensured if no solution exists {1,2,3} 1 2 {2,4,5} {1,2,3} 1 2 {2,4,5} 3 3 4 {1,4} 4 5 {2,3,5} 5 Decryptable {1,4} {2,3,4,5} Secret Witness Encryption Using MMAPs Choose random for element Product = ∈ for subset Publish encoding = | | ( ) Product of everything p∗ = ∈[] Use encoding ∗ = (∗ ) to hide message 1 2 3 4 5 1 2 {1,2,3} 1 = 3 (1 ⋅ 2 ⋅ 3 ) {2,4,5} 2 = 3 (2 ⋅ 4 ⋅ 5 ) 3 4 {1,4} 5 {2,3,5} 3 ⊠ 4 ≈ ∗ 3 = 2 (1 ⋅ 4 ) 4 = 3 (2 ⋅ 3 ⋅ 5 ) ∗ = 5 (1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ) ctxt = (1 , … , 4 , ∗ ⊕ ) Witness Encryption Using MMAPs Encrypt(message M, instance (, 1 , … , )) Set , ← (1 , 1 ), choose ← ∀ Compute = ∈ ∀ , and p∗ = ∈[] Encode ← (, , ), ∗ ← , ∗ , Use ∗ to hide message, ∗ ← , ∗ ⊕ Ciphertext is (pp, 1 , … , , ∗ ) Decrypt(cover , ciphertext (pp, 1 , … , , ∗ )) Multiply encodings in cover ←⊠∈ Use to unmask message, ← ∗ ⊕ , Security of Witness Encryption If no exact cover, then no polynomial relation of degree ≤ between ∗ and the ′ For some no-instances, ∗ is uniform even given ′ For others there is a relation,* but of degree > By über-assumption, ∗ is indistinguishable from encoding of a uniform element If ∗ was an encoding of a uniform element, then , ∗ was a uniform bit string * There could be many such relations, need to generalize über-assumption