On the Existence of Extractable One-Way Functions

Presentation on theme: "On the Existence of Extractable One-Way Functions"— Presentation transcript:

1 On the Existence of Extractable One-Way Functions
Research Seminar In Cryptography 2016/2017 Spring On the Existence of Extractable One-Way Functions [N. Bitansky, R. Canetti, O. Paneth, A. Rosen; 2016] Presentation: Karim Baghery Supervisor: Michal Zajac Coordinator: Dr. Vitaly Skacheck

2 Outline: Motivation Behind Knowledge Extraction
Zero-Knowledge and ZK Poofs of Knowledge Knowledge Extraction Extractable Functions (EF) & Applications A Reduction Using EF Contributions of the Paper Impossibility of Unbounded-Auxiliary-Input Extractable One-Way Fun. Main Intuition and details Theorem Proof with details Extend to Generalized EOWF Bounded-Auxiliary-Input Extractable One-Way Fun.

3 Zero-Knowledge Proofs
Definition Hard to present accurate definition! One can get knowledge from information Practical scenarios Discrete Log: Prove that we know the secret key 𝑠 for the public key 𝑦= 𝑔 𝑠 , without revealing the secret key. Isomorphism: Prove that 𝐺 1 and 𝐺 2 are isomorphic without revealing it. Factoring: Prove factoring of a large prime without revealing them Generally one party convinces another one that knows a secret, without revealing extra information about the secret. Zero-Knowledge Proofs

4 What does even knowing mean?!
Zero Knowledge Proofs: [Goldwasser-Micali-Rackoff] Intuition A P can prove to V any NP statement, so that V does not learn anything from the proof except the fact that the statement is true. 𝑥∈ℒ 𝑃 𝑉 Hide the Witness It says that if P is convincing, it must also know witness corresponding to the NP statement, 𝜔∈ 𝑅 𝐿 (𝑥). What does even knowing mean?!

5 What can be Efficiently Extracted from the adversary
ZK Proofs of Knowledge: [Goldwasser-Micali-Rackoff, Feig-Shamir, Bellareh-Goldreich] Require something stronger than soundness If P is convincing, then there is an efficient knowledge extractor that, can obtain the witness from P. 𝑥∈ℒ 𝑃 𝑉 Hide the Witness Extraction Witness 𝜔∈ 𝑅 𝐿 (𝑥) Effective Knowledge = What can be Efficiently Extracted from the adversary

6 How to Extract?

7 Black–Box security proof is impossible [Goldreich-Krawczyk]
How to Extract? Black-Box Extracting with interaction (Rewinding) Or Black-Box Extraction Adversary Public Parameters Extraction Black-Box Extraction has some limitations 𝑃 𝑉 3-Message Zero-Knowledge Black–Box security proof is impossible [Goldreich-Krawczyk]

8 Knowledge Assumption and Extractable Functions
A Different Approach... Knowledge Assumption and Extractable Functions

9 How to Extract? Non-Black Box
Knowledge of Exponent Assumption [Damgård 92] Extraction without Interaction 𝑥 𝑔 1 𝑔 2 𝑔 3 … ℎ 1 𝑔,ℎ ℎ 2 𝑔 𝑥 , ℎ 𝑥 Adversary ℎ 3 … 𝑔,ℎ← 𝐺 ∗ {𝑔 𝑥 , ℎ 𝑥 :𝑥∈ 𝑍 𝐺 } Is 1 𝐺 -Sparse

10 How to Extract? Non-Black Box
Knowledge of Exponent Assumption [Damgård 92] Extraction without Interaction Adversary 𝑔 𝑥 , ℎ 𝑥 𝑔,ℎ 𝑔,ℎ← 𝐺 ∗ Non-Black-Box Extraction Extraction 𝑥 ∀𝐴 ∃𝐸 s.t. 𝐴 𝑔,ℎ → 𝑔 𝑥 , ℎ 𝑥 ⇒ 𝐸 𝑔,ℎ →𝑥

11 Non-Black-Box Extraction
Extractable Functions (EF): [Canetti-Dakdouk] Generalization of Knowledge Assumption A family of function 𝒇 𝒆 is extractable if: Adversary 𝑓 𝑒 (𝑥) 𝑒 + Hardness One-way, Collision resistance 𝑒←𝒦(𝑛) Non-Black-Box Extraction 𝑥 ′ 𝑓 𝑒 𝑥 ′ = 𝑓 𝑒 (𝑥) Formally ∀𝐴 ∃𝐸 s.t. 𝐴 𝑒 → 𝑓 𝑒 𝑥 ⇒𝐸 𝑒 →𝑥 Authors consider one-way extractable functions

