  Simulatability condition is a fundamental concept in studying key generation
over a non-authenticated public channel, in which Eve is active and can
intercept, modify and falsify messages exchanged over the non-authenticated
public channel. Using this condition, Maurer and Wolf showed a remarkable "all
or nothing" result: if the simulatability condition does not hold, the key
capacity over the non-authenticated public channel will be the same as that of
the case with a passive Eve, while the key capacity over the non-authenticated
channel will be zero if the simulatability condition holds. However, two
questions remain open so far: 1) For a given joint probability mass function
(PMF), are there efficient algorithms (polynomial complexity algorithms) for
checking whether the simulatability condition holds or not?; and 2) If the
simulatability condition holds, are there efficient algorithms for finding the
corresponding attack strategy? In this paper, we answer these two open
questions affirmatively. In particular, for a given joint PMF, we construct a
linear programming (LP) problem and show that the simulatability condition
holds \textit{if and only if} the optimal value obtained from the constructed
LP is zero. Furthermore, we construct another LP and show that the minimizer of
the newly constructed LP is a valid attack strategy. Both LPs can be solved
with a polynomial complexity.
