Multilinear Maps and Attacks Sanjam Garg (UC Berkeley) Based on works of Cheon, Coron, Garg, Gentry, Halevi, Han, Lee, Lepoint, Ryu, Stehle, Tibouchi 1 Outline Bilinear Maps: Recall Intuitively: Multilinear Maps Known results and Applications Definitions of Multi-linear Maps Classical Notion Our Notion GGH Construction and Attacks CLT Construction and Attacks 2 Cryptographic Bilinear Maps Bilinear maps are extremely useful in cryptography lots of applications [Joux00, BF01] As the name suggests allow pairing two things

together 3 Bilinear Maps Definitions Cryptographic bilinear map Groups and of order with generators and a bilinear map such that Instantiation: Weil or Tate pairings over elliptic curves. DDH is easy Given Given hard to get 4 Bilinear Maps: ``Hard Problem Bilinear Diffie-Hellman: Given hard to distinguish from Random Multilinear Maps [BS03] generalize

this concept. 5 Candidate Constructions of Multilinear Maps Approximate Multilinear Maps [GGH13, CLT13, GGH14] Various attacks [GGH13, CHLRS15, CGHLMRST15] Most obfuscation schemes unaffected New Multilinear Maps [CLT15] Very active area of research 6 Non-Interactive Key Agreement [DH76] Application 1 , Alice

Bob Extended to three parties by [Joux00] Mmaps would give solution for more than 3parties. [BS03] 7 Non-Interactive Key Agreement [DH76] 1 Application 1 1 = 1

Easy Application: Tri-partite key agreement [Joux00]: Alice, Bob, Carol generate and broadcast . They each separately compute the key More than 3-parties easy application. [GGH13] 8 Application 2 Software Obfuscation [BGIRSVY01, GR07, GGHRSW13] Obfuscation aims to make computer programs unintelligible while preserving their functionality. O(P) P Alice Bob 9 Obfuscation + Mmaps Applications

Witness Encryption [GGSW13] Attribute Based Encryption [GGHSW13] Functional Encryption [GGHRSW13, GJKS13, GGJS13, ABGSZ13,] Round Optimal Multiparty Secure computation [GGHR14] Deniable Encryption [SW13] Removing random oracles [HSW13a, FHPS13, HSW13b] Broadcast Encryption and Traitor-Tracing [GGHRSW13, BZ13, ABGSZ13] Impossibility results [BCPR13a,BP13,GK13,BCPR13b,KRW13,MO13,] Functional Witness Encryption [BCP13] Mmaps optimizations and extensions [CLT13,GGH13b,] Obfuscation optimizations and extensions [BCP13, ABGSZ13, BR13, BGKPS13, PTS13,] Pick your favorite primitive in cryptography Can it be improved? 10 Outline Bilinear Maps: Recall Intuitively: Multilinear Maps Results and Applications Definitions of Multi-linear Maps Classical Notion Our Notion

GGH Construction and Attacks CLT Construction and Attacks 11 Cryptographic Multi-linear Maps Definitions: Classical notion and our Approximate variant 12 Multilinear Maps: Classical Notion Cryptographic n-multilinear map (for groups) Groups of order with generators Family of maps: , where . And at least the ``discrete log problems in each is ``hard. And hopefully the generalization of Bilinear DH 13 Getting to our Notion Our

visualization of (traditional) Bilinear Maps Step by step I will make changes to get our notion of Bilinear Maps At each step provide Extension to Multi-linear Maps 14 Bilinear Maps: Our visualization 1 2

1 2 1 1 2 1 1 2 2 2 1

2 15 Bilinear Maps: Our visualization Sampling 1 2 1 2 1 1

2 1 1 2 2 2 1

2 It was easy to sample uniformly from . 16 Bilinear Maps: Our visualization Equality Checking 1 2 1 2 1 1 2 1 1

2 2 2 1 2 Trivial to check if two terms are the same.

17 Bilinear Maps: Our visualization Addition 1 2 1 2 1 1 2 1 1 2 2 2

1 2 3 1 18 Bilinear Maps: Our

visualization Multiplication 1 2 1 2 1 1 2 1 1 2 2 2

1 2 19 Bilinear Maps: Sets (Our Notion) 1 2

1 10 20 12 0 0 1 1 2 1

2 1 11 1 1 1 2 2 2

22 2 12 2 2 Level-0 encodings 20 Multilinear Maps: Our Notion Finite ring and sets ``level- encodings Each set is partitioned into for each : ``level- encodings of .

21 Bilinear Maps: Sampling (Our Notion) 1 2 1 10 20 0 0 2 1

1 1 1 2 2 should 1 1 I 1 2 2 efficient 2 22sample to 12 be

