# home / posts

## Open Problem (Theoretical Cryptography): Simultaneously Achieving Both Anonymity and Homomorphism in Additively-Homomorphic IBE

Before I delve into this open problem, I want to mention that I'm happy I have the new features that I've recently added to this blog (see my previous two posts) available to me such as LaTeX-style theorem enviornments and bibliography/references because I think I'm going to need them here, although I'm just going to start writing and see what happens.

Now it is worth pointing out that the open problem here is most likely not of much general interest, even in cryptography, since it is very narrowly-focused and theoretical. It relates to a primitive known as identity-based group homomrophic encryption (IBGHE) which is defined in my PKC paper [1] along with some of my other papers such as [2] and [3]. Basically, IBGHE is identity-based encryption that is homomorphic for some group operation and the ciphertext space for every identity forms a group. Moreover, the decryption function is a group homomorphism between the ciphertext group and the plaintext group. The aforementioned papers describe some of the applications of group homomorphic encryption (GHE).

I would be satisified with any progress in this direction. Even when indistinguishability obfuscation (iO) is employed, we still do not know how to solve this problem. In fact, it is proved in my paper [2] that assuming iO, given public-key GHE for some group, we get IBGHE for the same group. However, the transformation does not give us anonymity. I have an outline of a paradigm for solving this problem that makes use of the result in [2] from iO. The paradigm I have in mind is as follows. As part of the public parameters, we have an obfuscated program that maps an identity to a public key in some multi-user system with public parameters. The public keys in a multi-user system share the same set of common public parameters - think of the generator $g$ and modulus $p$ in ElGamal as the common public parameters, except ElGamal is of no use here since it is only multiplicatively homomorphic. Nevertheless, ElGamal serves to illustrate another property that this paradigm requires, namely that the multi-user system supports key privacy where key privacy can be viewed as the analog to anonymity in the identity-based setting; that is, the ciphertexts in the multi-user system do not reveal the public key they are associated with, which is the case in ElGamal. I'm using the term multi-user system in a broad sense here permitting both the case where we have a trusted authority and the case where we do not. In the former, the public parameters are generated by a trusted authority with a backdoor (master secret key) such that the trusted authority can decrypt any ciphertext. In our paradigm, the public parameters of the multi-user system will be generated by the trusted authority of the IBE scheme and published as part of the IBE scheme's public parameters. So we need the multi-user system to be key-private and additively homomorphic, where the homomorphic operation can be computed without knowing the public key associated with a ciphertext. Then additionally assuming iO, we get a solution to the problem, albeit with strong assumptions.