I'm having trouble understanding what the “security model” for “scalar multiplication” in NaCl is.

Security model

crypto_scalarmult is designed to be strong as a component of various well-known "hashed Diffie–Hellman" applications. In particular, it is designed to make the "computational Diffie–Hellman" problem (CDH) difficult with respect to the standard base.

crypto_scalarmult is also designed to make CDH difficult with respect to other nontrivial bases. In particular, if a represented group element has small order, then it is annihilated by all represented scalars. This feature allows protocols to avoid validating membership in the subgroup generated by the standard base.

NaCl does not make any promises regarding the "decisional Diffie–Hellman" problem (DDH), the "static Diffie–Hellman" problem (SDH), etc. Users are responsible for hashing group elements.

Since “crypto_scalarmult is the function crypto_scalarmult_curve25519”, does this mean that Curve25519 does not provide any guarantees for the DDH problem to be hard?

If so, how can one—as suggested—hash group elements to achieve this? E.g., how does one implement elliptic curve El-Gamal in a semantically secure way using this implementation, if possible at all?

  • $\begingroup$ The API makes no guarantees about DDH. The underlying implementation may go beyond what the API guarantees. $\endgroup$
    – SEJPM
    Jul 28 '16 at 9:49

Since "crypto_scalarmult is the function crypto_scalarmult_curve25519", does this mean that Curve25519 does not provide any guarantees for the DDH problem to be hard?

No, it just means, that the NaCl specification or API, which is different from the NaCl implementation / library, makes no guarantees about the DDH problem being hard in the group being used. The implementation however may of course go beyond what is guaranteed by the API and use a group where DDH is hard, such as Curve25519.

If so, how can one hash group elements to achieve this?

The output of the crypto_scalarmult function essentially is a chunk of bytes. You can then use your favorite hash function (e.g. SHA-3-256 or SHA-256) or preferably your favorite key-based key derivation function (KBKDF) (e.g. HKDF) to derive symmetric key material for bulk encryption.

How does one implement elliptic curve El-Gamal using this implementation, if possible at all?

ElGamal requires the message to be represented as a group element which is not trivially possible to do in an (easily) invertible way and thus I strongly discourage anyone from using EC-Elgamal and instead use ECIES.

However you asked and I shall answer (using the notation from the HAC (PDF)):
Let $\alpha$ be your generator of the (sub)group. Let $\beta$ be your recipient's public key and $a$ be his private key. $\beta$ can be generated from $\alpha$ as $\alpha^a=\beta$, which maps 1-to-1 to a call to crypto_scalarmult.

For encryption you then pick a random $k$ which is smaller than the group's order and compute $\beta^k$ and $\gamma=\alpha^k$ which both can be done by single calls to crypto_scalarmult and then you compute $\delta=m\cdot(\beta^k)$, e.g. you apply the group operation to $m$ and the buffered $\beta^k$. Your ciphertext of the plaintext $m$ is now $(\gamma,\delta)$.

Decryption is even easier, you compute $\gamma^{q-a}$ where $q$ is the (sub)group's order and then perform a group operation using $\gamma^{q-a}$ and $\delta$, the result will be $m$.

  • $\begingroup$ I'm not sure how the library/API could break destroy the DDH assumption; could you maybe give a reference or clarify this? Furthermore, what I now understand is that if one would implement EC ElGamal using NaCl, this would not be guaranteed to be semantically secure (due to DDH not being guaranteed). $\endgroup$ Jul 28 '16 at 11:27
  • $\begingroup$ @timothymctim I've replaced the relevant "library" term with "specification". The specification of NaCl doesn't break the DDH assumption, it just doesn't guarantee you that the underlying implementation will use a group where DDH is hard, so the implementation are free to use groups where DDH is easy, but CDH is hard. And yes, if you only rely on the specification for your assumption, ElGamal using this wouldn't be guaranteed to be secure, however, using ElGamal is really difficult anyways and it is "only" IND-CPA and thus ECIES is the better choice with IND-CCA2 using only CDH. $\endgroup$
    – SEJPM
    Jul 28 '16 at 11:41
  • $\begingroup$ Great! The EC ElGamal was more a hypothetical question, understanding if the library could be used for schemes relying on DDH. Now I understand that, as long as one uses the right curve (currently there's only one option: Curve25519), the DDH problem is (i.e., remains) hard. $\endgroup$ Jul 28 '16 at 12:09

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.