Monday, May 16, 2011

Eurocrypt '11 - Tallinn - Day One

We started off with the best paper at the conference - and a strong candidate for "best talk" too!
Efficient Authentication from Hard Learning Problems looked at how you could do authentication in a RFID tag. Forget Moore's Law, this is state-of the art technology and we're talking about a few thousand gates total. Even AES is not an option, so the authors developed an authentication protocol based on the "Learning Parity with Noise" problem (LPN), building on the HB scheme and adding security against active adversaries.
The basic idea is that prover and verifier share a secret vector, the verifier picks a random challenge vector and the prover replies with the inner product of the challenge and the secret XOR some biased random bit - this can fail for both honest and dishonest provers but the difference in failure probabilities allows you to construct a secure protocol through repetition.

Next up, a variant of NTRU which comes with a proof that it really is as hard as finding short vectors in lattices and a great introduction to the field of lattice-based cryptography by Phong Nguyen (invited talk).

The afternoon was devoted to side channels and (fully) homomorphic cryptography, where among others we saw fast(er) implementations of pairings, AES and Gentry's FHE scheme.
One highlight on side channels: A Formal Study of Power Variability Issues and Side-Channel Attacks for Nanoscale Devices.
As processsors get smaller, variability between different chips - even of the same series - starts to influence measurements like power traces, so you can't measure one chip to construct a hypothesis then test it on another as you'd like - the more exactly your hypothesis fits the first chip, the worse variation will make it on the second. The authors showed how you get better results by aiming for robustness rather than precision.
As an aside, chip manufacturers may be able to thwart side-channel attacks better by putting less effort into reducing variability.

No comments:

Post a Comment