Study Group: Multinlinear Maps (II) - Application

Following on from last weeks study group on the construction of multilinear maps from ideal lattices (http://eprint.iacr.org/2012/610.pdf), this weeks study group, given by Essam and Gareth, was on applications of multilinear maps. One of the papers (appearing at Crypto later this year) this week can be found here:  http://eprint.iacr.org/2013/128.pdf. 

This paper, entitled "Attribute Based Encryption for Circuits from Multi-linear Maps", can be seen as something of a breakthrough for ABE, as previous results were significantly weaker.  We note that there is another concurrent work due to S. Gorbunov, V. Vaikuntanathan and H. Weeto appearing at STOC which achieves a similar result basing security on the Learning With Errors assumption.  At the time of writing this paper was unavailable.

Before going into details, let's talk about ABE.  Introduced by Sahai and Waters in 05, ABE comes in two distinct flavours:  key-policy and ciphertext-policy.  In the former,  secret keys are generated per boolean functions f from an allowable class of functions F.  Ciphertexts encrypting messages are associated with an attribute (assignment of boolean values) x.  Decryption of a ciphertext with a secret key sk_f is possible iff f(x) = 1.  Ciphertext-policy is the just the same with the role of key and ciphertext reversed. 

One of the main challenges has been to increase the depth of function f which can be evaluated.  Previously this was only possible for log(n) depth circuits, where n is the max length of an attribute.  The goal of this work is to realise ABE for any depth circuit.  They construct a KP - ABE and CP-ABE for any polynomially bounded depth circuit, though it should be noted that this work is only a proof-of-concept and is not necessarily intended to be efficient in any way.

They identify the main problem in previous constructions (in paticular those based on bilinear maps) as "backtracking":  lets say I decrypt a ciphertext with attribute x so I possess a secret key sk_f such that f(x) = 1.  Now consider an OR gate (in f).  When using pairings, a ciphertext which succesfully decrypts also allows us to learn information about a gate for which the ciphertext would not have succesfully decrypted since the pairing computation evaluates to the same thing on the OR gate.  Now if the gate for which said attribute would not evalute to 1 on, had fan-out higher than 1, we can potentially use this information to decrypt a ciphertext for which f(x) should evaluate to 0, but the additional information is used such that it evaluates to 1.

The beauty of multi-linear maps is that we can replace the single bi-linear computation with maps from groups e:G_i X G_j -> G_{i+j} such that 

e(g_i^a,g_j^b) = g_{i+j}^{ab}

Using what they call "move-forward-then-shift" they can avoid the backtracking issue.  Essentially, the difference lies in the fact we are now in a new group, whereas previously we applied the bilinear map once and the required value the adversary would need to cheat lied in the exponent coming from a bilinear map.   Thus backtracking is no-longer possible.