Cryptography Group at IST Austria

Current Members Krzysztof Pietrzak (Professor)
Benedikt Auerbach (Postdoc)
Georgia (Zeta) Avarikioti (Postdoc)
Suvradip Chakraborty (Postdoc)
Michael Walter (Postdoc)
Karen Klein (PhD. student)
Guillermo Perez (PhD. student)
Michelle Yeo (PhD. student)
Mirza Baig (PhD. student)
Charlotte Hoffmann (PhD. student)
Group picture (summer 2019)
Chethan Kamath, Michelle Yeo, Michael Walter, Guillermo Perez, Krzysztof Pietrzak, Miguel Cueto (ISTern), Ahmadreza Rahimi (visiting), Margarita Capretto (ISTern), Karen Klein
Research Interests

The cryptography group at IST Austria works on theoretical and practical aspect of cryptography.

Several of our current topics involve graph-pebbling as described here, here you can try to consruct a hard to pebble graph.

Some of our current research interest are
  • 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],[Pie'19] as a replacement for Proofs of Work. An academic proposal using proofs of space is the Spacemint cryptocurrency [PPK+'15]. We are involved with the Chia network which will combine proofs of space with verifiable delay functions (VDF).

  • 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]
Publications Most recent:

Georg Fuchsbauer, Chethan Kamath, Karen Klein, Krzysztof Pietrzak
Adaptively Secure Proxy Re-encryption
Public Key Cryptography (PKC) 2019
[full version]

Hamza Abusalah, Chethan Kamath Karen Klein, Krzysztof Pietrzak, Michael Walter
Reversible Proofs of Sequential Work
Eurocrypt 2019
[full version]

Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy N. Rothblum
Finding a Nash Equilibrium is No Easier than Breaking Fiat-Shamir
STOC 2019
[full version]

Michael Walter
Sampling the Integers with Low Relative Error
[full version]

Krzysztof Pietrzak
Simple Verifiable Delay Functions
Innovations in Theoretical Computer Science (ITCS) 2019
[full version]

Krzysztof Pietrzak
Proofs of Catalytic Space
Innovations in Theoretical Computer Science (ITCS) 2019
[full version]

Stefan Dziembowski, Krzysztof Pietrzak and Daniel Wichs
Non-Malleable Codes
Journal of the ACM, Volume 65 Issue 4, August 2018
[article][full version]

Joel Alwen, Peter Gazi, Chethan Kamath, Karen Klein, Georg Osang, Krzysztof Pietrzak, Leonid Reyzin, Michal Rolinek and Michal Rybar
On the Memory-Hardness of Data-Independent Password-Hashing Functions
AsiaCCS 2018
[full version]

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

Joel 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]

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

Hamza Abusalah, Joel 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]

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

Joel 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 Gazi, Krzysztof Pietrzak and Michal Rybar
The Exact Security of PMAC
ToSC 2017, Volume 1, and FSE 2017
[article] [full version]

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

Joel 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]

Joel 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]

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

Peter Gazi, 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]

some older publications
Former Members Chethan Kamath (PhD student, graduated 2020)
Hamza Abusalah (PhD student, graduated 2018)
Joel Alwen (Postdoc) - now at Wickr
Maciej Skorski (Postdoc)
Peter Gazi (Postdoc) - now at IOHK
Georg Fuchsbauer (Postdoc) - now at ENS Paris
Michal Rybar (PhD. student, graduated 2017)
Stephan Krenn (Postdoc) - now at Austrian Institute of Technology

Visting students and interns Ahmadreza Rahimi, University of Virginia (visiting PhD student, 2019)
Margarite Capretto, University of Rosaria/Argentina, (ISTern, Summer 2019)
Miguel Cueto, University of Oviedo/Spain, (ISTern, Summer 2019)
Arka Rai Choudhuri , John Hopkins, (graduate summer student, 2018)
Samarth Tiwari , New York University (ISTern, Summer 2018)
Sasha Lapiga , Taras Shevchenko National University of Kyiv (ISTern, Summer 2018)
Anastasia Kucherenko , Taras Shevchenko National University of Kyiv (ISTern, Summer 2017)
Mukesh Pareek , IIT Bombay (ISTern, Summer 2017)
Hana Dlouha , 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.