3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 3
    $\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, 2018 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, 2018 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, 2018 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, 2018 at 18:29
  • 1
    $\begingroup$ @Pierre21 Can you use the edit link below the question and tags to incorporate the information you posted in the comments into the body of the question? $\endgroup$
    – Ella Rose
    Jan 6, 2019 at 3:40

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ The best known methods to solve for $a$ a DLP problem $g^a \bmod p=b$ are much faster than trying elements in $[1…p)$, which has cost $\mathcal O(p\ln(p)\ln(\ln(p)))$, thus exponential în the size of $p$. We know subexpoential algorithms. see this for the current state of the art, and references. $\endgroup$
    – fgrieu ♦
    Jul 28, 2022 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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