Report
Teaser, summary, work performed and final results
Periodic Reporting for period 2 - TOCNeT (Teaching Old Crypto New Tricks)
Teaser
The bulk of the research in modern cryptography goes into constructing new schemes for which stronger security guarantees can be proven. However, often it is not clear whether simple existing schemes already provide the required security, and it’s just that we don’t know...
Summary
The bulk of the research in modern cryptography goes into constructing new schemes for which stronger security guarantees can be proven. However, often it is not clear whether simple existing schemes already provide the required security, and it’s just that we don’t know how to prove it. As these new schemes are usually less efficient, there are not being applied resulting in a large discrepancy between what security the schemes applied in practice are supposed to provide, and what is actually proven. This project aims at closing this gap in different contexts: We will revisit simple schemes (including widely deployed ones) using new tools, developed by us and others in the last years, towards proving much stronger security properties than what is currently known.
The schemes developed and proven secure in this project will allow for more efficient and/or more secure solution to various challenges of information security.
A notable early result of this project is a proof that SCRYPT is memory-hard, this function was already widely deployed -- in blockchains and for password hashing -- without any formal security guarantees (this result won the Eurocrypt’17 best paper award).
Work performed
We made progress on several of the work packages, but we also started some new projects which fall into the general theme of the project which were not foreseen in the original proposal. Let us first mention the main results for each of the three work packages.
WP1 (adaptive security). At CRYPTO’17 we published a paper entitled “Be Adaptive, Avoid Overcommitting†which provides a general methodology to prove adaptive security of schemes. This methodology unifies and simplifies several previous results (by us and others), and has also been useful in proving new results. We’re currently looking for further applications of this technique.
WP2 (symmetric cryptography). In the paper “The Exact Security of PMAC†which appeared at FSE’17 (and was invited to the Journal of Cryptology) we determine the exact security of PMAC, which is a popular message authentication code. This result is not only important as PMAC is a popular scheme, and thus we should know it’s exact security, but also because many of the candidates of the currently running CEASAR competition (which aims at standardizing a authenticated encryption scheme) are based on the design principles of PMAC.
WP3 (pseudoentropy). After making progress on proving many positive results on various computational entropy notions during my previous ERC grant, we now started investigating from the other direction. That is, proving lower bounds to understand how far we can possibly push this line of research. The two main publications in this direction were “Non-Uniform Attacks Against Pseudoentropy†at ICALP’17 and “Pseudoentropy: Lower-Bounds for Chain Rules and Transformations†at TCC’17.
Final results
Two topics we worked on which fall into the aim of the project but were not already suggested as work packages in the proposal are “memory hard functions†(MHF) and “proofs of space†(PoS).
We have several papers on MHFs published or currently under submission. Our proof that scrypt is memory hard won the best paper award at Eurocrypt’17.
PoS will be used in an upcoming cryptocurrency https://chia.network/ where I’m involved in (as scientific advisor).
Website & more info
More info: http://pub.ist.ac.at/crypto/ToCNET.html.