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.

$\endgroup$
21
  • $\begingroup$ @kelalaka, homomorphic. Thanks, fixed! $\endgroup$
    – pintor
    Feb 21 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
    Feb 21 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
    Feb 21 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
    Feb 21 at 10:41
  • 1
    $\begingroup$ also, unless $q$ is prime, mod $q$ won’t work $\endgroup$
    – kodlu
    Feb 21 at 23:20
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

$\endgroup$
8
  • 1
    $\begingroup$ but aren't \mu_n a cyclic group too? $\endgroup$
    – pintor
    Feb 25 at 14:03
  • $\begingroup$ $\mu_n$ is a cyclic group. $\endgroup$ Feb 25 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
    Feb 26 at 13:51
  • 1
    $\begingroup$ Or $\mu_n$ is a group of $n$-th roots of unity in $F^∗_{p^n}$? $\endgroup$
    – pintor
    Feb 26 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
    Mar 1 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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