ࡱ> `!k=F=[/&[5%89xEPJA}INcF JD!+b vil|MJ"?`'B<]xaf{0€&51ָ*f \e("L$~yr>4an"o/*adF#;IFS$\\` !2{_*#W{urߊ{_s)3Wuz ^LG'D]8hn'uF.+⡉7ڤ*f!MtpʹE#Kn`!<"I}?km%A0Q9kF "xҰg잝9K HV*9"$G,% `VLFQ@$ٝr{}9SUZPAQ+Zź/:v5VƩ{|/5d 0M\ +#nt!ys I vg\}9lu+q[WX7zXQ(&1"Lݮ.vMwgdq8=(LdnȜ?Sp*u[3vwj 1['*R)HJ&%JR\E2 7Å##ãc9rƖbigϾ le(uߵ­]OARw;_YNut +As1J+S,rFHL*w. m2)_uj埯ri.Bm,5OExWC&d\3{U(e;/>v(BR~+zn;ձ\LG[V,oxIo R1W3>m$G36(ANJt6Q>XPԈj+W#9n`oxIE%R˜,\j 5Ib'U-ov)ڡl7F)fz3`j\i7[kͽ\~nm0X \k9Zc1ZK͑bs MfiY35ԭgkn^Y." 7' 1kVAfqeFO=܊י%Ü\c/s 61` -2f} [Y~{^#f 7.d]gF*7{Fwi`O; 6>U1/cYc q?gm."f~7q~QQ^ũ1s^I5z)*'3ҋ d%TToEIzJP},uczh ѿA\)l -r~~(b|FllRjδ2^vOC'i"3Naњ3~2a3ce.]4VQ_o4f%Lb*ZY*de9*g._XUCV3ӵ5KD5#vfXsX$|Eg_uqOY:aũVзЙxK L̻@>ee)SO[=mzWS H3{qc  ˥٥ܙ\}rٟ̼;/z_ÜWnk~:Pu0a&a]~أ SD\l)¥~a7u&"wf_ -;3sgzIx#f,!5rA/K+]d6wV B?a$j [NvΝs1.5vs$^2c~ sr$sGz.;tϥgf6Erit1(\TΨfŭ rk&N/c4STSߟKoak%d8: knN% z\}>SsI ^9d?m51\[B\z\ԏsiF7e^H 볏;W5>'4vwe3j`KHxGWsc1sSٔmϥ-C܊<;=dNtȭ3Nj"9-ʟzcy嘮YuպL sHXv[D-1og;)OL']9 JcNб5:ʾ+OL]Nuӭ"2(2(2 QſG)eRF-^~fʨn6l,)2 *2**2J*2j*2*2zOhǢ2+2:+2Z+2z+2+2+2+RُBwz1 əe]Fe$^Fz{|ї}ᗑ~!1AQaq-0/2b )s9tIuYviwygg,u0f\YRdNEVdEZdE^dFbdNFfdFjdFndGrdNGvdGzdG~d\qKdHdQ̎\|=7*rd~4F38q9"įU}c6efH5GN"?syt"GL>nc70q /6S͈= "ˑYKB^wb, 2 2 2!2/!2O!2o[V,!2!;?dDCd^DGdDKdD Gwۿv{"VE^D DEnE[L3?lۢOvY1NCŋ|]J,ˉv}ڵ6>n4Gcw4qWb/Q?hƴz'.;%i#E'b<8IH&&ULL|Q<,J1q[$| tFTI,R1QQ7MBpB$>IYN"R1xf(eR:N@U./'>+NL2$[#ě,Ďb^b+LbS1>DtO,)Z1 p,Is|\`g.q|mwpޜך4{ٕOg|#vZN[HTJuBQ꟭po;L1)Gkii0\0IOk` jbm%5Gvh`j\އ[kZPh Mǡrh0T P# T  ! JT(Du/tYءBNpPBG(~վ~qJ+h~mH#Vjƅ4Cb$tNc1,KbrhV }Coc+xWhV ҡG0нhV/h)x\ V0d|ۖs"3)Zc1Z֧ zn6R;܀ؿ4Zl/.{_q-2]",nӂ ;8, 'Ddhh2AYԀ'BVc` >I L +54$D=4R.DFPU)#Nt4B?ho0 &`&}DŴ2x Vђ#Z|L/hj~1A&T>)o%u÷~uom Yk"R_ܚʌ0_}xL[ o'ZªV]aj)US?*߆*u(/T?-X$LWCEs7TCeT/@4=ܿ)Z7CuUtnbI/qD?CL/L<}>mp? G}?O+0O60ނZYA?Du;~*ܮ-)>hAFД hLyT$AJT1(CՂ"T3KA7ep  vCF._$l:AS*A2 cɀpb:Pp uP+4,Tjy'E#g zpoHvi.1,W=b+b Ql/bwZΉ/YաpVk(5RBP+sjgg.1WP'ecͬSbaX2kZPڈJz{1;g_wzuϼ1Zoy.e^p/ٞBx=xOcE=D^>j姆LW 멄<w}pew+uWqw rgwu[p- d~u*h^0H"eQֻ R!k Q\΁>z{EqWGx/^)^:&ޓ8כ l7鋋4.1u52S` t^oLzBF{A$e˙YBWyDquwEuhΤ2mGt㾞>_= bzDLQOi1K='P_#:.!S=Ŝ+ysWUfΏPY+P!uS{C݁kԽz":$1Ţv)*}Dqr7(pQ2e5,l|N3'()8VqrF*a .Sy0@*$9;C(ѡ8at#:~(Cc)#:NF_#эct?fpI}t.Z8ˉ&X!Ǵ :d8V')d sZӜB)gmw*XEUnU߭jgҸއ}#f[z ;whE M컿b 3)X3ҴDB+طok:w;Y_Kkkvފ}6Z1ꤕG_EõOOiMyghMM1zm1۴VhUJIE͢+N5Na| Zo?kxRW}ODKuZW|[넯hٷ38!3hY(3oa!X嫰W`[|_lc.n;ml8]A}HC=4 zA`$ :| ,H]A],<lcOx8b3 f;m `< f\z#XF4?Hϳ_?')=FiPA}g -3(o~_o`mYoͬS~+kȤrSO⾊<* $E~5 `tߴHA"'Svvn&/;ٗF}2Av+FÿO<~E(䗃~Y(闁~)藄~ ɶ~QhT_:+L/F*'*~\?+p7aW` ~}}eҘ~?ܗN'mcxqtGQH^tJ~; HԤA9*YgD +٧E0A?T-/^  O>IvgO-/!P3:^{*<= )0= &{qgR//M^5c]&jvg]#+Y*eJ2eQd%3n>}gB5x[x ygq߰3ikW{54ꕡ^Y땣癿ziM)ݫHa^%U^ Uw5!65=^5J^c*5^3k^#r֡n5:斧nZgn&nr:w't7ܝi8M8˵~ϹEw.,p'w vUnK[zí ߹[[.e-rz:ٛe˭P;8%c-/e?7[y󰵷;x#J*콋ü8[ȼ#Ya(5ӌ ">^Go3{Sc2IrnSapH1 Wd_fS)U*sS>5 MTR:6ܮd2%TfRiEgpWkM |U gq6O*MPM& USZZکead~Sn"0j%*Vj U)z5HWkSԧJ4SJc:4J3|J#Z*uhR)iRX4UQ %(Gq(.)2 [+iR* <V]C )-arSd&LWsJeהR (@x8LtYy(˸ ǕpJJ2f*xS2yhKRJ,R*,r.d^J,f VV0ӚizCuD|vfN$ez߯:bfq&SmI[oӇѯiu, YE [G[+ejֶh h-h]+#z: NSI:9[5dt>uZny'$UYn7ՂIuZ3mn궳܇nkbuY\{}_h{=5Mvxw Mod?#׳uRWw Pkw59]I+>vߣ ;T}luݥ)yg!Eyn:ӓ;͙_(^u1W33L=0^vs .;!I+΃LQN8Xp1ᰓx`·b㋭Gܶ}e?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>> `X(    6 P  N       ( (j  0콬                  )     T2  0Ĭ ` ` H@___PPT9"@ j*    0dȬ `   V* .  0ά ``` H@___PPT9"@ f*"H  0޽h ? ̙33    4 0 D(    N 0k0k  5$    r*  J%%JJoop  N|0k0k u$`  H@___PPT9"@ *"   J%%JJood  c $ ?PF     Nl0k0k  K                  )     T  T, 0k0k  5    r*  J%%JJoor  TT 0k0k u`  H@___PPT9"@ *"  J%%JJooH  0j ? ̙3380___PPT10.N Ļ `X(     NU0k0k u$   t*  J%%JJoo  N<`0k0k  5$  ~*   J%%JJoo  Tc0k0k u   t*  J%%JJoor  Thu0k0k  5` H@___PPT9"@ *    J%%JJooH  0j ? ̙3380___PPT10.Ṋ. UM0(  r  S 0  r  S XP0     0) & YiJoint work with Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan and Ke Yang.j ja                  H  0޽h ? ̙33y___PPT10Y+D=' = @B +!  H@@ (     0`r 8  jAn obfuscator: An algorithm O such that for any program P , O(P) is a program such that: O(P) has the same functionality as P O(P) is infeasible to analyze /  reverse-engineer .Z( 2\( 2a aaaaaaaaaaa/aa   0D  ,$  0 FIntuition: an obfuscator should provide a  virtual black-box in the sense that giving someone O(P) should be equivalent to giving her a black-box that computes P.( 2 a aa"aa>aaa   S <$  0   nWhat Is an Obfuscator? g$PP H  0޽h ? ̙33y___PPT10Y+D=' = @B + P(    S    rWhy Might Obfuscators Exist?g$PP   0`e Practical Reasons: Understanding code is very difficult Obfuscation used (successfully?) in practice for security purposes Theoretical Reasons: All canonical hard problems are problems of reverse engineering: SAT, HALTING Rice s Theorem: You can t look at the code (Turing Machine description) of a function and find out a non-trivial property of it.( 2h( 2( 2( 2ahaaBa asa_ H  0޽h ? ̙33p  `(    S    rApplications for Obfuscatorsg$PP   0  8Distributing music on-line Removing Random Oracles for specific natural protocols. Converting a private key encryption to a public key encryption Give someone ability to sign/decrypt a restricted subset of the message space. ( 2a H  0޽h ? ̙33J  C;p%$ (  $T $ S h   nPrivate (Shared) Key Encryption Public Key EncryptionH8 g$PP$PPg$PP7 8   $ $ 00 EkH( 2c,k,c, `B $ 0D  $ 0`@ Um(2a `B $ 0D    $ 0 P DkH( 2c,k,c, `B  $ 0D   $ 0\   Uc(2a   $ 0 Um(2a  $ 0 @ vPrivate Key Encryption Scheme: ( 2a 1 $ 0L ,$D 0 'CPA (Chosen Plaintext Attack) Security:>(( 2aa a' al   %$ ,$D 0`B !$B 0Dfp  $ 60   EkH( 2c,k,c,  $ 6  [A"( 2c, fB $ 6Dp p fB $B 6Dp P fB $ 6Dp $ 6P @ Wc( 2a fB $ 6Dpp   $ 6` @@ Wm( 2a `B #$ 0Df H $ 0޽h ? ̙33___PPT10+=ZFD3' = @B D' = @BA?%,( < +O%,( < +D%' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*$%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%$%(+8+0+$ +4 `(  F   `0F  0T0 EeH( 2c,k,c, `B  0D   0 `@ Um(2a `B  0D     0 P DdH( 2c,k,c, `B  0D    0L   Uc(2a    0< Um(2a   0 uPublic Key Encryption Scheme: ( 2a   0#`@,$D 0 a Security: ( 2 a  l  0f   0f ,$D 0  6P(   [e"( 2c,   6!@ f  [A"( 2c, fB B 6Dp  P fB  6Dp    60@   Wc( 2a fB  6Dp 0   63 p  Wm( 2a Dl    ,$D 0`B B 0Df `B  0Df0 P H  0޽h ? ̙33C;___PPT10+޴[D' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(+8+0+  +   (~(  ( ( S XB   dThe Conversiong$PP l p   (   ,$D 0 ( 6HF @  E eH( 2c,k,c, fB ( 6D p    ( 60L   Um(2a fB  ( 6D `   ( 64I   D dH( 2c,k,c, fB  ( 6D P    ( 6U p   Uc(2a  ( 6lY `  Um(2a Q ( 0L]`p 1Instead of publishing the key k, publish e=O(Ek) n2( 2aa aaia.-   H ( 0޽h ? ̙33___PPT10~+Db' = @B D' = @BA?%,( < +O%,( < +DT' =%(%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*(%(+   , F (  , , S m`   v Security of The Converted Scheme!!g$PP  l   ,  ,$D 0 , 6qP   EkH( 2c,k,c,  , 6vp   [A"( 2c, fB , 6Dp p fB ,B 6Dpp P fB , 6Dp , 6{p P@ Wc( 2a fB , 6Dp ` , 60 @ Wm( 2a 8  ,P , 6$  ^A "( 2c, fB , 6DpP  , 6  Wc( 2a fB  , 6Dp@   , 6|0  Wm( 2a `B , 0Dp  ` , 0  e=O(Ek)B( 2aia.   B , 0D@ ,$D 0H , 0޽h ? ̙33jb___PPT10B+X'D&' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*,%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*,%(+ 0R(  0 0 S HX @`   jDefining Obfuscatorsg$PP B 0 00` \TL___PPT9.& ~Definition 1 An algorithm O is an obfuscator if for any circuit C: (functionality) O(C) ~ C (i.e., O(C) computes the same function as C) (polynomial slowdown) |O(C)| p(|C|) for some polynomial p( ). We say that O is efficient if it runs in polynomial time.,C( 2( 2:( 2 aaaa aaaaaaaaaacccccaa a aaa a a  @`H 0 0޽h ? ̙33w 8c(  8 8 S ( @`   gDefining Securityg$PP  8 0D  B( 2 : 8 0 ,$D 0 A Natural Formal Interpretation: For any adversary A there s a simulator S such that for any circuit C A(O(C)) C.I. SC(1|C|)pi( 2( 2!aaaaaaaaaee ( 8 0(0 p Anything that can be learned from the obfuscated form, could have been learned by merely observing the circuit s input-output behavior (i.e., by treating the circuit as a black-box)   ( 2a : 8 040,$D 0 &This definition is impossible to meet!H'( 2ef ef ef& H 8 0޽h ? ̙33LD___PPT10$+8MD' = @B DS' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(+p+0+8 ++0+8 + <(  < < S    kDefining Security (2)g$PP  < 0`p,$D 0 Relaxation: simulator should only compute a specific function (even predicate) rather than generate an indistinguishable output.L( 2 a*aaDa  @` < 0 p ,$D 0 .2Weak Obfuscators: " A " (poly time) predicate p:{0,1}*{0,1} $ S such that for all circuits C Pr[ A(O(C)) = p(C) ] Pr[ SC(1|C|) = p(C) ] + negl(|C|)( 2a        aaeeememe.    < 0d$ ,$D 0 \Note: may be too weak for desired applications, but still we ll prove that it is impossible to meet.\e( 2aKa a aad H < 0޽h ? ̙33___PPT10+iدD' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(++0+< ++0+< ++0+< + D (  D D S :   #Inherently Unobfuscatable Functions$$g$PP.      D 0x>F2 .Definition 2 A (efficiently computable) function ensemble { Ft } ( Ft:{0,1}|t|{0,1}|t| ) is an unobfuscatable function ensemble (UF) if it satisfies:( 2 a.aaiaaiaia%aa&a  )  @` D 0lD0,$D 0 B( 2  D 0PG ,$D 0 $r There s a poly time predicate p:{0,1}*{0,1} such that: l:( 2aai  :  @`  D 0z@ ,$D 0 x(a) (p easy to compute with a circuit) There s a p.p.t A such that for any circuit C such that C ~ Ft A(C) = p(Ft) Hu( 2( 2aePPePP ePPaaaa aa aaia eme v  @` D 0$( ,$D 0 :(b) (p hard to compute with black-box access) For any p.p.t S , if t {0,1}n then Pr [ SFt (1n) = p(t) ] + negl(n) R( 2&( 2( 2aePPePP'ePPaaaaaemoem ee eg@W      @`H D 0޽h ? ̙33x p ___PPT10P +~>pDT ' = @B D ' = @BA?%,( < +O%,( < +Dk' =%(D' =%(D' =K@BBBBPB0B%(/%(D' =1:Bvisible*o3>+B#style.visibility<*D%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(++0+D ++0+D ++0+D ++0+D +   L= (  L L S (K   eThe Main Resultg$PP  L 0`PH$D 0TL___PPT9.&@ hTheorem 1: $ unobfuscatable functions $  very weak obfuscators. Theorem 2: $ one way functions $ unobfuscatable functions Theorem 3: $ efficient weak obfuscators $ one way functions Corollary 4: Efficient weak obfuscators do not exist.5( 2 aa.aa aa(aaa aaa aa&aaa aaa*a\   u  j *  L C *Aj0261685g,$D 0 L C *Aj0261685 g`,$D 0 L C *Aj0248285P` ,$D 0 L C *Aj0261685 g` ,$D 0RB L@ s *Do pH L 0޽h ? ̙33___PPT10f+#wD' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*LX%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*LY%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L5%(D' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*L%(+8+0+L +t   `T (  ` ` S \<$D 0   nThe Combination Operatorg$PP  ` 0, 0I,$D 0 ~For f0 , f1 : X Y , define f0#f1: {0,1} X Y by: f0#f1(b,x) := fb(x)6( 2( 2AAIAIA &D    @` ` 0 0H |$D 0H@___PPT9" jProperties: From a circuit C that computes f0#f1 one can compute circuits C0,C1 that compute f0 and f1 (Cb(x) := C(b,x) .) Oracle access to f0#f1 oracle access to both f0 and f1  ( 2( 2   .i  J  @`. ` 0PFP 7,$D 0 BUsing the combination operator, we can attempt to prove Theorem 2. C( 2CcB H ` 0޽h ? ̙33XP___PPT100.+Z;D' = @B DS' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*`%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*`%(+p+0+` ++0+` + hx(  h h S |CPp   tSolving The Input Size Problemg$PP  h 0|90`6 sLemma 5: If one-way functions exist then there exists an (efficiently constructible) ensemble { Da,b,z } such that:t( 2aVaaaaiiiia a&`    @`p h 0c,$D 0 1. There s a p.p.t A such that for any circuit C that satisfies C(a)= b and for any z: A Da,b,z(C) = a1n( 2aaaaaaaaa aaaaemo o ooeem&]     @` h 0 ` ,$D 0 kI2. Oracle access to Da,b,z does not help in learning anything about a . J( 2aaiiii*aaae.  3  @`R h 0 ,$D 0 Formal Interpretation (semantic security): For any p.p.t S there s a p.p.t S such that for any (poly time) function p:{0,1}*{0,1}* Pra,b,z [SDa,b,z(1n) = p(a) ] Pra,b,z [ S (1n) = p(a) ] + negl(n) x( 2aacccc(cckgoooogoo o oogoggg g $g$(o(,o,0o00o04g44o44g48g8 8g88g8<<           h 0Ȯp ,$D 0 (in particular there s a p.p.t A  such that A  (C# Da,b,z ) = a1)C( 2cc cccck k kkcckc.4    H h 0޽h ? ̙33N F ___PPT10& +1-8D* ' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(++0+h ++0+h ++0+h ++0+h +:&   ~ p (  p p S    nLemma 5 Proves Theorem 2g$PP  p 0pPp$D 0<4___PPT9 * Define Fa,b,z := Ca,b#Da,b,z p(a,b,z) := a1 We claim that { Fa,b,z } is an IUF w.r.t the function p . Algorithm A: When given a circuit F do: Decompose F into circuits C,D such that F~C#D Return A D(C) Claim 1: For any circuit F such that F~ Fa,b,z , A(F) = a1 Claim 2: For any p.p.t S Pra,b,z[ SFa,b,z(1n) = a1 ] + negl(n)( 2<( 2A( 2F( 2aaiiiiai i iaiiiiaaa a  a  a  i  a  a  a  i $i$(i((i((a((a((a((a( (a((a((a((a( ,a,,a,,a,,a, ,a,,a,,a,,a,,i,,a,,a, ,a,,a,,a, ,a,,a,,i,0i04i44i44i44a44e44e44m44e4 8a88a88a88a88a88e88m8+B#style.visibility<*p%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p-%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p-i%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*pi%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p'%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p'T%(+8+0+p +#    x (  x x S ,YPp   fProof of Lemma 5g$PP  x 0y@ (,$D 0 | Let (ENCk , DECk) be a private key encryption scheme. Define: Ia,k  constant function ENCk(a1)& ENCk(an) Hk(c,d,) := ENCk( DECk(c) DECk(d) ) Ba,b,k (c1,& ,cn) := a1 if DECk(c1) = b1,& , DECk(cn) = bn Ba,b,k (c1,& ,cn) := 0 otherwise Let { hk } be a pseudorandom function ensemble. We define: Da,b,k,,k := Ia,k,k #Hk,k # Ba,b,k~S( 2aaiaia%a aiiiaaiaaiaiaaiaia  i i iaiaiaaiaaaiaiaaiaiaiaaiiiiaiaiaaaia&a aemm m  e  m  e  e  m $m$(m((e((e((m((e((((m(,m,0m06    .                                  5          H x 0޽h ? ̙33 ___PPT10+DD' = @B DR' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x8%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x8@%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x@k%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*xk%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x"%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x"-%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*x-S%(+8+0+x + vn0(    S     Unobfuscatable Encryption Scheme!!g$PP"  x  0` q  Definition 3: A (CPA secure) private key encryption scheme (GEN, ENC , DEC) is unobfuscatable if there is an alg A such that A(C) = k for any circuit C s.t. C~ENCk That is, A can totally break the encryption scheme given any circuit that computes the encryption function.( 2 a.aaaaaa aeaa aaaaia aaa aaa0abP    0  k \  0@ 0  rTheorem 6: If secure private key encryption schemes exist then so do inherently unobfuscatable encryption schemes.8s( 2 aga.P   H  0޽h ? ̙33T    @ (    S 4   hProof of Theorem 6g$PP   0  ` & Suppose that (GEN,ENC,DEC) is a (CPA) secure private key encryption scheme. It follows that one way function exist. Let { Fa,b,z } be the ensemble from the proof of Theorem 2 and change it to F a,b,z,k such that there s an algorithm A such that A(F ) = (a,b,z,k) for any circuit F such that F ~ F a,b,z,k. Define (GEN , ENC ,DEC ) to be the following: GEN (1n) := (k, a, b,z) where kGEN (1n) ENC k a, b,z(m) := ENCk(m);F a,b,z,k(m) DEC k a, b,z(c;y) := DECk(c) ( 2 a a_aaiiiia>aai i iiaa a aaaaaaa aaii i  i  a  a  a  a  i   a  a $a$(a( (a((((((((a((i((i(,i,0i00i0 0a00i00a0000a00i04i48i88i8 8a88i88i8