Protecting Obfuscation Against Algebraic Attacks Research Overview

protecting obfuscation against algebraic attacks n.w
1 / 36
Embed
Share

Explore the latest advancements in protecting obfuscation against algebraic attacks, including virtual black-box models, impossibility results, candidate obfuscation security, and more. Dive into the complexities of algorithmic protection in the digital age.

  • Protection
  • Obfuscation
  • Research
  • Security
  • Algebraic
rayaanacharya
ray_car Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Protecting Obfuscation Against Algebraic Attacks Boaz Barak Sanjam Garg Yael Tauman Kalai Omer Paneth Amit Sahai

  2. Program Obfuscation ? cipher ?????(?) Obfuscation ? cipher Public Key

  3. Virtual Black-Box (VBB) [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] Algorithm ? is an obfuscator for a class ? if: For every PPT adversary ? there exists a PPT simulator ? such that for every ? ?: ? ?(?) ? ? ?(?)

  4. VBB Impossibility [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] There exists contrived unobfuscatable programs. Code of a program equivalent to ? Secret ? ? Execute ? ? on itself Secret ? ?(?)

  5. First Candidate Obfuscation [Garg-Gentry-Halevi-Raykova-Sahai-Waters 13] What is the security of the candidate? Assumption: The [GGHRSW13] obfuscator is an Indistingushability Obfuscator. Indistinguishability Obfuscation(??): No known attacks except [BGIRSVY01]. For every pair of equivalent circuits ?1 ?2: ?? ?1 ???(?2)

  6. This Work A variant of the [GGHRSW13] obfuscator is VBB for all circuits in a generic model (underlying algebra is idealized)

  7. Multilinear Maps [Boneh-Silverberg 03, Garg-Gentry-Halevi 13] Encoding ?? of ? ? under a set ? ? . 1. ? 1,2,5 ? 1,2,5= ? ? 1,2,5 2. ? 1,2,5 ? 3,4= ? ? 1,2,3,4,5 = 1 iff ? = 0 3. ?? ? 1, ,? Idealy: any other operation is hard.

  8. The Generic MM Model Add Multiply ZT ? ? ?1,?2,E3,E4,E5 ? ?(?) ?6,?7,E8,E9,E10 ?(?) ?(?)

  9. Our Result Virtual Black-Box obfuscation in the generic MM model: 1. For NC1. 2. For P/Poly assuming LWE.

  10. Avoiding VBB Impossibility In the Generic MM Model Code of a program equivalent to ? Secret ? Add Mul ZT Execute ? ? on itself Secret ?(?)

  11. Interpretation Secure obfuscation against algebraic attacks . Warning: Non-algebraic attacks do exist [BGIRSVY01].

  12. Interpretation II Multi-Message Semantically-Secure Multilinear Maps [Pass-Seth-Telang 13] This Work: VBB with Generic Multilinear Maps + Virtual gray-box obfuscation for NC1 [Bitansky-Canetti-Kalai-P 14]. ?? for P/Poly (assuming LWE) [Pass-Seth-Telang 13]

  13. Previous Works [GGHRSW13] [Canetti-Vaikuntanathan13] VBB from Black-Box Pseudo-Free Groups ?? in the Generic Colored Matrix Model [Brakerski-Rothblum13] This Work ?? in the Generic MM Model VBB in the Generic MM Model [Brakerski-Rothblum13] Assuming BSH

  14. The Construction 1. Construction for NC1 via branching programs 2. Bootstrap to P/Poly assuming LWE (leveled-FHE with decryption in NC1)

  15. Branching Programs Program: 0 0 0 0 0 0 0 0 0 0 0 0 ?4 ?7 ?2 ?12 ?1 ?11 ?6 ?8 ?10 ?3 ?9 ?5 1 1 1 1 1 1 1 1 1 1 1 1 ?4 ?1 ?11 ?7 ?2 ?12 ?6 ?10 ?8 ?3 ?9 ?5 Input: ?1 ?2 ?3 ?4

  16. BP Evaluation Program: 0 0 0 0 0 0 0 0 0 0 0 0 ?4 ?7 ?2 ?12 ?1 ?11 ?6 ?8 ?10 ?3 ?9 ?5 1 1 1 1 1 1 1 1 1 1 1 1 ?4 ?1 ?11 ?7 ?2 ?12 ?6 ?10 ?8 ?3 ?9 ?5 Input: Output: or 0 1 1 0

  17. Obfuscating BP 1. Randomizing [Kilian 88] 2. Encoding

  18. Step 1: Randomizing Program: ?4 ?3 ?1 ?11 ?2 ?12 ?7 ?6 ?8 ?10 ?9 ?5 0 0 0 0 0 0 0 0 0 0 0 0 ?1 ?2 ?4 ?7 ?11 ?12 ?9 ?6 ?8 ?10 ?3 ?5 1 1 1 1 1 1 1 1 1 1 1 1 Input: Output: or ?1 ?2 ?3 ?4

  19. Step 1: Randomizing Program: ?4 ?3 ?1 ?11 ?2 ?12 ?7 ?6 ?8 ?10 ?9 ?5 0 0 0 0 0 0 0 0 0 0 0 0 ?1 ?2 ?4 ?7 ?11 ?12 ?9 ?6 ?8 ?10 ?3 ?5 1 1 1 1 1 1 1 1 1 1 1 1 Input: Output: or 0 1 1 0

  20. Step 2: Encoding Program: ?4 ?3 ?1 ?11 ?2 ?12 ?7 ?6 ?8 ?10 ?9 ?5 0 0 0 0 0 0 0 0 0 0 0 0 ?1 ?2 ?4 ?7 ?11 ?12 ?9 ?6 ?8 ?10 ?3 ?5 1 1 1 1 1 1 1 1 1 1 1 1 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} Obfuscation includes the encodings: ? ?? ? level ?,bit ? , 12 {1, ,12}

  21. Proof of Security ?4 ?12 ?1 ?8 ?9 ?5 0 0 0 0 0 0 ?2 ?7 ?11 ?3 ?6 ?10 1 1 1 1 1 1 + ?6 ?10 0 0 ?2 0 ?4 ?7 ?11 ?12 ?8 ?3 ?9 ?5 1 1 1 1 1 1 1 1 ?1 1 ? = 0 + ?

  22. Simulation Outline Test every monomial separately: ?4 ?12 ?1 ?8 ?9 ?5 0 0 0 0 0 0 ?2 ?7 ?11 ?6 ?10 ?3 1 1 1 1 1 1 By querying ? 0 1 1 0

  23. Problems 1. Inconsistent monomials: ?4 ?12 ?1 ?8 ?9 0 0 0 0 0 ?2 ?7 ?11 ?6 ?10 ?3 ?5 1 1 1 1 1 1 1 2. Too many monomials: ?1 0+ ?1 ?2 0+ ?2 ?12 0+ ?12 1 1 1

  24. Changing the Sets {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} ?4 ?3 ?2 ?12 ?1 ?6 ?7 ?10 ?11 ?8 ?9 ?5 0 0 0 0 0 0 0 0 0 0 0 0 ?1 ?4 ?7 ?11 ?2 ?12 ?6 ?8 ?10 ?3 ?9 ?5 1 1 1 1 1 1 1 1 1 1 1 1 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {1, ,12}

  25. Changing the Sets 7 7 1 1 2 2 3 3 4 4 6 6 8 8 9 9 10 10 11 11 12 12 5 5 ?4 ?3 ?2 ?12 ?1 ?7 ?11 ?6 ?8 ?10 ?9 ?5 0 0 0 0 0 0 0 0 0 0 0 0 ?1 ?4 ?7 ?11 ?2 ?12 ?6 ?8 ?10 ?3 ?9 ?5 1 1 1 1 1 1 1 1 1 1 1 1 7 7 1 1 2 2 3 3 4 4 6 6 8 8 9 9 10 10 11 11 12 12 5 5 1, ,12 1 , ,12

  26. Changing the Sets 1 1 9 9 5 5 ?1 ?9 ?5 0 0 0 ?1 ?9 ?5 1 1 1 1 1 9 9 5 5

  27. Straddling Set System 1 1 9 9 5 5 ?1 ?9 ?5 0 0 0 ?1 ?9 ?5 1 1 1 1 5 9 1 5 9 1,5,9 1 ,5 ,9 = 9 9 = 1 5 1 1 9 1 5 5 5 9 0-matrices 1-matrices

  28. Straddling Set System 1 1 9 9 5 5 ?1 ?9 ?5 0 0 0 ?1 ?9 ?5 1 1 1 1 5 9 1 5 9

  29. Straddling Set System 7 7 1 1 2 2 3 3 4 4 6 6 8 8 9 9 10 10 11 11 12 12 5 5 7 4 8 1 5 2 6 3 7 6 8 9 1 10 2 11 3 12 4 5 9 11 12 10

  30. Too Many Monomials ?1 0 ?5 0 ?9 0+ ?1 1 ?5 1 ?9 ?4 0 ?8 0 ?12 0+ ?4 1 ?8 1 ?12 1 1 + +

  31. Pairing Level Together

  32. From Two Levels to One 10,8 10 ,8 10,8 10 ,12 10,8 2 ,8 10,8 2 ,12 10 10 8 8 ?9 0 ?10 0 ?9 0 ?10 1 ?10 ?9 0 0 ?10 ?9 ?9 1 ?10 0 1 1 10 2 8 ?9 1 ?10 1 12

  33. From Two Levels to One

  34. Dual-Input BP Input: ?1 ?2 ?3 ?4

  35. Too Many Monomials + +

  36. Thank You!

Related


More Related Content