12 Knowledge of Exponent (KoE)
Application of EF: Knowledge of Exponent (KoE) Extractable One-Way Functions (EOWF) Extractable Collision-Resistant Hash Functions (ECRH) 3-Message Zero-Knowledge 2-Message Succinct Argument

13 A Reduction Using EF: Factoring
Assumption: ∀𝐴 ∃𝐸 s.t. 𝐴 𝑒 → 𝑓 𝑒 (𝑥) ⇒ 𝐸 𝑒 →𝑥 𝑒 𝑒 𝑒←𝒦(𝑛) 𝑝.𝑞 𝑝 𝐴 𝐸 𝑓 𝑒 (𝑥) 𝑥 Reduction Knowledge Assumption = Hole in Reduction (no explicit construction) 𝑒←𝒦(𝑛) 𝑒 𝑒 𝑝.𝑞 𝑝 𝐴 𝐸 𝑓 𝑒 (𝑥) 𝑥 Reduction

14 Can We Construct Explicit Extractors?
A Question: 𝑒 𝑒 𝑒←𝒦(𝑛) 𝑝.𝑞 𝑝 𝐴 𝐸 𝑓 𝑒 (𝑥) 𝑥 Reduction Can We Construct Explicit Extractors? Or Do Extractable One-Way Functions with an Explicit Extractor Exist?

15 Auxiliary Information
This Paper… Sometimes We Can! Depends on Adversary’s Auxiliary Information

16 Example: ZK Proofs 𝑥 𝑃 𝑉 𝑥∈ℒ 𝑓 𝑒 (𝑥) 𝑒 𝑧 𝑥 ′ 𝑒 𝑓 𝑒 𝑢 Adversary
Auxiliary input 𝑥 𝑥∈ℒ 𝑒 𝑃 𝑉 𝑓 𝑒 𝑢 Knowledge Extraction with Auxiliary Information 𝑒 Adversary 𝑓 𝑒 (𝑥) 𝑧 ∀𝐴 ∃𝐸 ∀𝑧 Extraction 𝑥 ′ 𝑓 𝑒 𝑥 ′ = 𝑓 𝑒 (𝑥)

17 Contributions of the Paper:
EOWF with unbounded Auxiliary Info. Generalized EOWF with unbounded Auxiliary Info. Generalized EOWF with bounded Auxiliary Info. EOWF with bounded Auxiliary Info. Adversary Adversary 𝑧 ≫|𝑓(𝑥)| 𝑧 ≪|𝑓(𝑥)| Explicit Extractor Extractor Impossible Possible Indistinguishability Obfuscation Public-verifiable delegation for P

18 Impossibility…: 𝑧 ≫|𝑓(𝑥)| Impossible
EOWF with unbounded Auxiliary Info. Adversary 𝑧 ≫|𝑓(𝑥)| Extractor Impossible Indistinguishability Obfuscation

19 Black-box obfuscation
Intuition of Impossibility…: [Goldreich, Hada-Tanaka] If you can have an arbitrary auxiliary information then this info may include some very obfuscated code… In order to extract pre image from this circuit, you have to efficiently reverse-engineer 𝐴 𝑓 𝑘 (𝑥) 𝑘 Black-box obfuscation Universal Adversary 𝐴 𝑘,𝑧= Universal Extractor 𝑥 Assuming virtual black-box obfuscation [Goldreich, Hada-Tanaka] Assuming indistinguishability obfuscation

20 Black-box obfuscation
Intuition of Impossibility…: They focus on the ‘hardest scenario’, where the auxiliary input z may represent an arbitrary malicious and potentially obfuscated code. 𝐴 𝑓 𝑘 (𝑥) 𝑘 Black-box obfuscation Universal Adversary 𝐴 𝑘,𝑧= Universal Extractor 𝑥 An adversary, given such an obfuscated circuit as auxiliary input z, can run it on the key e for the extractable function and always obtain a proper image The question is whether the extractor, given the same (e; z), can output a preimage.

