# Is Discrete Logarithmic assumption enough to design a secure searchable encryption scheme?

I have a basic question in my mind which is "Can we develop a scheme based on Discrete Logarithmic (DL) assumption only? "

Most of the "Searchable Encryption" schemes use assumptions like Decisional Bilinear Diffie–Hellman (DBDH) in their formal security proofs, (e.g. "Protecting Your Right: Verifiable Attribute-Based Keyword Search with Fine-Grained Owner-Enforced Search Authorization in the Cloud" by Sun et al. SE). Can the formal security proof of my designed scheme be based on DL assumption only?

• A scheme for what? – yyyyyyy Dec 22 '17 at 11:41

If you only use the group in a black-box way (meaning, if you wish to rely on the discrete logarithm problem on an arbitrary group), we do not know of any encryption scheme (searchable or not) whose IND-CPA security reduces to the discrete logarithm problem. What we can do from the discrete logarithm problem directly is quite limited. In particular:

• you can design a commitment scheme whose binding property reduces to the discrete log problem, this is the famous Pedersen commitment scheme.
• The key-recovery security of the ElGamal encryption scheme (i.e. the hardness of computing its secret key given only its public key) reduces to the discrete logarithm assumption.

However, in some specific groups, it is known that the computational Diffie-Hellman assumption is equivalent to the discrete logarithm assumption - this was shown by den Boer in this paper.

Furthermore, we know how to construct advanced types of encryption schemes from the computational Diffie-Hellman assumption. For example, using the Goldreich-Levin harcore predicate and the ElGamal encryption scheme, one can construct an encryption scheme whose IND-CPA security reduces to CDH. IND-CCA secure cryptosystems from CDH where given in this paper.

Very recently, in a breakthrough result, Garg and Döttling have shown that identity-based encryption can be obtained assuming CDH only.

In a follow up to the previous paper, this result was extended to anonymous IBE. Furthermore, it is known that encryption with keyword search can be constructed from anonymous IBE - see this paper. Combining all of the above, this gives you a CDH-based searchable encryption scheme.

All these schemes are secure under the discrete logarithm assumption when instantiated in the groups identified by den Boer. However, it should be noted that the dlog-based keyword-search scheme obtained this way is extremely inefficient and only of theoretical interest.

• @Geofroy Couteau: I have another question (doubt). Please let me know your answer. My question is as follows: Let, $g^{a}$, $g^{b}$ are known elements, where $g\in G$ and $a, b\in Z_q$. According to Computational Diffie-Hellman (CDH) assumption, it is hard to compute $g^{ab}$. If $g^{a^2}$ is also known then is it still fall into Computational Diffie-Hellman assumption? In other words, if $g^{a}$, $g^{a^2}$, $g^{b}$ are known, is computing $g^{ab}$ still CDH? – Naz Dec 29 '17 at 20:14
• The answer to your question is no, it's not equivalent to CDH, it's another (stronger) assumption, but still a plausible one. But in general, if you have a different question to ask, the best thing is to open a new question thread on crypo.stackexchange rather than asking it in the comments :) – Geoffroy Couteau Dec 29 '17 at 20:30