4
$\begingroup$

Consider an elliptic curve $E$ defined over a finite field $\mathbb{F}_{\!q}$ with a fixed non-zero $\mathbb{F}_{\!q}$-point $P$. For simplicity, let the order of the $\mathbb{F}_{\!q}$-point group $E(\mathbb{F}_{\!q})$ be prime and hence the group is generated by $P$. For the sake of security, in numerous protocols of elliptic cryptography (e.g., in a safe version of Dual_EC_DRBG) we need to generate yet another "independent" $\mathbb{F}_{\!q}$-point $Q$ on $E$.

Please answer the question. Do you know protocols, where it is necessary to obtain more "independent" $\mathbb{F}_{\!q}$-points on the same curve ? In other words, a party deals with "independent" $\mathbb{F}_{\!q}$-points $Q_1$, $Q_2$, $\ldots$, $Q_n$ in addition to $P$. By "independent" I mean such points that no one knows the discrete logarithms relative to each other.

I ask you, because for some $E$ and $n$ I know how to produce simultaneously several $Q_i$ faster than separate generation of them. I would like to understand whether my approach is worthy of publication in a good scientific journal. Or maybe it even has something to do with real world cryptography.

Improve this question
$\endgroup$
2
  • $\begingroup$ Maybe some multi-party ECDH based key agreements? $\endgroup$
    – eckes
    Apr 26, 2022 at 6:57
  • $\begingroup$ @eckes, could you precise your comment ? $\endgroup$
    – Dimitri Koshelev
    Apr 26, 2022 at 7:09

3 Answers 3

Reset to default
8
$\begingroup$

Do you know protocols where it is necessary to obtain several "independent" points on the same elliptic curve?

One obvious place where this occurs if you are implementing a Pedersen commitment of a vector of values; you commit to a vector $(x_1, x_2, ..., x_n)$ by publishing the value $rH + x_1G_1 + x_2G_2 + ... + x_nG_n$; for this to work, you obviously need $n+1$ independent points $H, G_1, G_2, ..., G_n$

While this is a tad obscure, this does come up; a quick Google finds this paper, and so there is some applicability; certainly more than some papers I have seen...

Improve this answer
$\endgroup$
8
  • $\begingroup$ thank you! I don't know much about commitment schemes. Why is not it sufficient to take $n = 1$ ? Does $n > 1$ occur in real world crypto ? $\endgroup$
    – Dimitri Koshelev
    Apr 25, 2022 at 16:17
  • $\begingroup$ @DimitriKoshelev: $n=1$ might not be sufficient if you're trying to take advantage of the homomorphic properties of Pedersen commitments; e.g. given a commitment of $(x_1, x_2)$ and $(y_1, y_2)$ generate a ZKP that $2(x_1, x_2) - 5(y_1, y_2) = (3, 7)$ $\endgroup$
    – poncho
    Apr 25, 2022 at 16:47
  • $\begingroup$ I forgot to say that my generation method gives $\approx q$ tuples $(Q_i)_{i=1}^n$ among $E^n(\mathbb{F}_{\!q}) \approx q^n$. Isn't this important for security ? $\endgroup$
    – Dimitri Koshelev
    Apr 25, 2022 at 17:20
  • $\begingroup$ @DimitriKoshelev: what's critical (at least, for vector Pedersen commitments) is that no one knows a nontrivial solution for $x_1G_1 + x_2G_2 + ... + x_nG_n = 0$ (where the trivial solution is $x_1 \equiv x_2 \equiv ... \equiv x_n \equiv 0$). Does your idea provide that? $\endgroup$
    – poncho
    Apr 25, 2022 at 17:36
  • $\begingroup$ It provides that, but the distribution is far from uniform on $E^n(\mathbb{F}_{\!q})$ (it covers only $\approx q$ tuples). I have the impression that this is not important, because $q$ is big in cryptography and we can change often independent points. What do you think ? $\endgroup$
    – Dimitri Koshelev
    Apr 25, 2022 at 17:47
2
$\begingroup$

There is a "hash-to-point" function used in several schemes, where it is necessary to generate an EC point where the discrete log w.r.t. any other EC point is unknown. In particular:

  1. A linkable ring signature. A 'key image' needs to be generated, where the correctness of the 'key image' declared with a signature is verifiable, and where if the same signer (using the same private key) were to create a ring signature again (even with different other ring member public key participants), it would be clear that they have used the same private key to sign again. See here for details.

  2. An oblivious psuedo-random function uses hash-to-point to encode the PRF input values as EC points. here.

  3. Oblivious transfer uses hash-to-point, and EC El Gamal can use hash-to-point if you only need the encoding of messages into points to go in one direction. See an example of both here.

  4. This non-membership proof uses hash-to-point for a variation on Pedersen commitments where the commitment needs to be blinded, but does not need to be additively homomorphic.

