Join Log in
Score:1
knaccc avatar Crypto

Is partial computation of an Ed25519 Diffie-Hellman shared secret possible?

es flag
knaccc

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.

33
0 + 0
kelalaka avatar
in flag
kelalaka
Ed25519 is not for DHKE, [X25519 is the recommended Montgomery-X-coordinate DH function.](https://crypto.stackexchange.com/q/84434/18298), and the answer is no.
0
Reply
knaccc avatar
es flag
knaccc
@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.
0
Reply
knaccc avatar
es flag
knaccc
@kelalaka thanks, I've amended the question to ask instead if any characteristics can be partially computed.
0
Reply
kelalaka avatar
in flag
kelalaka
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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.