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
    Commented Jan 29, 2022 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
    Commented Jan 29, 2022 at 18:57
  • $\begingroup$ @kelalaka thanks, I've amended the question to ask instead if any characteristics can be partially computed. $\endgroup$
    – knaccc
    Commented Jan 29, 2022 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
    Commented Jan 29, 2022 at 19:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.