21 Intuition of Impossibility…:
Black-Box Extractor Adversary 𝑥 𝑘 = 𝑈 𝑛 Adversary 𝑥 𝑘 𝑘 𝑥 𝑘 =𝑃𝑅 𝐹 𝑠 (𝑘) 𝑓 𝑘 ( 𝑥 𝑘 ) Intuitively, since we had given the extractor black-box access to the circuit Ck, instead of an obfuscation of Ck, it would have to invert the one-way function to obtain such a preimage. Indeed, since the oracle Ck answers any query e with 𝑓 𝑒 (𝑃𝑅 𝐹 𝑘 (𝑒)), it follows from pseudo-randomness that finding a preimage of 𝑓 𝑒 (𝑃𝑅 𝐹 𝑘 (𝑒)) is as hard as finding a preimage of 𝑓 𝑒 (𝑢), for a uniformly random 𝑢.

22 Theorem: Proof: Impossibility...: 𝑓 𝑒 (𝑥) 𝐴 𝑒,𝑧 𝑧←𝒵 𝑥 𝐸
Assuming indistinguishability obfuscation for all circuits, there is not extractable one-way function (EOWF) with unbounded common auxiliary input. Proof: For any EOWF family ℱ, one should describe an adversary A and a distribution 𝒵 on auxiliary inputs, such that any extractor E fails, for auxiliary inputs sampled from 𝒵. 𝑓 𝑒 (𝑥) 𝐴 𝑒,𝑧 𝑧←𝒵 𝑥 𝐸

23 [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01]
Indistinguishability Obfuscation(IO): [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] 𝐶 1 𝐶 2 ≡ Obfuscator 𝒊𝐎 ≈ 𝑐 𝒪(𝐶 1 ) 𝒪(𝐶 2 ) 𝒪 𝐶 1 (x) = 𝒪 𝐶 2 𝑥

24 Extractable One-way Functions:

25 Puncturable PRFs: Puncturable PRFs: An efficiently computable family of functions: 𝓟𝓡𝓕= 𝑃𝑅 𝐹 𝑘 : 0,1 𝑚 𝑛 → 0,1 𝑙 𝑛 | 𝑘← 0,1 𝑛 , 𝑛∈𝑁 is a puncturable PRF if there exists a puncturing algorithm 𝑃𝑢𝑛𝑐 that takes as input a key 𝑘 and a point 𝑥 ∗ , and outputs a punctured key 𝑘 𝑥 ∗ , so that Puncture a given 𝑘 at point 𝑥 in the domain of fun Functionality is preserved under puncturing Indistinguishability at punctured points

26 Theorem: Proof: Impossibility...: 𝑓 𝑒 (𝑥) 𝐴 𝑒,𝑧 𝑧←𝒵 𝑥 𝐸
Assuming indistinguishability obfuscation for all circuits, there is not extractable one-way function (EOWF) with unbounded common auxiliary input. Proof: For any EOWF family ℱ, one should describe an adversary A and a distribution 𝒵 on auxiliary inputs, such that any extractor E fails, for auxiliary inputs sampled from 𝒵. 𝑓 𝑒 (𝑥) 𝐴 𝑒,𝑧 𝑧←𝒵 𝑥 𝐸

27 Adversary & Distribution:
The universal adversary 𝐴 𝑒,𝑧 𝑧←𝒵 Parses 𝑧 as a circuit and returns 𝑧(𝑒) 𝑧(𝑒) The auxiliary input distribution Let ℱ be a family of EOWFs and let 𝓟𝓡𝓕 be a puncturable pseudo- random function (PRF) family. Define two families of circuits

28 Distribution: The auxiliary input distribution
Define two families of circuits

29 Distribution: The auxiliary input distribution
Let 𝐶 𝑠 shows a circuit padded with zero to max ( 𝒞 , 𝒞 ∗ ) Auxiliary input distribution 𝑍 𝑛

30 Let E be any PPT candidate extractor for A then
The rest of proof...: Proof: For any EOWF family ℱ, one should describe an adversary A and a distribution 𝒵 on auxiliary inputs, such that any extractor E fails, for auxiliary inputs sampled from 𝒵. 𝑓 𝑒 (𝑥) 𝐴 𝑒,𝑧 𝑧←𝒵 𝑥 𝐸 Proposition: Let E be any PPT candidate extractor for A then The key 𝑒 is sampled independently of the auxiliary input 𝑧.

31 Let E be any PPT candidate extractor for A then
The rest of proof...: Proposition: Let E be any PPT candidate extractor for A then Proof of Preposition: - First step: Adversary - It directly comes from… 𝑒,𝑧 𝑧(𝑒) A

32 Let E be any PPT candidate extractor for A then
The rest of proof...: Proposition: Let E be any PPT candidate extractor for A then Proof of Preposition: - Second step: contradiction - Assume that the extractor E successfully outputs a preimage with noticeable probability 𝜀(𝑛)