Improve this answer
$\endgroup$
6
  • $\begingroup$ thank you, but I cannot compute a "hash-to-point" function in several arguments faster than separately. My problem is different. I can generate several independent points (depending in only one argument) faster than separately. $\endgroup$
    – Dimitri Koshelev
    Apr 25, 2022 at 17:04
  • $\begingroup$ @DimitriKoshelev can you clarify what you mean by "depending in only one argument"? And does your technique work when there is a co-factor, and you need to ensure that the point is within the same large subgroup as the large subgroup generated by a particular well-known base point? You might be interested that there was some optimization work done for the Monero cryptocurrency to ensure that an arbitrary byte sequence can be quickly mapped to an Ed25519 point: github.com/monero-project/research-lab/blob/master/whitepaper/… $\endgroup$
    – knaccc
    Apr 25, 2022 at 17:23
  • $\begingroup$ This is the C and Python code for mapping quickly to valid EC points, based on the paper I linked in the comment above: github.com/monero-project/monero/blob/… github.com/monero-project/mininero/blob/… $\endgroup$
    – knaccc
    Apr 25, 2022 at 17:29
  • $\begingroup$ Me technique returns a tuple $(Q_i)_{i=1}^n$ depending on a given element of the basic field $\mathbb{F}_{\!q}$. It works when there is a co-factor, because we can always clear it. $\endgroup$
    – Dimitri Koshelev
    Apr 25, 2022 at 17:39
  • $\begingroup$ @DimitriKoshelev In the examples I've given above, let's say you are doing some kind of private set intersection and the numbers being sent to the OPRF are small integers lower than, say, 100. Depending on how much faster it might be to create a tuple of 100 elements using your technique, perhaps it would be preferable to use your technique than to individually do a hash-to-point operation on each integer input. $\endgroup$
    – knaccc
    Apr 25, 2022 at 17:56
1
$\begingroup$

Your question is essentially: Is it useful to be able to sample a tuple $(Q_1, Q_2, \dots, Q_n) \in E(F)^n$ such that no relation is known among the points, but the tuple is not sampled from the uniform distribution.

From a practical point of view, there are two issues:

  • Often, these points are sampled during the generation of system parameters, which does not happen very often and is not time critical.
  • Many schemes seem secure even if the points have not been sampled from the uniform distribution.

That is, practically it is often not very useful, but also often not insecure, seemingly at least.

The main objection would be that the security proofs of these schemes sometimes rely on being able to sample the tuple $(Q_1, \dots, Q_n)$ with some trapdoor embedded, and this is often hard to do if you need a non-uniform distribution on the tuple. This would then ruin the security proof. (Example: Suppose I want to be able to equivocate openings of Pedersen multi-commitments.)

Some people may not care about that, but I think most cryptographers would be very reluctant to accept this without any clear benefit to be had.

In other words, I would expect the algorithm you have to be mostly not useful and sometimes unusable.

That said, the algorithm you have come up with may be interesting to some people for some reason, regardless of these obstacles. Or it may have other interesting properties. So it may be worthwhile publishing anyway.

Improve this answer
$\endgroup$
4
  • $\begingroup$ thank you. You write "Often, these points are sampled during the generation of system parameters, which does not happen very often and is not time critical." However, if we don't change often the points, then there is a risk that an attacker can find a dependency between them, especially if $n$ is big. Am I right ? $\endgroup$
    – Dimitri Koshelev
    Apr 26, 2022 at 14:35
  • $\begingroup$ I didn't understand your paragraph starting from "The main objection ...". Could you clarify ? $\endgroup$
    – Dimitri Koshelev
    Apr 26, 2022 at 14:44
  • $\begingroup$ These points might appear in system parameters, public keys and standards. Long-term objects, in other words. What in particular is it you do not understand? $\endgroup$
    – K.G.
    Apr 26, 2022 at 18:20
  • $\begingroup$ in fact, I can refine the method to make it uniform. Even then, it works much more efficiently in average than the successive calls of a constant-time map to a curve. $\endgroup$
    – Dimitri Koshelev
    May 23, 2022 at 14:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.