2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ A scheme for what? $\endgroup$
    – yyyyyyy
    Dec 22, 2017 at 11:41

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ @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? $\endgroup$
    – Naz
    Dec 29, 2017 at 20:14
  • $\begingroup$ 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 :) $\endgroup$
    – Geoffroy Couteau
    Dec 29, 2017 at 20:30
  • $\begingroup$ @Geofroy Couteau: Thank you so much for your answer. I have already asked it on a different thread :) $\endgroup$
    – Naz
    Dec 29, 2017 at 20:34
  • $\begingroup$ 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 :) $\endgroup$
    – Geoffroy Couteau
    Dec 29, 2017 at 20:35
  • $\begingroup$ @Geofroy Couteau: Could please tell me, which complexity assumption should I follow for the above question? $\endgroup$
    – Naz
    Dec 29, 2017 at 20:39
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Is DL known to be NP-hard? $\endgroup$
    – mikeazo
    Dec 22, 2017 at 14:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – Geoffroy Couteau
    Dec 22, 2017 at 16:14
  • $\begingroup$ @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. $\endgroup$
    – Benjamin Mord
    Dec 24, 2017 at 3:29
  • $\begingroup$ 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. $\endgroup$
    – Squeamish Ossifrage
    Dec 24, 2017 at 3:43
  • $\begingroup$ 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/… $\endgroup$
    – Benjamin Mord
    Dec 24, 2017 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.