Lets assume we have a group $G$ with unknown order. And we have a pair $(A_1,K_1), (A_2,K_2)$ in which all $A_1,K_1,A_2,K_2$ are group elements. The claim is $A_1= K_1 ^ x$ and $A_2 = K_2 ^ x$. or informally we want to show they both have the same exponent. ($x$ is prime)

We do not want to share both $K_1,K_2$. We want to share a single element as a proof for this fact. It is ok if someone can extract $K_1,K_2$ from the single element provided.

Is there any protocol for this?

  • 2
    $\begingroup$ This Q&A is relevant. $\endgroup$
    – SEJPM
    Mar 11 '20 at 19:35
  • 1
    $\begingroup$ Among the various parameters $(A_1, K_1, A_2, K_2, x)$, which is public? Which is private (must not be revealed in the proof)? You state that the group is unknown order - does it mean that it's secret (e.g. $\mathbb{Z}_n^*$ with $n$ a composite of secret factorization)? $\endgroup$
    – poncho
    Mar 11 '20 at 21:02
  • $\begingroup$ nothing is secret. instead of sending $K_1$ and $K_2$ we want to send only one element. And it is ok if anyone can recalculate $K_1,K_2$. The main goal is to send only 1 elements. $\endgroup$ Mar 13 '20 at 7:54
  • $\begingroup$ Regarding to the group. It can be $Z^*_n$ but without {1,-1} as they have known order. We need a group without knowing the order of any of the elements inside as we can break the system by knowing it. For further information you can read this part in RSA accumulator paper by Dan boneh (2018) $\endgroup$ Mar 13 '20 at 7:56

Your Answer

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

Browse other questions tagged or ask your own question.