# 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