1
$\begingroup$

I'm trying to figure out how to do a mapping between elliptic curve points and Zq without breaking homomorphic properties.

Sorry, I'll write the problem in multiplicative notation because it's easier.

I've got $a = g^bh^r \in \mathbb{G}_1$, where $g$ is a generator of $\mathbb{G}_1$, $h = g^s$ and $r, s, b$ are some values from $Z_q$. I need to have a Pedersen commitment to $g^b$, but since $g^b\in \mathbb{G}_1$ I should map it to $Z_q$ with function $F$ first i.e. $c = G^{F(g^b)}H^R$, where $G,H \in \mathbb{G}_1$ is a commitment key and $R$ is randomly selected from $Z_q$.

The point is, I need to relate $a$ and $c$, so I need to find a mapping function F such that $G^{F(a)} = G^{F(g^b) \cdot F(h^r)}$.

Do you have any idea how to chose $F$ if $\mathbb{G}_1$ is an elliptic curve? Or if it's even possible? In the finite fields, $\bmod q$ would have worked ($q$ is prime). But with points, I'm not sure what to do. Maybe homomorphic hash functions would work, not sure.

Improve this question
$\endgroup$
21
  • $\begingroup$ @kelalaka, homomorphic. Thanks, fixed! $\endgroup$
    – pintor
    Commented Feb 21, 2021 at 10:25
  • $\begingroup$ When you say $x = y \cdot h^r$ what is $h$ what is $r$ what is $y$, EC has coordinates $(x,y)$ is it $x$ or $y$? $\endgroup$
    – kelalaka
    Commented Feb 21, 2021 at 10:31
  • $\begingroup$ @kelalaka. Maybe I used not the best notations, y and x are not related to EC coordinates. It's just some points on G1. I'll update notations $\endgroup$
    – pintor
    Commented Feb 21, 2021 at 10:36
  • $\begingroup$ if you consider scalar multiplication on ECC write as $[k]P$ and if you extract the $x$ coordinate then $x(P)$. $\endgroup$
    – kelalaka
    Commented Feb 21, 2021 at 10:41
  • 1
    $\begingroup$ also, unless $q$ is prime, mod $q$ won’t work $\endgroup$
    – kodlu
    Commented Feb 21, 2021 at 23:20

1 Answer 1

Reset to default
2
$\begingroup$

I think that you can use a bilinear pairing map for the function $F$. This map is defined from $G_1 \times G_2$ to $\mu_n$. This means that $F(x)=e(x,T)$ that $T \in G_2$.

The feature of this map is as:

$e(g^a,T^b)=e(g,T)^{ab}$

$e(g^bh^r,T)=e(g^b,T).e(h^r,T)=F(g^b).F(h^r)$

The amount of $\mu_n$ is in $F_{q^k}^*$. There is a map from $F_{q^k}$ to $F_q$ that is called Trace map. You can find more information about this map at "Pairing for beginners" book or http://www.m-hikari.com/ija/ija-2011/ija-21-24-2011/yadavIJA21-24-2011.pdf

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ but aren't \mu_n a cyclic group too? $\endgroup$
    – pintor
    Commented Feb 25, 2021 at 14:03
  • $\begingroup$ $\mu_n$ is a cyclic group. $\endgroup$
    – Mahdi Mahdavi
    Commented Feb 25, 2021 at 19:33
  • $\begingroup$ Thanks, but I need a mapping to $Z_q$. So one more step in F is missing - map $\mu_n$ to $Z_q$. Do we know anything about $\mu_n$? Can it be any cyclic group of order q, for example, a subgroup of $Z^*_p$? Btw, it's type-3 pairing, right? $\endgroup$
    – pintor
    Commented Feb 26, 2021 at 13:51
  • 1
    $\begingroup$ Or $\mu_n$ is a group of $n$-th roots of unity in $F^∗_{p^n}$? $\endgroup$
    – pintor
    Commented Feb 26, 2021 at 14:14
  • $\begingroup$ Sorry, I cannot accept the answer as it is, because it's incomplete. Can you please edit it before bounty expires? Thanks! $\endgroup$
    – pintor
    Commented Mar 1, 2021 at 9:25

Your Answer

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

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