trace and indistinguishability properties

Since 1981, a large variety of formal methods for the analysis of cryptographic protocols has evolved. In particular, the tool-supported inductive method has been applied to many protocols. Despite several improvements, the scope of these and other approaches is basically restricted to the simple enc-dec scenario (decryption reverts encryption) and to standard properties (confidentiality and authentication). In this thesis, we broaden the scope of the inductive method to protocols with algebraically specified cryptographic primitives beyond the simple enc-dec scenario and to indistinguishability properties like resistance against offline testing. We describe an axiomatization of message structures, justified by a rewriting-based model of algebraic equations, to provide complete case distinctions and partial orders thereby allowing for the definition of recursive functions and inductive reasoning. We develop a new proof technique for confidentiality properties based on tests of regular messages. The corresponding recursive functions are provably correct wrt. to an inductively defined attacker model. We introduce generic derivations to express indistinguishability properties. A central theorem then provides necessary and sufficient conditions that can be shown by standard trace properties. The general aspects of our techniques are thoroughly discussed and emphasized, along with two fully worked out real world case studies: PACE and TC-AMP are (to be) used for the German ID cards. To the best of our knowledge TC-AMP is among the most complex algebraically specified protocols that have been formally verified. In particular, we do not know of any approaches that apply formal analysis techniques to comparable cases