Project

Back to overview

Efficient cryptographic hashing with provable properties

English title Efficient cryptographic hashing with provable properties
Applicant Lenstra Arjen K.
Number 116712
Funding scheme Project funding
Research institution Laboratoire de cryptologie algorithmique EPFL - IC - IIF - LACAL
Institution of higher education EPF Lausanne - EPFL
Main discipline Information Technology
Start/End 01.09.2007 - 31.08.2010
Approved amount 146'035.00
Show all

Keywords (4)

Cryptology; Cryptographic hashing; Provability; Pseudorandomness

Lay Summary (English)

Lead
Lay summary
Since the announcement in 2004 of unexpectedly successful cryptanalysis of common cryptographic hash functions, the cryptographic hash world has been in a state of turmoil. We now know for sure that the hash functions that are used by all popular Internet browsers to secure our communications, are not as strong as they should be. Furthermore, there is suspicion that the planned successors of these hash functions are vulnerable too. Finally, although most agree that something needs to be done, there is no consensus what.

So far, the design of practical cryptographic hash functions has been
heuristic: approaches that are not based on firm mathematical principles, but that are efficient and that were believed to resist attacks. This latter belief has now proved wrong, at least for the commonly used hash functions, thereby undermining the traditional design approach. The objective of this proposal is to investigate a different design approach where a successful attack can be proved to be equivalent to solving a hard mathematical problem.

The `provable' approach to cryptographic hash function design has never been popular because of the relative inefficiency of provable hashes compared to heuristic ones. This is now changing, mainly due to the recently discovered weaknesses in the heuristic hashes. These recent attacks brought to a sudden end the period of complacency in hash research and inspired, among others, a promising new approach to provable hash function design that was published earlier this year. This new approach, called VSH for "very smooth hash", links the security of the hash function to the well-known integer factoring problem (a problem that is widely believed to be hard). Even though VSH is still less efficient than the successfully attacked heuristic hashes, it is considerably faster than any of the previously existing hashes with provable security properties. Also, the method allows for many variations that this project intends to explore.
More specifically, it aims to study improvements of VSH on the following fronts:


speed: Careful (software and hardware) implementations should close the performance gap to a large extent.
footprint: Study methods to succinctly represent a large table of small primes.
size: Use discrete logarithm variants, along with compression or elliptic curve methods to reduce VSH's output size.
pseudorandomness: Study how recent results in pseudorandom number generation may be applied to improve VSH's pseudorandomness properties.

Simultaneous success on all fronts would result in an efficient cryptographic hash function with provable attack resistance properties.
This may have important practical implications.
Direct link to Lay Summary Last update: 21.02.2013

Responsible applicant and co-applicants

Employees

Name Institute
Sarinay Juraj

Associated projects

Number Title Start Funding scheme
117409 Potential of a cell cluster for scientific computing 01.07.2007 R'EQUIP

-