Let's say, I have a group $G$ of large prime order $p$. A set $S$ consists of $n$ random elements chosen from $G$. Without using a collision resistant hash function $H$, how can I map elements of $G$ to unique elements in $Z_p$?

I thought about it before posting here. But, finding discrete logarithm for an arbitrary group is hard, right? In theory, it'd satisfy the requirement of collision resistance, but inefficient.

I don't really know the structure of the group beforehand. What I am essentially trying to do is, I am trying to figure out a generic means to map public key ($PK$) of a Public Key Encryption system to $z \in Z_p$, such that a third party can be convinced about the co-relation between the $PK$ and $z$ without revealing $PK$ but $z$ and some form of proof-of-knowledge. Hash functions, due it inherent nature of pre-image resistance, seems unsuitable.

  • $\begingroup$ If you can find a non-identity element and efficiently compute discrete logarithms, then you can use Dennis's suggestion. $\:$ If $S$ is determined before (or independently of) the map, then you can just use a universal hash family. $\:$ If neither of those hold, then I'm pretty sure it depends on the group $G$. $\;\;\;\;$ $\endgroup$ – user991 Sep 10 '14 at 0:34
  • $\begingroup$ I have updated the original post to make it clearer. Please go it through once more. $\endgroup$ – Holmes.Sherlock Sep 10 '14 at 1:43
  • $\begingroup$ Why does the ring's ($Z_p$'s) size need to be the same as $G$'s? $\;$ $\endgroup$ – user991 Sep 10 '14 at 2:54
  • 1
    $\begingroup$ Sorry, but I remain confused. 1. Why are you keeping the public key secret? 2. What does the third party know? What exactly is it supposed to be able to verify? $\endgroup$ – Dennis Sep 10 '14 at 4:20
  • 1
    $\begingroup$ Any mapping which ignores the group structure will be based solely on element representation and would probably not be usable in a ZKP. Also, why invent a new ring signature scheme rather than using an existing one? $\endgroup$ – abacabadabacaba Sep 22 '14 at 0:31

The order of every element $g$ of a group $G$ divides the order of the group ($p$).

Since $p$ is prime, every $g\in G$ has order $1$ or $p$. Only the identity element $e$ satisfies the first case, so every $g\in G\setminus\{e\}$ is a generator of $G$, i.e., $$G = \{g^0,g^1,g^2,\cdots,g^{p-1}\}.$$

This allows defining a bijection $$\begin{array}{cccc}\varphi:&\mathbb Z_p&\rightarrow& G\\&n&\mapsto&g^n\end{array}.$$

If you can find $\varphi^{-1}$, you're done.

  • 1
    $\begingroup$ Note that finding $\varphi^{-1}$ might be infeasible in some cases. It would help to know which group you're trying to map to $\mathbb Z_p$. $\endgroup$ – Dennis Sep 9 '14 at 21:28
  • $\begingroup$ $\mathbb{Z}_p$ does not have order $p$, unless you use the addition as group operation. The multiplicative group $\mathbb{Z}_p^*$ has order $p-1$. $\endgroup$ – tylo May 8 '15 at 9:57
  • $\begingroup$ @tylo: The order of a finite group equals its number of elements, so for all valid group operations $*_1$ and $*_2$, $(\mathbb Z_p,*_1)$ and $(\mathbb Z^*_p,*_2)$ have orders $p$ and $p-1$, respectively. Since $\mathbb Z_p\neq\mathbb Z^*_p$, I'm not sure what your example is supposed to prove. $\endgroup$ – Dennis May 8 '15 at 13:11
  • $\begingroup$ @tylo: I use multiplicative notion for the group $G$, yes. $\mathbb Z_p$ is a simple set here. No group operation required. $\endgroup$ – Dennis May 8 '15 at 13:35

Let's start with an article in a wiki about group theory. That one states, that it is automatically cyclic and it is isomorphic to $(\mathbb{Z}_p,+)$. Formally speaking, it is abelian, cyclic, nilpotent, and of course finite.

That means actually you know a lot about the group structure ahead of time. Because it is already fully determined with a variable $p$.

That means, you actually don't need to anything, because the isomorphism into $(\mathbb{Z}_p,+)$ does everything for you. If you want to add some more flavor, you can choose a generator other than the usual $1$ for the additive group, or since you don't need the structure preserving property, just choose any bijective function, e.g. a polynomial with a degree coprime to $p-1$.


Your Answer

