This week a large part of the MPC community is meeting in Aarhus for a workshop on Theory and Practice of Secure Computation. The local Crypto Group is going to blog live(ish) about all the talks at the workshop. As we are blogging live, our posts might contain inaccuracies and errors. Please write us if you find any!
The MPC workshop in Aarhus kicked off with a talk by Sanjam Garg on Multilinear Maps. The talk was divided into three parts: background on bilinear maps, definitions of multilinear maps and the concrete candidate construction of Garg, Gentry and Halevi.
At first background on bilinear maps was covered. We saw a number of applications of bilinear maps in cryptography, including non-interactive key agreement for 3 players by Joux’00. It was evident that a k-linear map implies non-interactive key agreement for k+1 players. Also the bilinear Diffie-Hellmann assumption was covered and we saw that standard DDH is easy in bilinear group.
Next we moved into the realm of multilinear maps and the definition from [BS03] was presented. This definition includes encoding procedure, uniformly sampling, possibility of equality testing and operators for addition and multiplication. Sanjam stressed that this definition is not what they achieve in their construction, but a relaxed version. In their construction each element has an associated noise (much like FHE) and this noise grows as one performs the addition and multiplication operations. As long as this noise stays under an a priori bound however, everything works out. This is why for most applications the approximation multilinear maps construction is sufficient.
In the concrete construction we work in two rings R = Z[x]/f(x) for an irreducible polynomial f(x) and R_q where the coefficient are in Z_q for a large q. In the setup of the scheme two trapdoors g \in R_q and z \in R_q^* are chosen once and for all. We let I = <g>, i.e. the ideal generated by g. The scheme now encodes elements of the quotient ring QR = R/I using z. Next Sanjam walked the audience through how this scheme fulfills the above requirements of a multilinear map, with some relaxations because of the noise. Finally a notion of re-randomization is introduced which is necessary to achieve security of the scheme. This included adding a large number of encoding to 0 to the public parameters which was then added to an encoding.
Lastly a brief overview of the security of the scheme was covered and it was mentioned that an adversary that only adds, subtracts, multiplies or divides pairs of elements an cannot break the scheme. This notion of security is similar to proofs in the generic group model.
Garbled Circuits Old and New
The talk focused on achieving Reusable Garbled Circuits(RGC) from Attribute-based Encryption(ABE): Yao’s original construction only gives you a Garbled Circuit (GC) that you can evaluate once (without compromising security). If you give the evaluator two different garbled inputs, mix-and-match attacks let the security break down. Moreover, Vinod explained other interesting and related notions such as Compact Garbled Circuits, which I will not discuss here.
The talk started with an introduction into ABE, which basically is a Public Key Encryption scheme with an additional (possibly public) attribute vector. The secret key is now tailored to a circuit C such that the decryption reveals the encrypted value if C evaluates to 1 during decryption. A particular flavor of ABE is called Two-Input ABE, where you encrypt to two values and obtain either of them during decryption (it’s like Rabin OT vs. 1 out of 2 OT). In order to construct such an ABE, one can use the Learning With Errors (LWE) assumption as follows: For a single use symmetric key ABE, one can let the secret key be a GC and the encryption of the message m be the input labels of the GC chosen according to the attribute vector, plus the xor of the output label and m. Now to make a full-fledged ABE out of it, one replaces the labels with functions, and at each gate we distill a new function out of the input functions. To actually implement that, these functions will be LWE samples (for fixed matrices), and the “distiller” at each gate applies linear transformations to these samples. Here you need some additional work to make the matrices “small” in order to bound the noise growth throughout the evaluation. To make it deterministic, one can use Learning With Rounding instead.
Afterwards, Vinod presented how to go from this ABE to a RGC that is only correct (without giving privacy). Here we give the evaluator the circuit C plus an instance of a Two-Input ABE, where the secret key is tailored for the circuit C. An input x is encoded as a ciphertext with two random values as messages and the input x as the label, and circuit evaluation consists of computing C(x) together with decrypting the correct value using the Two-Input ABE as the “proof of correctness”.
To get to full RGC, one then uses Fully Homomorphic Encryption(FHE) to encrypt everything and achieve privacy. But now the output of the evaluation is encrypted under the FHE. The solution now is to use a standard GC to give away a one-time decryption circuit for the output values of the encrypted weak RGC.