Unclonable Cryptography and Copy Protection Research Insights

Unclonable Cryptography with Unbounded Collusion & Impossibility of Hyperefficient Shadow Tomography (eprint.iacr.org/2023/1841) Alper akan1, Vipul Goyal2,1 1Carnegie Mellon University, USA 2NTT Research, USA

No-Cloning Principle |? [Wooters, Zurek 82] [Dieks 82] |? Unknown state |?

Copy-Protection | ???????(?) For all ? with overwhelming probability | Correctness: ? = ?(?) ????( ,?) Implication: Can repeatedly use the state for various inputs (Gentle Measurement [Aar 16])

Copy-Protection Security (Simplified) ????(1?) ? P | ???????(?) | 1 | 2 Test wrt ? Output 1 if both pass Pr ??? = 1 ????(?)

Unclonable Decryption Keys (Simplified) ???(??1) | 1 ?1 | ???????(??) At most +negl prob. ?1=??1 ?2=??2 ???(??2) ? | 2 ??,?? ?????(1?) ?2

Copy-Protection Security (Multiple-Copy Setting) Copy-Protection Security (Full Security) ???(??1) Models users who collide or user who buys multiple copies | | ???????(??) | 1 | 2 ?1 ???(??2) ???????(??) ?2 . . . ??=??? for all ? [? + 1 ] . . . At most +negl prob. . . . ? ??,?? ?????(1?) ???????(??) ???(???) | ? | | ?? ???(???+1) ??+1 ? + 1 ? keys ? + 1 pirates

Previous Work Folklore: Only unlearnable programs can be copy-protected Aaronson et al [ALLZ 21]: 1 2 copy-protection for any unlearnable program using ideal classical oracles Coladangelo et al [CLLZ 21]: 1 2 copy-protection for PKE and PRF keys, from subexp iO + LWE Ananth-La Placa [AL 21]: Even some unlearnable programs cannot be copy-protected in the plain model Liu et al [LLQZ 22]: Bounded collusion q-way repetition of CLLZ 21 q q+1 copy protection for fixed q for PKE, PRF, signature keys, from subexp iO + LWE

Attack on Previous Scheme Users flip a coin, measure their program in computational basis or Hadamard basis. Post measurement results (which are classical) online Measurement results are anonymous, cannot get caught! For CLLZ: ~2 users For LLQZ: ~q users (q fixed at setup, params grow linearly with q) sufficient to obtain a classical pirate program that anyone can download!

Our Results 1) There exists {PKE, PRF, Signature, FE} with unbounded collusion-resistant copy-protected keys assuming subexp secure iO + LWE 2) There exists unbounded collusion-resistant copy-protection scheme for any unlearnable functionality in classical oracle model 3) Poly. time shadow tomography is impossible, - Assuming subexp secure iO + LWE, OR - Unconditionally, relative to a quantumly accessible classical oracle

Coset State [CLLZ21, VZ21] 1 ? = 1 ?, ? |? + ? where random ? ?2 ?,dim ? = ?/2 ?,? ?2 |?? ? 4 2 ? ? ? ?1? = 1 iff ? ? + ? ?0? = 1 iff ? ? + ? Properties: Can efficiently generate the states Canonical element of Can be computed efficiently using ? ?|?? ? = |(? )? ? ? + ?: ????(?) ?

Monogamy-of-Entanglement [CLLZ21, CV22] ? | 1 ? ? |?? ?? ?0, ??(?1) At most negl. prob. ? ?? + ? ? ?? + ? ? | 2 Sample ?,?,? ? ?

[CLLZ21] Construction Encryption )? [?] ?? = (??,??,?? 1) Sample ? 2) Output ?,??(???) ???????(??) |??,??,?? ???(?1, ,??) ?,?1 ?)? [?] ?? = (?0 ?,?1 ?)? [?] x Hardcoded: m, ?,(?0 1) For ? [?] check if ?? 2) Output ? if checks pass ??? = 1 Given 2 copy-protected keys, measure one for b=0 and one for b=1 ?1= ?? ? [?]and ?2= ?? ? [?] ?1,?2 sufficient to decrypt anything Similar attack for LLQZ 22: Given ? + 1 keys, we will get one of the states twice

Solution Step 1: Pseudorandom Coset States Existing coll. res. states (Haar random/PRS) cannot be classically verified [Kre 21, LLQZ 22] Poly. many different coset states will have collusion A poly. size key can only have information about poly. many different random coset states Use PRF to compress information about exponentially many coset states and fit it into poly. size public key ?? = ? ?? ??,|??,?? ? [?] where (?? ??,?? ??, ?? ??) = ?(?,??) ???????(??) ??,?? ?? ?? = ??(??) where ??( ?? ? ?,?,??) emulates ??? ? for ??

