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).
It is an open problem to construct an IBGHE that is simultaneously anonymous and homomorphic for addition. There are only two IBGHE schemes that support modular addition to the best of my knowledge, namely my XOR-homomorphic variant of the Cocks IBE scheme in [3] and my IBGHE scheme from [1] that is homomorphic for addition modulo smooth square-free integers. Now Joye discovered that the Cocks IBE scheme itself is XOR-homomorphic [4] but the scheme is not an IBGHE since the ciphertext space with the homomorphic operation forms a quasigroup and not a group. Some readers might wonder about schemes that are considered multiplicatively homomorphic, which allow addition in the exponent, and question why we do not classify them as IBGHE schemes for addition. The reason is that the corresponding additive group has exponential order and decryption can only recover messages using Pollard's lambda algorithm that are less than some polynomial bound so the valid message space does not form an additive group. Now the two IBGHE schemes supporting modulo addition that we are aware of are not anonymous (see my post on breaking anonymity in the scheme from [1]). But there are variants of these schemes that achieve anonymity. However, although these schemes gain anonymity, they lose the homomorphic property. Most usually, we need to know the identity associated with a ciphertext in order to correctly compute the homomorphic operation and so when the identity is hidden to us as it is when the scheme is anonymous, we cannot compute the homomorphic operation. So the open problem here in a nutshell is to construct an IBGHE for addition that is anonymous while retaining the homomorphic operation. This is mainly of theoretical interest.
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.
References
- Additively Homomorphic IBE from Higher Residuosity. Michael Clear and Ciaran McGoldrick. Public Key Cryptography. 2019.
- A Note on Attribute-Based Group Homomorphic Encryption.Michael Clear and Ciaran McGoldrick. Cryptology ePrint Archive, Report 2017/752. 2017.
- Homomorphic Encryption with Access Policies: Characterization and New Constructions. Michael Clear, Arthur Hughes and Hitesh Tewari. AFRICACRYPT. 2013.
- Identity-Based Cryptosystems and Quadratic Residuosity.. Marc Joye. Public Key Cryptography (1). 2016.