Main Content

Current Members Krzysztof Pietrzak (Professor)
Joël Alwen (Postdoc)
Maciej Skorski (Postdoc)
Michael Walter (Postdoc)
Hamza Abusalah (PhD. student)
Chethan Kamath (PhD. student)
Karen Klein (PhD. student)
Group picture
Chethan Kamath, Michael Walter, Karen Klein, Krzysztof Pietrzak, Hamza Abusalah, Joël Alwen
Research Interests

The cryptography group at IST Austria works on theoretical and practical aspect of cryptography. Here's a selection of current research topics:

  • Memory-hard Functions (MHF) are functions which require a large amount of memory to be evaluated. Despite having found many applications, until recently there were no meaningful security proofs MHFs at all. MHFs come in two flavours, data-dependent and data-independent. In [ACPRT'17] (Best Paper Award at Eurocrypt'17) we show that Scrypt is an "optimal" data depentend MHF. In [ABP'16] we show how "depth robust" graphs give rise to data independent MHFs with optimal parameters. In a series of papers [AB'16a],[AB'16b],[AGK+'16b] we break most of the proposals of data-independent MHFs.

  • Crypto for light-weight devices. We work towards provably secure cryptographic schemes for light-weight devices such as RFID tags, which are too constrained to run existing cryptographic schemes. In [KPC+'11] (Best Paper Award at Eurocrypt'11) and [HKL+'12] we construct extremely efficient and provably secure authentiaction schemes based on the the (ring) LPN problems. In [JKPT'12],[BKLP'15] we give commitments with effecient zero-knowledge proofs from the same assumption.

  • Symmetric Cryptography. We develop new tools to construct and analyze symmetric (aka secret key) primitives. One focus lies is determening the exact security of popular schemes. We gave such tight bounds for HMAC [GPR'14] (and variants  [GPT'15]), PMAC [GPR'17] and CBC [GPT'15]
  • Sustainable Cryptocurrencies. Bitcoin is the first successful digital currency. Its popularity comes from the fact that it is decentralised, so no central authority controls it. To achieve security despite decentralisation a huge amount of computing power is constantly wasted towards generating Proofs of Work, this is economically and ecologically problematic. We work on more "sustainable" cryptocurrencies. Towards this goal we introduced the concept of "Proofs of Space" [DFKP'15],[ACK+'16] as a replacement for Proofs of Work, and a cryptocurrency called Spacemint [PPK+'15] based on this proof system.

Publications Complete list of publications (under construction)

Most recent:

Bram Cohen and Krzysztof Pietrzak
Simple Proofs of Sequential Work (Best Paper Award)
Eurocrypt 2018
[full version]

Joël Alwen, Jeremiah Blocki and Krzysztof Pietrzak
Sustained Space Complexity
Eurocrypt 2018
[full version]

Daniele Micciancio and Michael Walter
On the Bit Security of Cryptographic Primitives
Eurocrypt 2018
[full version]

Maciej Obremski and Maciej Skorski
Renyi Entropy Estimation Revisited
Approx-Random 2017
[proceedings] [full version]

Maciej Skorski
On the Complexity of Breaking Pseudoentropy
TAMC 2017
[proceedings] [full version]

Joël Alwen, Jeremiah Blocki and Ben Harsha
Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions
ACM CCS 2017
[proceedings] [full version]

Hamza Abusalah, Joël Alwen, Bram Cohen, Danylo Khilko, Krzysztof Pietrzak, Leonid Reyzin
Beyond Hellman's Time-Memory Trade-Offs with Applications to Proofs of Space
Asiacrypt 2017
[full version]

Krzysztof Pietrzak and Maciej Skorski
Non-Uniform Attacks Against Pseudoentropy
ICALP 2017
[proceedings] [full version]

Joshua Brody, Stefan Dziembowski, Sebastian Faust and Krzysztof Pietrzak
Position-Based Cryptography and Multiparty Communication Complexity
TCC 2017
[proceedings] [full version]

Eike Kiltz, Krzysztof Pietrzak, Daniele Venturi, David Cash and Abhishek Jain
Efficient Authentication from Hard Learning Problems
Journal of Cryptography 2017

Zahra Jafargholi, Chethan Kamath, Karen Klein, Ilan Komargodski, Krzysztof Pietrzak and Daniel Wichs
Be Adaptive, Avoid Overcommitting
Crypto 2017
[proceedings] [full version]

Joël Alwen and Jeremiah Blocki and Krzysztof Pietrzak
Depth-Robust Graphs and Their Cumulative Memory Complexity
Eurocrypt 2017
[proceedings] [full version]

Joël Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro
Scrypt is Maximally Memory-Hard (Best Paper Award)
Eurocrypt 2017
[proceedings] [full version]

Peter Gaži, Krzysztof Pietrzak and Michal Rybár
The Exact Security of PMAC
ToSC 2017, Volume 1, and FSE 2017
[article] [full version]

Joël Alwen, Jeremiah Blocki
Towards Practical Attacks on Argon2i and Balloon Hashing
Euro S&P 2017
[proceedings] [full version]

Joël Alwen, Susanna F. de Rezende, Jakob Nordström and Marc Vinyals
Cumulative Space in Black-White Pebbling and Resolution
ITCS 2017

Maciej Skorski
Key Derivation for Squared-Friendly Applications: Lower Bounds
STACS 2017
[proceedings] [full version]

Krzysztof Pietrzak, Maciej Skorski
Pseudoentropy: Lower-Bounds for Chain Rules and Transformations
TCC (B1) 2016
[proceedings] [full version]

Maciej Skorski
Simulating Auxiliary Inputs, Revisited
TCC (B1) 2016
[proceedings] [full version]

Stephan Krenn, Krzysztof Pietrzak, Akshay Wadia, Daniel Wichs
A counterexample to the chain rule for conditional HILL entropy
Computational Complexity 2016
[article] [full version]

Georg Fuchsbauer, Felix Heuer, Eike Kiltz, Krzysztof Pietrzak
Standard Security Does Imply Security Against Selective Opening for Markov Distributions
TCC (A1) 2016
[proceedings] [full version]

Georg Fuchsbauer, Christian Hanser, Chethan Kamath and Daniel Slamanig
Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions
SCN 2016
[proceedings] [full version]

Chethan Kamath and  Sanjit Chatterjee
A Closer Look at Multiple-Forking: Leveraging (In)dependence for a Tighter Bound
Algorithmica 2016, Volume 74
[full version]

Joël Alwen, Binyi Chen, Chethan Kamath, Vladimir Kolmogorov, Krzysztof Pietrzak and Stefano Tessaro
On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model
Eurocrypt 2016
[full version]

Joël Alwen, Jeremiah Blocki
Efficiently Computing Data-Independent Memory-Hard Functions
[full version]

Peter Gaži, Stefano Tessaro
Provably Robust Sponge-Based PRNGs and KDFs
Advances in Cryptology — Eurocrypt 2016, Lecture Notes in Computer Science, Springer-Verlag, 2016
[proceedings] [full version]

Hamza Abusalah, Georg Fuchsbauer, Krzysztof Pietrzak
Constrained PRFs for Unbounded Inputs
CT-RSA 2016
[proceedings] [full version]

Hamza Abusalah, Georg Fuchsbauer
Constrained PRFs for Unbounded Inputs with Short Keys
ACNS 2016
[proceedings] [full version]

Hamza Abusalah, Georg Fuchsbauer, Krzysztof Pietrzak
Offline Witness Encryption
ACNS 2016
[proceedings] [full version]

Former Members Stephan Krenn (Postdoc) - now at Austrian Institute of Technology
Georg Fuchsbauer (Postdoc) - now at ENS Paris
Peter Gaži (Postdoc) - now at IOHK
Michal Rybar (PhD)

Summer students and interns Anastasia Kucherenko , Taras Shevchenko National University of Kyiv (ISTern, Summer 2017)
Mukesh Pareek , IIT Bombay (ISTern, Summer 2017)
Hana Dlouhá , CTU in Prague (ISTern, Summer 2017)
Teresa Steiner, TU Wien (student intern, 2016)
Danylo Khilko, Taras Shevchenko National University of Kyiv (ISTern, 2016)
Zahra Jafargholi, UCLA (graduate summer student, 2014)
Maciej Skorski, University of Warsaw (graduate summer student, 2012/13/14/15)
Sophie Stevens, Bristol (ISTernship, 2014)
Kristian Tokmakov, Oxford (ISTernship, 2014)
Alexander Golovnev, NYU (graduate summer student, 2014)
Momchil Konstantinov, Oxford (ISTernship, 2013)
Vanishree Rao, UCLA (graduate summer student, 2013)
Akshay Wadia, UCLA (graduate summer student, 2012)
Aris Tentes, NYU (graduate summer student, 2011)

Applicants If you are interested in doing a PhD in this group (or at IST Austria in general), please visit the Graduate School homepage. If you are interested in a postdoc position, please contact Krzysztof Pietrzak directly.