Crypto 2013 is going to be a mammoth conference, more papers than ever before; meaning the dropping of the Tuesday afternoon off AND an extension into Thursday afternoon. The conference is also co-located with CHES; so the number of attendees is also large.
The first session is on Fully Homomorphic Encryption and Lattice based crypto; probably the most active area in crypto from the last few years.
The session started with a talk by Alperin-Shefiff et al on Practical Bootstrapping in Quasilinear Time. Bootstrapping is a means to turn a SHE scheme (one which can evaluate circuits of bounded depth) into an FHE scheme (one which can evaluate circuits of aribitrary depth). The talk outlined two techniques for bootstrapping one for unpacked ciphertexts, and one for packed ciphertexts. The latter technique used the ring-switching techniques presented by GHPS in SCN 2012. The basic idea is (as always) to homomorphically evaluate the decryption circuit.The main trick is a way of ring switching from one ring to another, which is not a subring. This is done by going "via" the compositum. However, to avoid a complexity blowup this is done by a series of smaller steps. The main problem remains however using a circuit for rounding from integers mod q to integers mod 2, which is a high degree circuit.
The second talk was a paper by Micciancio and others on Hardness of SIS and LWE with Small Parameters. The SIS problem is to invert the function Ax=b mod q given a matrix A with n rows and m columns (m>n) and b; where one is told in advance that x is "short". The LWE problem is to solve Ay+x=b mod q where the unknowns are x and y, but now A is an m times n matrix, and x is chosen from some distribution of short vectors. The hardness of these problems is usually related to how one selects the distribution from which you choose x. Usually one selects the distribution to be discrete Gaussians (for LWE) and the relative large sizes of q (SIS). This talk analysed these problems from the point of view when one selects the vectors with small uniform distribution and for smaller values of q than for previous works. In terms of SIS they show that if you can break SIS for small q (suitably defined) then you can break SIS for problems with moduli a power of q. The authors also show that LWE is hard if the errors are chosen from a non-Gaussian distribution with small errors (in particular binary vectors). However, the results are only true when one restricts the dimension/modulus to a certain range (one cannot after all have a free lunch).
The third talk on Lattice Signatures and Bimodal Gaussians, was by Ducas et al. This paper looks at the problem of constructing lattice based signatures; by extending prior work of some of the authors on a Fiat-Shamir style construction which used rejection sampling. Rejection sampling is used to ensure the distributions in the underlying ZK-proof are indistinguishable from those one constructs in the simulator. The paper presents a more efficient scheme than previous ones by optimizing the rejection sampling step, by selecting the distribution to be a bimodal, as opposed to standard, Gaussian.
Then Alwen et al presented their work on Learning with Rounding Revisted: New Reduction, Properties and Applications. LWR is a like LWE in that LWE tweaks the low order bits of Ax by adding in an error e; whilst LWR simply removes the low order bits. It was previously shown that LWE hardness implies LWR hardness; but with various restrictions on the parameters. In particular the modulus-to-error ratio would have to be very small (amongst other problems).
The final talk of this session was by Gentry et al on Homomorphic Encryption From Learning With Errors. The method presented here uses ciphertexts which are matrices, the homomorphic addition and multiplication becomes just adding or multiplying the matrices. The main benefit being that one does not need the expensive relinearisation step for multiplication. When combined with efficient matrix multiplication techniques, this becomes the faster asymptotic SHE scheme (although in practice it is not as fast as the other schemes). Since the public key does not need to contain any information needed for evaluation (i.e. one can perform homomorphic operations without needing the public key), this means one can construct ID based homomorphic schemes.
The basic idea is related to eigenvalue/eigenvectors of matrices. When you multiply/add matrices you end up multiplying/adding the eigenvalues (which represent the messages), with respect to the same eigenvector (which represents the secret key). The problem is with this basic idea is that finding eigenvectors of matrices is easy. To fix this issue we simply LWE'ify it by adding in some errors; so one is finding approximate eigenvectors. i.e. we have A x = u x + e, with x called an approximate eigenvector. To make this work (i.e. preserve homomorphic properties) one has to control the noise; this is done by restricting the message space to {0,1}, by restricting to NAND gates, and by having a procedure to "flatten" the product of matrices out so that it's coefficients are small. This flattening can be done obliviously of the public key.
No comments:
Post a Comment