📅 Original date posted:2013-06-20
📝 Original message:On Wed, Jun 19, 2013 at 05:28:15PM +0200, Adam Back wrote:
> I think Timo's point is that while you cant do discrete log, you can do y-th
> root. So if P = xG is a parent public key (x private key, G base point),
> then your proposed multiplier address is hash of Q=yP. However its easy to
> find another P such that Q=zP'. ie just "divide by z" (EC multiply by z^-1
> mod n, n the order of the curve). So P'=z^-1.Q, which will work because
> Q=zP', substituting P' you get Q=z.z^-1.Q, Q=Q.
>
> Of course the attacker has just performed an unspenable DoS (maybe, or maybe
> a useless collision) because he wont know the discrete log of Q, nor P, nor
> P'. So thats the question, does the protocol have any reliance on knowing
> the discrete log - is it a problem if someone can find different multipliers
> of different (unknown, uncomputable discrete log) parent keys.
>
> If it was a concern I guess you could require a proof of knowledge of
> discrete log. ie as well as public key parent, multiplier the address must
> include ECDSA sig or Schnorr proof of knowledge (which both demonstrate
> knowledge of the discrete log of Q to base G.)
The "concern" (if there is any) would be that the owner of the parent
P=xG, i.e. the person knowing x, in addition to y creates another pair
(P',z) such that yP=Q=zP' and uses that second pair maliciously later on
(such as claiming the payment went to identity P' not P). Since the
owner of P knows the private key for P' (x*y*z^-1) he can also produce
proof of knowledge for discrete log for P'. I think adding proof of
knowledge or signatures on the multiplier don't help to eliminate all
possible concerns, which could involve proving something to a third
party that has not seen the communication between payer and payee.
If you consider only payer and payee then Alan's original proposal is
just fine, as far as I can tell. Only if you start using it in a payment
protocol or, more precisely, if you start interpreting P as an identity
(as Alan suggested in subsequent posts) _and_ this identity is a
public/global one rather than a local one that only the payer uses, then
reasons can pop up to eliminate ambiguity about which identity each
payment went to.
Timo
ps the fact that this post used the multiplicative rather than additive
derivation scheme doesn't change the argument.
--
Timo Hanke
PGP 1EFF 69BC 6FB7 8744 14DB 631D 1BB5 D6E3 AB96 7DA8
Timo Hanke [ARCHIVE] /
npub1dd…pgp9a
2023-06-07 15:03:32
in reply to nevent1q…dkgs
Author Public Key
npub1ddqaln8xsfmy6sxqplt9sz5ev99kh052sveqsh02q7hmc3a6n68shpgp9aPublished at
2023-06-07 15:03:32Event JSON
{
"id": "4b87573bbe81b976795bb868d57738d8dc3c3ab878d0de47b4139218e9d51b57",
"pubkey": "6b41dfcce682764d40c00fd6580a99614b6bbe8a8332085dea07afbc47ba9e8f",
"created_at": 1686150212,
"kind": 1,
"tags": [
[
"e",
"60c63b2d935c09c2d6c618c7776de45a3225391d6d5c2bbb728d2b54da18fc56",
"",
"root"
],
[
"e",
"ef8d18a9ef776faffdfb1c378417c85222ddde6acc1870495114c0a1b1cc1d3c",
"",
"reply"
],
[
"p",
"86f42bcb76a431c128b596c36714ae73a42cae48706a9e5513d716043447f5ec"
]
],
"content": "📅 Original date posted:2013-06-20\n📝 Original message:On Wed, Jun 19, 2013 at 05:28:15PM +0200, Adam Back wrote:\n\u003e I think Timo's point is that while you cant do discrete log, you can do y-th\n\u003e root. So if P = xG is a parent public key (x private key, G base point),\n\u003e then your proposed multiplier address is hash of Q=yP. However its easy to\n\u003e find another P such that Q=zP'. ie just \"divide by z\" (EC multiply by z^-1\n\u003e mod n, n the order of the curve). So P'=z^-1.Q, which will work because\n\u003e Q=zP', substituting P' you get Q=z.z^-1.Q, Q=Q.\n\u003e \n\u003e Of course the attacker has just performed an unspenable DoS (maybe, or maybe\n\u003e a useless collision) because he wont know the discrete log of Q, nor P, nor\n\u003e P'. So thats the question, does the protocol have any reliance on knowing\n\u003e the discrete log - is it a problem if someone can find different multipliers\n\u003e of different (unknown, uncomputable discrete log) parent keys.\n\u003e \n\u003e If it was a concern I guess you could require a proof of knowledge of\n\u003e discrete log. ie as well as public key parent, multiplier the address must\n\u003e include ECDSA sig or Schnorr proof of knowledge (which both demonstrate\n\u003e knowledge of the discrete log of Q to base G.)\n\nThe \"concern\" (if there is any) would be that the owner of the parent\nP=xG, i.e. the person knowing x, in addition to y creates another pair\n(P',z) such that yP=Q=zP' and uses that second pair maliciously later on\n(such as claiming the payment went to identity P' not P). Since the\nowner of P knows the private key for P' (x*y*z^-1) he can also produce\nproof of knowledge for discrete log for P'. I think adding proof of\nknowledge or signatures on the multiplier don't help to eliminate all\npossible concerns, which could involve proving something to a third\nparty that has not seen the communication between payer and payee. \n\nIf you consider only payer and payee then Alan's original proposal is\njust fine, as far as I can tell. Only if you start using it in a payment\nprotocol or, more precisely, if you start interpreting P as an identity\n(as Alan suggested in subsequent posts) _and_ this identity is a\npublic/global one rather than a local one that only the payer uses, then\nreasons can pop up to eliminate ambiguity about which identity each\npayment went to.\n\nTimo\n\nps the fact that this post used the multiplicative rather than additive\nderivation scheme doesn't change the argument.\n\n-- \nTimo Hanke\nPGP 1EFF 69BC 6FB7 8744 14DB 631D 1BB5 D6E3 AB96 7DA8",
"sig": "850f74e6fb70888f6172ca4d9d1528d7a10063080ef9c87aece2e840e99b00002faea91343972ca94c6f3b0d9bcbe939cd48b867a2b418c95173b57e9356171a"
}