An identification scheme involves two parties, a prover A and a verifier B. In such a scheme prover A wants to convince verifier B that A is really A. In cryptography this can be achieved in an interactive protocol during which B gets convinced that A has a solution to a difficult problem. In this protocol, B learns nothing but the belief that A has a solution to a known instance of the problem. As these protocols allow for efficient implementation, they play an important role for the security of information transmission. Therefore several indentification schemes have been proposed which are based on various apparently hard problems.
In this talk an attack on an identification scheme based on a combinatorial problem, the Permuted Perceptron Problem, is described. This problem is motivated by Neural Computing. The basic idea of the attack is to use several applications of Simulated Annealing and to combine the outcomes into an iterated search. As a consequence, the identification scheme based on the Permuted Perceptron Problem is several orders of magnitude less secure than previously believed.