In order to understand the construction of a zK-SNARK, I have recently been trying to understand the KEA1 assumption in The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols by Mihir Bellare and Adriana Palacioy.

I do not understand the meaning of this assumption. For example, why is this "hard problem" used in cryptography?

On page three of the paper, the authors roughly outlined the assumption, but this didn't clarify things for me. I have a strong math background, so if someone could explain the KEA1 assumption to me in a mathematical way, that would be great.

  • 1
    $\begingroup$ You'll need to ask a more precise question here. The paper is very clearly written, so at least quote the parts you don't understand. $\endgroup$ – fkraiem Dec 20 '18 at 16:04
  • $\begingroup$ Let $q$ be a prime such that $2q+1 $ is also prime, and let $g$ be a generator of the order $q$ subgroup of $Z_{2q+1} $. Suppose we are given input $q, g, g^a$ and want to output a pair $(C, Y )$ such that $Y = C^a$. One way to do this is to pick some $c \in Z_q$, let $ C = g^c$, and let Y = g^{ac} . Intuitively, KEA1 can be viewed as saying that this is the “only” way to produce such a pair. The assumption captures this by saying that any adversary outputting such a pair must “know” an exponent. $\endgroup$ – Pierre21 Dec 20 '18 at 18:22
  • $\begingroup$ This is really the part I don't get. Why does it make this assumption a hard assumption? How can it be used for example? $\endgroup$ – Pierre21 Dec 20 '18 at 18:23
  • $\begingroup$ I have no idea what you mean by "a hard assumption". To see how it can be used, look at papers that use it (the first one is that of Damgård). $\endgroup$ – fkraiem Dec 20 '18 at 18:29
  • $\begingroup$ I mean that this assumption can be used for cryptography, for me the meaning of the assumption is that there is no chance to construct such a pair $(g^c, g^{ac}) $ but I am probably wrong. Is this the same thing as en.wikipedia.org/wiki/… ? $\endgroup$ – Pierre21 Dec 20 '18 at 18:33

I think why this assumption is hard is that in the prime field $F_p$, you can't find directly $a$ from $g^a \bmod p$ , where $g$ is generator. So if prime is too large it takes a lot of time to find $a$, because you need to try all the elements in $1..p$.

that is based on DLP(Discrete Logarithm Problem).


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.