How much do we trust KEA1 Assumption?

Question

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 knowledge of exponent (KEA1) assumption says 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, says that the only way to compute the tuple $(C,Y)$ is, actually, by knowing the exponent $x$.

This assumption was first proposed by Ivan Damgård 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?

Answer 1

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.