Let's say we're using the Ed25519 curve, and we're computing a Diffie-Hellman shared secret EC point $S$ by scalar multiplication of scalar $a$ with EC point $B$.

Is there any way of partially calculating at least a few bits of $S$ without completing the full scalar multiplication process?

The goal is to be able to communicate a few bits (ideally 8 bits) of $S$ in advance to the person that intends to compute $S = a\cdot B$. The recipient will perform a quick partial calculation first to check if a full calculation will actually result in a value of $S$ that will have the specified 8 bits.

The sender of the 8 bits will not know $a$, because instead they will know $A$ and $b$ such that $bA==aB$.

If certain bits cannot be partially computed, can any characteristics of $S$ be partially computed instead?

Even 1 bit of information about $S$ through partial calculation would be useful.

  • $\begingroup$ Ed25519 is not for DHKE, X25519 is the recommended Montgomery-X-coordinate DH function., and the answer is no. $\endgroup$
    – kelalaka
    Jan 29 at 18:54
  • $\begingroup$ @kelalaka I know Ed25519 is not usually used for DHKE for performance reasons, but it is used for this purpose in the Monero protocol to communicate a shared secret to the recipient of a transaction. This question has important performance implications when it comes to wallets scanning the blockchain for incoming transactions. $\endgroup$
    – knaccc
    Jan 29 at 18:57
  • $\begingroup$ @kelalaka thanks, I've amended the question to ask instead if any characteristics can be partially computed. $\endgroup$
    – knaccc
    Jan 29 at 19:03
  • $\begingroup$ I think one can conclude that any quick calculation can fasten DLOG, and I'm not aware of such an approach. Maybe one can show something. Besides, I started to believe that those currency people don't know/care about cryptography at all. Let see some has knowledge about this. $\endgroup$
    – kelalaka
    Jan 29 at 19:17


Your Answer

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

Browse other questions tagged or ask your own question.