Collusion-Resistant Monogamy-of-Entanglement ??1 |??,?? ? [?] ??1,?? ??1 ??1 ?? ??2 ?1, ?? ??2 |??,?? ? [?] ? [?] | 1 ??2,?? ??2 ?? + ?? ?? ?? ??? if ?1 ?= 0 ?? ?(?? ?? ? [?] . . . ?? ) + ?? ?? ?? . . . At most negl. prob. if ?1 ?= 1 ?? ?2, ?? ? ? [?] | 2 Sample ? ?? ? [?] ??? ?? + ?? ?? ?? ??? if ?2 ?= 0 ??? |? ? [?] ???,?? ??? ?,?? ?? ) + ?? ?? ?? ?(?? if ?2 ?= 1 (All different ??)

Construction So Far ?? = ? Encryption ?? ??,|??,?? ??) = ?(?,??) ? [?] ???????(??) 1) Sample ? 2) Output ?,??(???) ??,?? ?? ??,?? ??, ?? where (?? ?? = ??(??) where ??( ?? ? ?,?,??) checks for membership in ?? or (?? ???(??,?1, ,??) Hardcoded: m,?,?? 1) Check if ???1, ,??,?,?? = 1 2) Output ? if check passes ??+ ?? (if ??= 0) ?? (if ??= 1) x ??) + ??

Challenges To reduce to coll. res. MoE: Enforce them to copy one of the keys: All pirates could be using different id, but we need to 2 pirates with same ?? Even then, need to identify which coset state tuple the pirates are using to find that ?? Also: Adversaries not necessarily running ??? to decrypt since we are using iO: They could be learning m through other ways

Solution Step 2: Identity-Based Encryption With each key also give IBE key for id Ciphertext program (after verification for id) also encrypt message under id Now adversary will have k IBE keys for ??1, ,??? Pirates must decrypt IBE ciphertext: Must use one of these ids by IBE security k id values and k+1 pirates: Two pirates will use the same ?? {??1, ,???} Finding ?? also easier: Only k choices, can guess

Construction ?? = ? Encryption ?? ??,|??,?? ??) = ?(?,??) ? [?] ???????(??) 1) Sample ? 2) Output ?,??(???) ??,?? ?? ??,?? ??, ?? where (?? ?? = ??(??) where ??( ?? ? ?,?,??) checks for membership in ?? or (?? ???(??,?1, ,??) Hardcoded: m,?,?? 1) Check if ???1, ,??,?,?? = 1 2) Output IBE.E??(?,??) if check passes ??+ ?? (if ??= 0) ?? (if ??= 1) x ??) + ??

(Very) High Level Security Sketch Assume adversary succeeds Each pirate succeeds with honest ciphertext distributions They necessarily fail with ciphertext programs that terminate if input id > id for ?? = 2? (since this can never be satisfied) There is a success jump point between 0 and 2? In fact, they will fail for the case ?? > ??? since they do not have the IBE key! There is a success jump point between 0 and ??? Jump points can only be at ??_? : Otherwise the program output only changes between two secure IBE ciphertexts (i.e. adv. has no key) indistinguishable!

By pigeonhole, 2 out of k+1 pirates will have the same jump point since there are k possible jump points Predict two pirates randomly: Only 1/?2 loss Predict jump point randomly: Only 1/? loss Test the two pirates around the jump point If guesses are correct, there is indeed a jump Use compute-and-compare obfuscation to extract vectors Gives an adversary for coll. res MoE game!

Other Primitives FE: Associate functional key for f with f || id IBE-Encrypt f(m) under identity f || id inside ciphertext program PRF, Signature: Hidden trigger technique and a new prefix puncturing argument - technical All unlearnable programs: Use pseudorandom coset states, but no need for IBE due to ideal oracle

Shadow Tomography Introduced by Given quantum distribution (i.e. mixed state ?), impossible to learn with poly. many copies Shadow tomography (Aaronson [STOC 18]): Can learn a circuit C such that it predicts behaviour of ? wrt to fixed exponentially large set of measurements ? = {??}? using poly. copies! Can we learn it in poly. time? Previous ([AK 07, Aar 18]): Impossible relative to a quantum oracle

Suppose possible: Query for some number of keys Learn wrt to set of measurements induced by honest decryption procedure on all possible ciphertext strings Output C to each pirate! By shadow tomography guarantee, using C, can predict behaviour of an honest key on honest decryption procedure i.e., can decrypt! This work: Hyperefficient shadow tomography impossible assuming iO + LWE Implication: Any hyperefficient shadow tomography algorithm (quantumly) breaks iO or LWE

Eprint 2023/1841 Questions?