slides

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 ProtocolBP-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

similar documents