Second Priority Ideas Blog

A New Cryptographic Assumption

Bilinear maps have been one of the weapons of choice for solving complex cryptographic problems in the recent past. They have lead to a number of algorithms with very interesting security properties, such as proxy re-encryption, searchable encryption and homomorphic encryption. Unfortunately bilinear maps can only be applied once, i.e. the designer can use them for one trick and then it's over. So there are many schemes out there that use bilinear maps for different purposes. Now, I think it would be nice to be able to combine those schemes, but there's nothing like a trilinear map.

I've been searching for alternative cryptographic assumptions that can be used in order to combine the features of two of those schemes that use bilinear maps. I haven't been all that successful, but I came across the following idea of combining RSA and bilinear maps. Let n=pq be a composite of two large primes. Then construct the bilinear maps over fields of size n. I denote h(a, b) the bilinear map (since my blogging tool has no embedded latex for \hat{e}). It should be hard to solve the following problem:

Given x^e, y^e and e, compute h(x, y)^e

Note that x^e and y^e are RSA ciphertexts. Computing h(x, y)^e is as hard as decrypting RSA, but given h(x, y)^e one can verify it like a signature, since h(x^e, y^e) = (h(x, y)^e)^e. I can construct nice things using based on the assumption that solving this problem is hard, but there is a draw-back. One can use it only with a single e for any n, since otherwise the common modulus attack on RSA makes the problem trivial. This limits most of the things I came up with and I have given up using it for now, but now I am publishing it here. Maybe somebody else can use it. If you do, please let me know.