such that for a uIt may not be uniform in or . 1 1 2 2 1 2 It was easy to sample uniformly from . 22 Multilinear Maps: Our Notion Finite ring and sets ``level- encodings Each set is partitioned into for each : ``level- encodings of .

Sampling: Output for a u 23 Bilinear Maps: Equality Checking (Our Notion) 1 2 1 10 20 12

0 0 1 1 2 1 2 1 11 1

1 1 2 2 2 22 2 12 Check if two values come from the

same set. 2 2 It was trivial to check if two terms are the same. 24 Multilinear Maps: Our Notion Finite ring and sets ``level- encodings Each set is partitioned into for each : ``level- encodings of . Sampling: Output for a random Equality testing(): Output iff such that 25 Bilinear Maps: Addition (Our Notion)

1 2 1 10 12 20 0

0 1 1 2 1 2 3 1 1 1

1 1 2 2 2 22 11 13 2 12 2

2 26 Multilinear Maps: Our Notion Finite ring and sets ``level- encodings Each set is partitioned into for each : ``level- encodings of . Sampling: Output for a random Equality testing(): Output iff such that Addition/Subtraction: There are ops and such that: We have and 27 Bilinear Maps: Multiplication (Our Notion) 1 2

1 10 20 12 0 0 1 1 2 1

2 1 11 1 1 1 2 2 2 22

2 12 2 2 28 Multilinear Maps: Our Notion Finite ring and sets ``level- encodings Each set is partitioned into for each : ``level- encodings of . Sampling: Output for a random Equality testing(): Output iff such that

Addition/Subtraction: There are ops and such that: Multiplication: There is an op such that: such that We have . 29 Bilinear Maps: Noisy (Our Notion) 1 2 1 10 20 12

0 0 1 1 2 1 2 1 11

1 1 1 2 2 2 22 2 12 All operations

are required to work as long as ``noise level remains small. 2 2 30 Multilinear Maps: Our Notion Discrete Log: Given level- encoding of , hard to compute level-- encoding of . n-Multilinear DDH: Given level- encodings of and a level-n encoding T distinguish whether T encodes or not. 31

Outline Bilinear Maps: Recall Intuitively: Multilinear Maps Results and Applications Definitions of Multi-linear Maps Classical Notion Our Notion GGH Construction and Attacks CLT Construction and Attacks 32 ``Noisy Multilinear Maps (Kind of like NTRU-Based FHE, but with Equality Testing) 33 Background We work in polynomial ring E.g., ( is a power of two) Such is irreducible over , 34

GGH13 Construction We work in polynomial ring E.g., ( is a power of two) Also use Public parameters hide a small and a random invertible (large) Let be the ideal generated by g, also has lattice structure is required to be Small and invertible in should be a large prime is not too large The ``scalars that we encode are cosets of (i.e., elements in the quotient ring ) 35 GGH13 Construction

Small defines a principal ideal over 1 0 + and 2 0 1+ 2+ n n o tiliocati 0 i dp d ti Aul M

0 1 1 12 [ ] 12 22 1 short then,

If , are both the has thehas form , form , where isstill short and 1 A random (large) 2 [ ] 2

2 should have small coefficients 36 GGH13 Construction (in general) In general, ``level-k encoding of a coset has the form for a short Addition: Add encodings as long as || Multi-linear: Multiply encodings to get an encoding of the product at level as long as ``Somewhat homomorphic encoding Sampling and equality check? 37 Bilinear Maps: Sampling (Our Notion)

1 2 1 10 20 0 0 2 1 1 1 1 2

2 should 1 1 I 1 2 2 efficient 2 22sample to 12 be such that for a uIt may not be uniform in or .

1 1 2 2 1 2 It was easy to sample uniformly from . 38 Sampling Sampling: Sample small , but larger than then encodes a random coset. Why should this work? -- vector with tiny coefficients 39

Encoding this random coset Publish an encoding of 1: Sampling: If (wide enough), then encodes a random coset. Dont know how to encode specific elements Given this short , set is a valid level- encoding of the coset Translating from level to : 40 Equality Checking Do encode the same coset? Suffices to check - encodes . Publish a (level-k) zero-testing param h is ``somewhat short (e.g. of size ) To test, if encodes , compute = = (output yes if ) 41 Equality Checking

Correctness I Do encode the same coset? Suffices to check - encodes . Publish a (level-k) zero-testing param h is ``somewhat short (e.g. of size ) To test, if encodes , compute = = (output yes if ) Correctness: if (or, ) Problem: may not be small Solution: is small, is same as in 42 Equality Checking Correctness II Do encode the same coset? Suffices to check - encodes . Publish a (level-k) zero-testing param h is ``somewhat short (e.g. of size ) To test, if encodes , compute = = (output yes if ) Correctness: if Assume then both and are

Hence in Implies divides or . 43 re-randomization Re-randomizatonThis gets us statistically 1 0 0 0 0 close to the actual

