I have a primitive $A$ which is impossible to prove under some hardness assumption in a black-box way. Now, if another primitive $B$ is stronger than $A$ - in other words $B$ implies $A$ - will it imply that $B$ is also impossible to prove under the same hardness assumption in a black-box way?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ If B implies A in a black box way, then yes, this just follows immediately from what you stated and the transitivity of black box reductions. $\endgroup$– MikeroAug 10, 2018 at 1:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This seems like a logic question: $B$ implies $A$, therefore not $A$ implies not $B$
Proving $B$ would prove $A$, so if it is impossible to prove $A$ it must be impossible to prove $B$ in the same setup.
Alternatively lets assume $B$ is proven, since $B$ implies $A$, $A$ is proven. Yet $A$ is unproveable: a contradiction.