33 The rest of proof...: Proof of Preposition:
- Second step: contradiction_ E successfully outputs a preimage with noticeable probability 𝜀(𝑛) - Third step: for every 𝑒 ∗ consider an alternative distribution Z n ( 𝑒 ∗ , y ∗ ) Instead of sampling a circuit C 𝑘 , samples a circuit C 𝑘 𝑒 ∗ , 𝑦 ∗ By first sampling 𝑘 as usual, and then computing 𝑦 ∗ = 𝑓 e ∗ ( PRF 𝑘 𝑒 ∗ ) and the punctured key 𝑘 𝑒 ∗

34 The rest of proof...: Proof of Preposition:
- Second step: contradiction_ E successfully outputs a preimage with noticeable probability 𝜀(𝑛) - Third step: The extractor still success in finding a preimage,

35 The rest of proof...: Proof of Preposition:
- Third step: The extractor still success in finding a preimage, - Fourth step: consider another alternative distribution Z n ( 𝑒 ∗ , 𝑢) Again samples a circuit C 𝑘 𝑒 ∗ , 𝑦 ∗ , samples 𝑘 as usual and just samples 𝑦 ∗ = 𝑓 e ∗ 𝑟 for independent random 𝑟← 0, 1 𝑙

36 This means that 𝜀 can be used to break the one-wayness of 𝓕
End of Proof: Proof of Preposition: - Fourth step: consider another alternative distribution Z n ( 𝑒 ∗ , 𝑢) This means that 𝜀 can be used to break the one-wayness of 𝓕 An Inventor:

37 Theorem: Proof: Done! Impossibility...:
Assuming indistinguishability obfuscation for all circuits, there is not extractable one-way function (EOWF) with unbounded common auxiliary input. Proof: Done! Puncturable PRFs ← one-way functions. Thus, the impossibility result is implied by 𝑖𝒪 without any further assumptions.

38 Impossibility on GEOWFs:
Generalized EOWF with unbounded Auxiliary Info. EOWF with unbounded Auxiliary Info. Adversary 𝑧 ≫|𝑓(𝑥)| Extractor Impossible Indistinguishability Obfuscation

39 Impossibility on GEOWFs:
In this case, instead of obtaining an Inverter that breaks the one wayness of 𝓕, one can obtain an Inverter that breaks the 𝑹 𝓕 -hardness of 𝓕.

40 ? Open Problems...? 𝑧 ≫|𝑓(𝑥)| 𝑧 ≪|𝑓(𝑥)| Adversary Adversary Extractor
Generalized EOWF with unbounded Auxiliary Info. Extractable CRHF\COM\1-to-1 OWF Generalized EOWF with bounded Auxiliary Info. Adversary Adversary EOWF with unbounded individual auxiliary info. | 𝒛 𝑨 |>|𝒇(𝒙)| 𝑧 ≫|𝑓(𝑥)| 𝑧 ≪|𝑓(𝑥)| Extractor Extractor ? Explicit Extractor Impossible Possible ? Indistinguishability Obfuscation Private-verifiable delegation for P LWE [Kalai-Raz-Rothblum]

41 Thank You. ? Write catchy header here! Text goes here
A sample of Persian calligraphy . I do not know what is the secret of your eyes, which is out of my power to watch and explain.

42 BACKUP SLIDES

43 Definition of EF with AI:
For every 𝐴 and auxiliary input 𝑧 𝐴 there exist 𝐸 and auxiliary input 𝑧 𝐸 such that for every auxiliary input 𝑧: 𝐴 𝑧 𝐴 ,𝑧,𝑘 → 𝑓 𝑘 (𝑥) ⇒ 𝐸 𝑧 𝐸 ,𝑧, 𝑘 →𝑥 For every 𝐴 and auxiliary input 𝑧 𝐴 there exist 𝐸 and auxiliary input 𝑧 𝐸 such that for every auxiliary input 𝑧: 𝐴 𝑧 𝐴 ,𝑧,𝑘 → 𝑓 𝑘 (𝑥) ⇒ 𝐸 𝑧 𝐸 ,𝑧, 𝑘 →𝑥 Individual \ Common Bounded \ Unbounded

44 𝐴 𝑒,𝑧 𝑥 𝐸 𝐴 𝑓 𝑘 (𝑥) 𝐴 𝑘,𝑧= 𝑥 Intuition Impossibility…: 𝑓 𝑒 (𝑥) 𝑘
Common A.I. 𝐴 𝑒,𝑧 𝐸 𝑥 Universal Extraction Universal Adversary 𝐴 𝑓 𝑘 (𝑥) 𝑘 𝑘,𝑧= 𝐴 Universal Extractor 𝑥

