Crypto Day 3, Session 10

With some delay due to a busy BBQ schedule, here is a quick report of yesterdays last session on symmetric schemes. It started with a talk by Jooyoung Lee on the collision security of Tandem-DM. Since I'm a coauthor on this paper, I obviously know it quite well. The bottom line is that previous proofs of the collision security of Tandem-DM were flawed and that we gave a whole new proof, relying on a nice technique. For details please see the paper (and for those interested, there is an interesting follow up related to the preimage security of Tandem-DM accepted for Asiacrypt'11).

The second talk of the session was by Nathan Chenette on order-preserving encryption. This type of encryption was formally introduced at Eurocrypt'09 by a superset of the current authors. As the name indicates, the idea is that if for two different plaintexts it holds that x < y, then it also holds for the ciphertexts that E_K(x) < E_K(y). This notion is useful for efficient range checking, but unfortunately it immediately implies that the encryption scheme cannot be IND-CPA secure. Originally, a superset of the authors proposed a security notion by comparing the encryption scheme with an ideal order preserving function. While in a way this is the best one can hope for, the object 'ideal order preserving function' was not at all well understood. Chenette and his coauthors shed light on these functions, for instance by examining how one-way these functions can be. The analysis required mathematics of a nature that one not often encounters in crypto talks or papers. An interesting topic and it felt like there was still more to be said.

Kan Yasuda gave a new blockcipher-based MAC inspired on PMAC. His construction uses a single blockcipher call per message block to be authenticated, yet it achieves (unforgeability) security up to 2^{2n/3} queries. To me this result was rather surprising: firstly, from a technical perspective the PRP-PRF switching lemma cannot be used (as it breaks down at around 2^{n/2} queries) and secondly, it shows that there is also a considerably gap between the collision resistance and the weak collision resistance of blockcipher based compression functions. It makes me wonder how far one can go with weak collision resistance...

The final talk of the session was by Keelveedhi who discussed the key-dependent message security of authenticated encryption (AE). He pointed out that there is a mismatch with the theoretical treatment of AE and its actual use in practice, where typically the randomness is replaced by a nonce and the message is extended by a header that needs to be authenticated but not encrypted. Since the nonce can be either random or adversarially chosen (without repeats) and both message and header could be key dependent, several different notions occur. It turns out that security cannot be achieved if the nonces are adversarially chosen or if the header is key dependent. For the remaining scenario, random nonces and key-independent header, there is a relatively simple KDM-secure scheme in the ROM.