On the Impossibility of Approximate Obfuscation

In this study, the authors delve into the challenging realm of approximate obfuscation, shedding light on its complexities and limitations. The exploration of program obfuscation, virtual black-box constructions, and the implications of relaxed security and functionality reveal foundational insights into the boundaries of obfuscation techniques. This journey from understanding the impossibility of obfuscation to its practical applications uncovers a fascinating landscape of cryptographic research.

• Cryptography
• Obfuscation
• Security
• Virtual
• Functions

osll695 Follow

Uploaded on Feb 15, 2025 | 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.

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.

Presentation Transcript

1. On the Impossibility of Approximate Obfuscation Nir Bitansky and Omer Paneth

2. Program Obfuscation ? Compute ???(?) ? = ???(?)

3. Program Obfuscation ? ? = ???(?)

4. Program Obfuscation ? Sign email ? with ?? If ? starts with omer@bu.edu ? = ?(?)/

5. Virtual Black-Box [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] ??? is an obfuscation of ???: - Functionality: ?,???? = ???? - Security: ??? ? ? ???

6. Impossibility of Obfuscation There exist families of functions that cannot be obfuscated [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01]

7. Relaxed Security [Barak et al. 01, Goldwasser-Rothblum07, Hofheinz-Malone-Lee-Stam07, Hohenberger-Rothblum-Shelat-Vaikuntanathan07, Bitansky-Canetti10] - Functionality: ?,???? = ???? - Security: ??? ? ? ???

8. Relaxed Functionality? - Functionality: ?,???? = ???? - Security: ??? ? ? ???

9. Approximate Obfuscation [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] ??? is an approximate obfuscation of ???: - Functionality: Pr - Security: ? ????? = ???? > 0.9 ??? ? ? ???

10. Main Result Assuming trapdoor permutations, there exist families of functions that cannot be approximately obfuscated Motivation? Positive applications

11. From Impossibility to Applications Impossibility of approximate obfuscation Non-black-box extraction ?? Zero-knowledge with Worst-case ??? ? ???(?) resettable security extractable signatures

12. Plan [BGIRSVY 01]: Impossibility of Obfuscation Unobfuscatable Functions This work: Impossibility of Approximate Obfuscation Robust Unobfuscatable Functions Applications

13. Unobfuscatable Functions From Barak et al. ??? 1. Black-box unlearnability: efficient ?, ?? ?: ? ?? 2. Extraction: efficient ?, ?,??: ?? Pr ? ?? ? = ???? = 1 ? ?

14. Robust Unobfuscatable Functions ??? 1. Black-box unlearnability: efficient ?, ?? ?: ? ?? 2. Robust extraction: efficient ?, ?,??: ?? Pr ? ?? ? = ???? > 0.9 ? ?

15. Robust Unobfuscatable Functions 90% ? ??? ??? ? ? ? ? ?? ??

16. RUFs Construction

17. Unobfuscatable Functions Construction of Barak et al. (using FHE for simplicity) ??,?,??? : ?,? two ?-bit strings ?? - secret key for FHE

18. Unobfuscatable Functions 0? ??? ? ??? b ? ? ? ? ? ? ? = ? ? = 0? Dec??(?) = ? o.w. Enc??(?) ? ??,?,??(?)=

19. Black-Box Unlearnability 0? ??? ? ??? b ? ? ? ? ? ? ? ?

20. Extraction 0? ??? ? ??? b ? ????(?) ? ? ? ? ? ? ? ? ?

21. Robust Extraction? 0? ??? ? ??? b ? ? ? ? ? = ? ? = 0? ?????(?) = ? ?.?. ?????(?) ? ? ? ? ? (?) =

22. A Taste of the Construction ??,?(?) = ? ? = ? ?.?. Q: Find ? such that: Randomly reduce ? to ? ? with 10% errors ?a,b

23. Getting Robustness ??,?(?) = ? ? = ? ?.?. ??,?,?? = ? PRF?? ?,?,?? = PRF?? ?

24. ? ? ? ? PRF(?) ? ? ? ? ? ? PRF(?) (?.?.0.8) ?, with 10% errors ??,?,?? = ? PRF?? ?a,b ?,?,?? = PRF?? ?

25. ?, ? queries ? on ? and ? ? ? ? queries on ? ? ? ??,?,?? = ? PRF?? ?a,b ?, ?,?,?? = PRF?? ?

26. Construction of RUFs ? = ? ? = 0? ?????(?) = ? ?.?. ? ?????(?) ? ??,?,??(?) =

27. Assumptions RUFs from trapdoor permutations. Weak RUFs from OWF only: ?: ? ? ???? , ? ?? ?

28. Applications

29. Publicly-Verifiable RUOFs ??,?? Gen() Ver???,? = 1 iff ? = ???(?) ?? ?? ??? ?? ? ?? ? ? 1 Pr ? ?Ver???,? ? = 1 > ??,?? Gen() poly(?)

30. Resettably-Sound ZK [Micali-Reyzin 01, Barak-Goldreich-Goldwasser-Lindell 01] ? ? Standard ZK Resettable Soundness ? ?

31. Resettable Soundness [Micali-Reyzin 01, Barak-Goldreich-Goldwasser-Lindell 01] ? ? ?

32. Resettable Soundness [Micali-Reyzin 01, Barak-Goldreich-Goldwasser-Lindell 01] ? ? ? ?

33. No Black-Box Simulator [Barak-Goldreich-Goldwasser-Lindell 01] Resettable soundness Zero-knowledge (black-box simulator) ? ? ? ? ? ?

34. Resettably-Sound ZK [Barak-Goldreich-Goldwasser-Lindell 01, BP 12, Chung-Pass-Seth 13] Resettable soundness Zero-knowledge (non-black-box simulator) ? ? ? ? ? ?

35. Resettably-Sound ZK ?? ??,?? ? ? ???(?) ? ? Witness indistinguishable proof: ? or? knows ??

36. Resettably-Sound ZK ?? ??,?? ? ???(?) ? ? Witness indistinguishable proof: ? or? knows ??

37. Analysis Resettable soundness Zero-knowledge ??? ? ? ??? ?.?. ? ? ? ??? ? ???(?) 1 ? p ? ? ?? ??

38. More Resettable Crypto Resettably-sound ZK from OWFs (Different approach from Chung-Pass-Seth 13) Simultaneously-resettable ZK from OWFs (using srWI by Chung-Ostrovsky-Pass-Visconti 13) 4-message resettably-sound ZK 3-message simultaneously-resettable WI proof of knowledge

39. Worst-Case Extractable Signatures Digital Signatures: ??,?? Sign?? Sign?? ? ?,? ? , ? ?? ??

40. Worst-Case Extractable Signatures For every ??,??: ? ? breaks security for ??,?? ? ??

41. Thank You. #define _ -F<00||--F-OO--; int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO(){ _-_-_-_ _-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_ _-_-_-_ } IOCCC 88