**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**3

# formal proof system Related Publications

##### 3 A Formal Approach for Proof Constructions in Cryptography

**Authors:**
Markus Kaiser,
Johannes Buchmann

**Abstract:**

**Keywords:**
prime numbers,
primality tests,
formal proof system,
higher-order logic,
Bayes' Formula,
Miller-Rabin primality test,
(conditional) probabilitydistributions,
formalverification

##### 2 Computer Verification in Cryptography

**Authors:**
Markus Kaiser,
Johannes Buchmann

**Abstract:**

In this paper we explore the application of a formal proof system to verification problems in cryptography. Cryptographic properties concerning correctness or security of some cryptographic algorithms are of great interest. Beside some basic lemmata, we explore an implementation of a complex function that is used in cryptography. More precisely, we describe formal properties of this implementation that we computer prove. We describe formalized probability distributions (o--algebras, probability spaces and condi¬tional probabilities). These are given in the formal language of the formal proof system Isabelle/HOL. Moreover, we computer prove Bayes' Formula. Besides we describe an application of the presented formalized probability distributions to cryptography. Furthermore, this paper shows that computer proofs of complex cryptographic functions are possible by presenting an implementation of the Miller- Rabin primality test that admits formal verification. Our achievements are a step towards computer verification of cryptographic primitives. They describe a basis for computer verification in cryptography. Computer verification can be applied to further problems in crypto-graphic research, if the corresponding basic mathematical knowledge is available in a database.

**Keywords:**
prime numbers,
formal verification,
primality tests,
(conditional) proba¬bility distributions,
formal proof system,
higher-order logic,
Bayes' Formula,
Miller-Rabin primality test

##### 1 A Computer Proven Application of the Discrete Logarithm Problem

**Authors:**
Sebastian Kusch,
Markus Kaiser

**Abstract:**

In this paper we analyze the application of a formal proof system to the discrete logarithm problem used in publickey cryptography. That means, we explore a computer verification of the ElGamal encryption scheme with the formal proof system Isabelle/HOL. More precisely, the functional correctness of this algorithm is formally verified with computer support. Besides, we present a formalization of the DSA signature scheme in the Isabelle/HOL system. We show that this scheme is correct what is a necessary condition for the usefulness of any cryptographic signature scheme.

**Keywords:**
formal verification,
formal proof system,
higher-order logic,
cryptographic signature scheme