distribution [AGHS12,AR13]. And to re We need to re-randomize the encoding, Need to break 1 randomize these simple algebraic relations But then this as well. 0 1 0 0

0 44 The Complete Encoding Scheme Parameters: , , and Encode a random element: S Re-randomize u (at level 1): Zero Test: Re-randomization not needed for applications like obfuscation. Map to level(by multiplying by for appropriate j) Check if is small 45

Variants Asymmetric variants (many zis), XDH analog ,, Partially symmetric and partially asymmetric 46 Discrete-log attack , , and Complete Break: To find or Without the - essentially the NTRU problem Discrete-log Given , find , where is Weak discrete-log is where is allowed to be large but still . 47 Weak Discrete Log Attack brings the encoding multiplied with zero-test to the highest level

Can break DLIN but not MDDH. Extended to some other settings without zeros [CGHLMRST15] Extended to total break given zeros [Hu-Jia15] 48 Outline Bilinear Maps: Recall Intuitively: Multilinear Maps Results and Applications Definitions of Multi-linear Maps Classical Notion Our Notion GGH Construction and Attacks CLT Construction and Attacks 49 The [CLT'13] Construction Working mod a composite Assuming that factoring is hard The s are all the same size Extensive use of CRT representation Public parameters hide s

Plaintext values are -vectors Operations () are component-wise 50 The CLT13 Construction 10 + and 2 0 , 0 is the element mod with this CRT decomposition 0

A random (large) 51 The CLT13 Construction 1 0 20 , 12 0 n o n

ti o a c tili i 0 dp ti d l Au M 1 1 [ ] 12 22

2 [ ] 2 1 short IfIf and and ss are are short then, then, has thehas form

, the form , where is1still short and 2 A random (large) 52 The CLT13 Construction (in general) In general, ``level-k encoding of has the form for a short , Addition: Add encodings as long as || Multi-linear: Multiply encodings to get an encoding of the product at level as long as ``Somewhat homomorphic encoding

Sampling and equality check? 53 Sampling/Encoding/ Re-randomization Sampling at level-0: Similar to re-randomization from GGH Public parameters include level-0 encodings of random plaintext elements Taking random linear combinations gives a level-0 encoding of a random plaintext element. Encoding at higher level: Include encoding of 1 Re-randomization: Publicly include encoding of 0s 54 The [CLT'13] Zero-Test Let , For any we have The CLT zero-test parameter is 55 The [CLT'13] Zero-Test

An encoding of at level has the form , and therefore And the sum as well. 56 The [CLT'13] Zero-Test Encoding of a non-zero has for in some components This component does not cancel the So we have some large summands Zero-testing: multiply by and check size 57 Zeroing Attacks on CLT13 Initially GGH13 attacks did not seem to extend to [CLT'13] [Cheon-Han-Lee-Ryu-Stehle'15] extend these attacks breaking [CLT'13] in case when encodings of zero are provided

58 Cheon et al. Attack An encoding of looks like for a short , For short denote it as: Finding the s means breaking the scheme Here since so the value are unreduced If is an encoding of 0 (at top level) then Zero-test on gives where is independent of the computed value is unreduced (only because encoded 0) 59 Cheon et al. Attack Attack Encodings: , Encoding of 0: Filler encoding: We get a level- encoding

Similarly 60 Cheon et al. Attack Z Or Unreduced mod N Similarly zgives Or 61 Cheon et al. Attack Extending to multiple values has rows consisting of encodings of 0 is the target encoding along the diagonal has columns of filler encodings Zero-test on Similarly, 62

Cheon et al. Attack G we compute Eigenvalues of are Enough to violate security of many assumption Can be used to factor N as well! Extensions of attack [CGHMMRST15] Strengthened scheme that resists these attacks [CLT'15] make zero-test ``less linear 63 Summary of current constructions Ideal Lattice based [GGH] Not for obfuscation! Weak-discrete Log Attack given zeros [GGH13] Quantum Attack [CDPR] and sub-exponential classical attack Extend weak-discrete log attack to some other settings without zeros [CGHLMRST15] Extend weak-discrete log attack to total break given zeros [HuJia15] Over the integers [CLT]

Quantum Attack - relies on hardness of factoring Total break given zeros [CHLRS15] Extend to some other settings without zeros [CGHLMRST15] A new fix [CLT15] also for GGH Graph Based Mmaps [GGH] Open to investigation? 64 Conclusion and Current Landscape Multilinear maps - very useful and currently a very active area of investigation Attacks break many hardness assumptions and several schemes But certainly not all (e.g. most obfuscation schemes are unaffected) Break and repair situation Better understand what does not work Theoretical understanding on the hardness of what we

are assuming is missing 65 Thank You! Questions? ? 66