$Would the Equation $s\cdotG=P1+e\cdotP2$ Reveal Hidden Points $P1$ and $P2$ on an Elliptic Curve?$

Question

$Would the Equation $s\cdotG=P1+e\cdotP2$ Reveal Hidden Points $P1$ and $P2$ on an Elliptic Curve?$

My apologies if this is not a valid question. I come from a computer science background, and this question came to mind while attempting to provide privacy protection for my use case.

Assume there are two points, $P1$ and $P2$, on an elliptic curve with generator $G$.

Given that the scalars $s$ and $e$, and the generator $G$, are public, while the points $P1$ and $P2$ are hidden,

Would the following equation reveal any information about $P1$ or $P2$?

$s⋅G=P1+e⋅P2$

Algebra Abstract Algebra Algebraic Geometry

Emmaqh

9

Report

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.

Answer 1

Answers can only be viewed under the following conditions:

The questioner was satisfied with and accepted the answer, or
The answer was evaluated as being 100% correct by the judge.

View the answer

Emmaqh,

The equation you have represents a linear relationship in the elliptic curve group between a known point and two hidden points. If you rearrange the equation:

$P1 = s.G - e.P2$

s.G and e are public, so P1 is effectively determined if P2 is known. This implies a dependency between P1 and P2.

There are infinitely many valid pairs (P1, P2) that satisfy your equation. The equation alone does not uniquely determine either P1 or P2.

Elliptic curve cryptography is highly context-dependent. Whether this setup leaks information depends on additional factors such as for example if P1 and P2 are random points. If both are independently and randomly chosen elliptic curve points, the equation reveals no meaningful information about P1 or P2 because like I said above, there are infinitely many solutions for (P1, P2) that satisfy the equation.

However, if P1 or P2 are derived from structured data, the equation could potentially leak information. Why? For instance:

If $P2 = x.G$ , where x is a private scalar, the equation becomes:

$P1 = s.G - e. (x.G)$

Substituting $P1 = y.G$ , where y is another private scalar, we get:

$y.G = s.G - e. (x.G)$

Simplifying, this leads to:

$y = s - e.x$

In this case, the equation reveals a linear relationship between the scalars x, y, s, and e which could potentially leak information about x or y if s and e are known and x or y have further constraints (e.g. a small range).

So, all in all, your equation does not directly reveal P1 or P2 in the general case (random elliptic curve points). A single elliptic curve equation typically cannot uniquely determine multiple unknown points.

However, in specific contexts where P1 or P2 are derived from structured or constrained data, it may leak information about those points.

In cryptographic terms, as long as P1 and P2 are chosen independently and uniformly at random from the group of points on the curve, the equation does not leak information about those points.

Hope this helps.

Kav10

1.9K

Emmaqh

0

Many thanks! Your answer is actually very helpful. The points are indeed independently generated from uniformly random scalars x and y. Since you mentioned cryptography, allow me to ask a follow-up question ( I’ll increase the tip).
- Kav10
  
  0
  
  I am glad you found it helpful.
Emmaqh

0

I am working on distributed verification of Schnorr’s identification protocol using multi-party computation to hide the clients’ public keys. The verification involves the equation: s* G = R + e * P, where s is the client signature, R is a random point and P is the client public key. Only P and R are private (secret-shared). The result of 𝑅 + 𝑒 * 𝑃 will be revealed, and the equality test will be performed in the clear. Based on your answer I can say that this should not reveal P, correct?
Kav10

0

You are correct. The scenario you described does not reveal the private key P based on what you mentioned and under the conditions you described. The revealed value R+e⋅P and the subsequent equality test do not reveal information about P, provided if you have randomness of R and secure secret-sharing.
Kav10

0

So, basically, you have a P which is secret-shared and not directly exposed. R is a random elliptic curve point, also secret-shared and not revealed directly. Only R+e⋅P is revealed, which is effectively a masked version of e.P. So, because R is random and independent of P, its presence ensures that the revealed R+e⋅P does not expose direct information about P.
Emmaqh

0

Great! Last question، could you point me to approaches or resources that may help in writing a formal security analysis?
- Kav10
  
  0
  
  I did a quick Google search and this paper seem to be helpful for that: https://www.baigneres.net/downloads/2007_provable_security.pdf
Kav10

+1

Found a good one for you. This will help you: https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_5.pdf
Kav10

0

Thanks for the tip. Let me know if you have more questions.

$Would the Equation $s\cdotG=P1+e\cdotP2$ Reveal Hidden Points $P1$ and $P2$ on an Elliptic Curve?$

Answer

Related Questions

Search

Would the Equation $s⋅G=P1+e⋅P2$ Reveal Hidden Points $P1$ and $P2$ on an Elliptic Curve?

Answer

Related Questions

Search

$Would the Equation $s\cdotG=P1+e\cdotP2$ Reveal Hidden Points $P1$ and $P2$ on an Elliptic Curve?$