45 Black-box obfuscation
Intuition Impossibility…: We focus on the ‘hardest scenario’, where the auxiliary input z may represent an arbitrary malicious and potentially obfuscated code. 𝐴 𝑓 𝑘 (𝑥) 𝑘 Black-box obfuscation Universal Adversary 𝐴 𝑘,𝑧= Universal Extractor 𝑥 An adversary, given such an obfuscated circuit as auxiliary input z, can run it on the key e for the extractable function and always obtain a proper image The question is whether the extractor, given the same (e; z), can output a preimage.

46 Intuition Impossibility…:
Black-Box Extractor Adversary 𝑥 𝑘 = 𝑈 𝑛 Adversary 𝑥 𝑘 𝑘 𝑥 𝑘 =𝑃𝑅 𝐹 𝑠 (𝑘) 𝑓 𝑘 ( 𝑥 𝑘 ) Intuitively, since we had given the extractor black-box access to the circuit Ck, instead of an obfuscation of Ck, it would have to invert the one-way function to obtain such a preimage. Indeed, since the oracle Ck answers any query e with fe(PRFk(e)), it follows from pseudo-randomness that finding a preimage of fe(PRFk(e)) is as hard as finding a preimage of fe(u), for a uniformly random u.

47 𝐶 2 ≡ 𝐶 1 Intuition Impossibility…: 𝑥 𝑘 𝑘 𝑥 𝑘 =𝑃𝑅 𝐹 𝑠 (𝑘) 𝑓 𝑘 ( 𝑥 𝑘 )
Compute the same function Extractor Adversary 𝑥 𝑘 𝑘 𝑥 𝑘 =𝑃𝑅 𝐹 𝑠 (𝑘) 𝑓 𝑘 ( 𝑥 𝑘 ) Prove that the obfuscation hides 𝑥 𝑘

48 Alternative adversary
Intuition Impossibility…: Extractor 𝑥 𝑘 𝑘 𝑥 𝑘 =𝑃𝑅 𝐹 𝑠 (𝑘) 𝑓 𝑘 ( 𝑥 𝑘 ) ≈ Extractor 𝑥 𝑘 Alternative adversary 𝑘 𝑓 𝑘 ( 𝑥 𝑘 ) hides 𝑥 𝑘

49 Intuition Impossibility…:
𝑃𝑅 𝐹 𝑠 𝑓 𝑘 𝑘 𝑓 𝑘 ( 𝑥 𝑘 )

50 Intuition Impossibility…:
Extractor 𝑥 𝑘 𝑘 𝑓 𝑘 ( 𝑥 𝑘 ) hides 𝑥 𝑘

51 𝑥 y 𝑥 y Program Obfuscation: Program Obfuscated program Obfuscation
Obfuscation: Makes code or program hard to understand /reverse engineer

52 𝑥 y 𝑥 y 𝑃 Program 𝑃 𝑜 Virtual Black-Box Obfuscation:
Obfuscated program Functionality: 𝑃 𝑥 = 𝑃 𝑜 𝑥 . Virtual Black-Box: “ 𝑃 𝑜 is not more useful than 𝑃 oracle”

53 [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01]
Obfuscator: [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] History: : No general solution. Obfuscation for simple functions: [C97,W05,CD08,CRV10,BC10,BR13] 2013: Candidate obfuscation for all circuits [Garg-Gentry-Halevi-Raykova-Sahai-Waters 13]

54 Contributions of Paper:
EOWF with bounded Auxiliary Info. OWF 𝑓: 0,1 2𝑛 → 0,1 2𝑛 Extraction from 𝐴 <𝑛 (no restriction on space or running time) Adversary 𝑧 ≪|𝑓(𝑥)| Explicit Extractor 𝑓(𝑖,𝑠)= PRG 𝑠 if 𝑖≠ 0 𝑛 𝑠 1 𝑛 if 𝑖= 0 𝑛 Possible Public-verifiable delegation for P Interpert 𝑠 as a program outputting 2𝑛 bits

55 Contributions of the Paper:
Generalized EOWF with unbounded Auxiliary Info. Generalized EOWF with bounded Auxiliary Info. Adversary Adversary 𝑧 ≫|𝑓(𝑥)| 𝑧 ≪|𝑓(𝑥)| Explicit Extractor Extractor Impossible Possible Indistinguishability Obfuscation Private-verifiable delegation for P