Director, Certicom Research
Matthew Campagna joined Certicom in 2007 as the Director of Research. At Certicom, Matthew has been focused on defining strategy for Research, Standardization, and Intellectual Property generation. Matthew has specialized on development of efficient implementation and the development of new cryptographic primitives using elliptic curve cryptography.
Prior to joining Certicom, Matthew managed the Secure Systems research group at Pitney Bowes' Advanced Concepts and Technology division. In addition to managing Matthew functioned as the group's lead cryptographic researcher. Matthew focused was on developing, engineering and deploying efficient public key systems for low cost and low computing power devices communicating over restricted communication channels. Matthew worked for the National Security Agency as a senior cryptologic mathematician focused on commercial cryptography. He holds a Ph.D. in mathematics from Wesleyan University in group theory, and a bachelor’s degree in mathematics from Fordham University.
NIST has opened a public competition to develop a new cryptographic hash algorithm, which converts a variable length message into a short “message digest” that can be used for digital signatures, message authentication and other applications. The competition is NIST’s response to recent advances in the cryptanalysis of hash functions. The new hash algorithm will be called “SHA-3” and will augment the hash algorithms currently specified in FIPS 180-2, Secure Hash Standard.
A brief background on cryptographic hashing
A cryptographic hash function is a deterministic procedure that takes as input an arbitrary block of data and produces a fixed length output with three specific properties:
1. Pre-image resistance: given a hash value it is computationally infeasible to find an input that hashes to that value.
2. 2nd pre-image resistance: given an input value it is computationally infeasible to find a second input value that hashes to the same value.
3. Collision resistance: it is computationally infeasible to find two distinct inputs that hash to the same value.
A brief description of the Certicom ECOH submission
The elliptic curve only hash (ECOH) algorithm is a submission to NIST’s SHA-3 competition. The ECOH algorithm is based on the MuHASH algorithm of Bellare and Micciancio. ECOH is based on elliptic curve cryptography over binary fields. The scheme is defined to provide hash algorithms for the 112, 128, 192 and 256 cryptographic bit strengths. In addition to meeting the requirements set by NIST there are a number of other advantages that ECOH provides including:
1. Security Analysis: The ECOH SHA-3 submission includes heuristic security arguments relating the security of ECOH to the hardness of the elliptic curve discrete logarithm problem. We believe that the additional assurance provided by these arguments will be unique among traditional hashing scheme submissions.
2. Parallelization: The scheme lends itself to take advantage of parallelizing much of the computation. In the age of increasing multi-core systems replacing traditional processor speed as the means of computational advancement this is considered a significant advantage in designing a hash scheme.
3. Incrementable: The scheme lends itself to incremental changes of the hash value based on the input value. That is if the input value changes by a small amount then instead of recomputing the hash value it can be more quickly updated through incrementation. This would be a significant advantage in spaces like hashing a disk image.
4. Carry-less Multiplication: Intel has introduced a new set of instructions known as AVX that contains operations that perform carry-less multiplication. These new instructions will speed-up binary curve arithmetic on general CPUs.