CRYPTO 2012: Day Three

The maybe most-anticipated talk of the conference was also the one with the shortest and most generic title: Public Keys. The authors collected more than 11 million public keys openly accessible on the Internet, and searched for duplicates and common factors of RSA moduli. As for duplicates, they found only a few ElGamal and DSA keys, but 270000 duplicate RSA moduli, of which not all seem to be used by unrelated entities. For the distinct moduli, the authors managed to factorize 10 of 2048 bits and 13000 moduli of 1024 bits, of which 5000 are still in use, in a few hours on a laptop. Putting the broken moduli in graphs shows clusters representing different vendors. Most notable, an IBM product generated 687 keys using all possible combinations of only 9 primes. As a conclusion, the authors considers RSA to be riskier than other public-key cryptosystems that do not offer the possibility of breaking keys by GCD computations. The speaker also mentioned the idea of a central directory for public keys, which would allow the testing of new public keys. However, this does not prevent the actual problem of keys becoming compromised by the same randomness being available to another entity. Consequently, this would only help to take the unavoidable action of revoking all public keys generated by such a faulty algorithm at an earlier point in time. After the presentation, it was pointed out in a comment that weak PRNGs affect all cryptosystems equally because one can always try to replicate the key generation given access to the algorithm. Another comment proposing a public directory for private keys instead of public keys was met with amusement. On a side note, the somewhat controversial earlier title of the paper was shown to be a tongue-in-cheek suggestion by Adi Shamir.

In the session on secure computation, it was interesting to see how three state-of-the-art MPC schemes encounter the same problem – one could say the core problem of MPC – and tackle it in three different ways. This problem is how to securely multiply two secret numbers. All three schemes involve the generation of so-called multiplication triples with information-theoretic MACs during a pre-processing phase where the inputs to the MPC are not know yet. Multiplication triples are secret sharings of (a,b,ab), where a and b are random numbers. It is well-known that, due to the properties of linear secret sharing, multiplication triples suffice to compute any arithmetic or binary circuit in MPC, depending on the field of the secret sharing scheme. The scheme can be made secure against active adversaries if the triples are authenticated by MACs, which are essentially a secret sharings of the product of the values with a MAC key. In conclusion, the core problem appears twice, first computing the triples and second computing the MACs. Two papers in the session solved the problem with computational security, the one by Damgård et al. using a reduced version of FHE, called somewhat homomorphic encryption, the one by Nielsen et al. using oblivious transfer to generate binary triples. While the latter method is not entirely new, a novel way of amortizing OT allows to greatly speed up the pre-processing phase. In contrast, the contribution of the paper by Eli-Sasson et al. is an improvement of MPC with unconditional security against active adversaries. It uses a clever secret-sharing of per-party MAC keys that allows to compute a secret sharing of the MACs locally.

Eventually, the day was concluded by the traditional beach barbecue.