2
$\begingroup$

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.

Improve this question
$\endgroup$
18
  • $\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
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 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$ I have updated the original post to make it clearer. Please go it through once more. $\endgroup$ – Holmes.Sherlock Sep 10 '14 at 1:45
  • $\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
0
$\begingroup$

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$.

Improve this answer
$\endgroup$

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.