# How much do we trust KEA1 Assumption?

Let $$(g,h=g^s,q)$$ be a tuple such that $g$ is a generator for a group $\mathbb{G}$ of ord $q$ and $s$ is uniformly random in $\mathbb{Z}_q$.

The KEA1 Assumption saies that for any adversary $\mathcal{A}(g,h,q)$ that outputs a value $(C,Y)$ such that $C^s \equiv Y$ then there exists a extractor $\mathcal{B}$ that on the same input outputs a value $x$ such that $g^x \equiv C$.

The assumption, roughly speaking, saies that the only way to compute the tuple $(C,Y)$ is, actually, by knowing the exponent $x$.

This assumption was first proposed by Ivan Damgard in the paper "Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks" in the '91.

My question is, how much do we trust this assumption? Is it reducible to something else?

-
Could you check your notation? It looks like the only $S$ you used should be something else. –  Paŭlo Ebermann Jan 26 '13 at 22:17

I'm not sure how to answer the question about "trust" in the assumption. I suppose that is a matter of personal belief more than science. We don't know the truthfulness about any cryptographic assumptions, although obviously some have received more scrutiny than others. I'd say that the KEA assumptions have received relatively little attention, and so should be avoided if possible. However, I suspect that if you're asking the question, then it's not possible to avoid it.

As to the reducibility question, it's not reducible to anything that one might call a "standard" assumption. This is in fact by design. Standard assumptions, such as the RSA assumption or the DDH assumption, are "falsifiable" in the sense that if the assumption is false, then it is (in principle) easy to show a counterexample. In the case of RSA or DDH, the counterexample would be an algorithm A that successfully breaks the hard problems. Even if you have no idea how A works, it'd be pretty easy to verify that A is in fact a valid attacker just by sampling RSA composites/DDH tuples at random and seeing how often A succeeds.

By contrast, the knowledge of exponent assumption is one of the few non-falsifiable assumptions that cryptographers use. (The most common non-falsifiable "assumption" would be the concept of a random oracle, although that's not really an assumption per se.) It's possible that KEA1 is false, but it's not possible for me to prove to you that it's false just by showing you some simple witness to this claim.

-
Thanks! that was what I meant concerning the "trust". i.e. how many researchers have studied this assumption and how much we know about that. –  AntonioFa Jan 26 '13 at 16:36
the answer you gave is wonderful! KEA1 assumption is always very weird for me. Are there some plain words to describe it? And if a protocol(say key-exchange) is based on it, then if we can say that it's not good or insecure ? –  T.B Oct 15 '13 at 8:08