# 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
• @Geofroy Couteau: Thank you so much for your answer. I have already asked it on a different thread :) – Naz Dec 29 '17 at 20:34
• You're welcome. If my answer to your question on this thread is the one you were looking for, you should consider marking it as accepted :) – Geoffroy Couteau Dec 29 '17 at 20:35
• @Geofroy Couteau: Could please tell me, which complexity assumption should I follow for the above question? – Naz Dec 29 '17 at 20:39

It is also known that sufficiently powerful quantum computers will break the assumption that discrete logarithms cannot be solved in polynomial time, raising doubts about the future security of systems based on it.

• Is DL known to be NP-hard? – mikeazo Dec 22 '17 at 14:52
• Notwithstanding the incorrect use of the term NP-hard, this does absolutely not answer OP's question... Quantum computers would as well break searchable encryption based on DBDH, and also ElGamal, RSA, and most cryptosystems, but that's not relevant to the current question at all. – Geoffroy Couteau Dec 22 '17 at 16:14
• @GeoffroyCouteau, thank you for correcting my misuse of term 'NP hard', I have corrected the post. But please note D-Wave annealers are at 2,000 qubits and counting, not a threat this year but it is just a matter of time - seems appropriate to inform folks when their direction is vulnerable. – Benjamin Mord Dec 24 '17 at 3:29
• The shape of the growth curve as the parameter size grows, polynomial or not, isn't as important as the concrete cost of attacks. Note that even if D-Wave's quantum computing improves on classical computers for certain optimization problems, they are useless for cryptanalysis. That doesn't mean one should disregard possible adversaries in the future who can run Shor's algorithm, but it's not really helpful to just throw up one's hands and answer any question about DL-based crypto with Shor. – Squeamish Ossifrage Dec 24 '17 at 3:43
• The next chip architecture D-Wave is working on now not only expands number of qubits, but more importantly it greatly increases connectivity among physical qubits, so as to greatly improve efficiency of typical problem embeddings. The discussion about them not being practical for cryptography actually suggests they are closer than I had thought. nature.com/news/… – Benjamin Mord Dec 24 '17 at 20:34