Basic Research in Cryptographic Protocol Theory

ERC Starting Grant 279447

Last update on: 27/01/2015

About the Team

We are a team of researchers focusing on various topics of fundamental nature within cryptographic protocol theory, such as Security Models, Rational Cryptography, Quantum Cryptography, Leakage Resilience and Tamper Resilience. We are funded by European Research Council (ERC) Starting Grant 279447. We would like to thank the ERC for making this research possible!

People

Apart from the Principal Investigator, Jesper Buus Nielsen, the team is composed by 2 PhD Students and 2 PostDoc fellows. A PhD thesis and a PostDoc fellowship have already been successfully completed as part of this project. Being part of the Cryptography and Security Group at Aarhus University, our team collaborates closely with other members of this group.

Menu

Publications

Here you can find a list of publications in refereed journals and conferences that resulted from research done by the team. A publication is listed if one or more team members is an author of the publication. Often there are also co-authors who are not part of the project team on the articles, meaning that the article was also funded by other sources.

2016

Jesper Buus Nielsen, Samuel Ranellucci: Reactive Garbling: Foundation, Instantiation, Application. ASIACRYPT 2016. [Full version]

Jesper Buus Nielsen, Claudio Orlandi: Cross and Clean: Amortized Garbled Circuits with Constant Overhead. TCC 2016. [Full version]

Antonio Faonio, Daniele Venturi: Efficient Public-Key Cryptography with Bounded Leakage and Tamper Resilience. ASIACRYPT 2016. [Full version]

Samuel Ranellucci, Alain Tapp, Rasmus Zakarias: Efficient Generic Zero-Knowledge Proofs from Commitments. ICITS 2016. [Full version]

Ignacio Cascudo, Ivan Damgård, Felipe Lacerda, Samuel Ranellucci: Oblivious Transfer from Any Non-trivial Elastic Noisy Channel via Secret Key Agreement. TCC 2016. [Full version]

Nico Döttling : Low Noise LPN: KDM Secure Public Key Encryption and Sample Amplification. IET Information Security. [Full version]

Nico Döttling, Nils Fleischhacker, Dominque Schröder and Johannes Krupp : Two Message Oblivious Evaluation of Cryptographic Functionalities. CRYPTO 2016. [Full version]

Tore Kasper Frederiksen, Thomas P. Jakobsen, Jesper Buus Nielsen, Roberto Trifiletti: On the Complexity of Additively Homomorphic UC Commitment Schemes. TCC 2016-A. Pages 542-565. [Full version]

Ignacio Cascudo, Bernardo David, Ivan Damgård, Nico Döttling and Jesper Buus Nielsen : Rate-1, Linear Time and Additively Homomorphic UC Commitments. CRYPTO 2016. [Full version]

Ivan Damgård, Jesper Buus Nielsen and Antigoni Polychroniadou: On the Communication required for Unconditionally Secure Multiplication CRYPTO 2016. [Full version]

Sebastian Faust, Carmit Hazay, Jesper Buus Nielsen, Peter Sebastian Nordholt, Angela Zottarel : Signature Schemes Secure Against Hard-to-Invert Leakage. J. Cryptology 29(2). Pages 422-455 (2016). Springer. [Full version]

Ivan Damgård, Jesper Buus Nielsen, Rafail Ostrovsky, Adi Rosén: Unconditionally Secure Computation with Reduced Interaction. EUROCRYPT (2) 2016. Pages 420-447 [Full version]

2015

Sebastian Faust, Pratyay Mukherjee, Jesper Buus Nielsen, Daniele Venturi : A Tamper and Leakage Resilient von Neumann Architecture. Public Key Cryptography 2015. Pages 579-603. Springer. [Full version]

Ivan Damgård, Frédéric Dupuis, Jesper Buus Nielsen: On the Orthogonal Vector Problem and the Feasibility of Unconditionally Secure Leakage-Resilient Computation. ICITS 2015. Pages 87-104. Springer. [Full version]

Tore Kasper Frederiksen, Jesper Buus Nielsen, Claudio Orlandi : Privacy-Free Garbled Circuits with Applications to Efficient Zero-Knowledge. EUROCRYPT (2) 2015. Pages 191-219. [Full version]

Nico Döttling, Daniel Kraschewski, Jörn Müller-Quade and Tobias Nilges : From stateful hardware to resettable hardware using symmetric assumptions. ProvSec 2015. [Full version]

Nico DDöttlingttling and Dominique Schröder : Efficient Pseudorandom Functions via On-the-Fly Adaptation. CRYPTO 2015. [Full version]

Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions Ronald Cramer, Ivan Damgård, Nico Döttling, Serge Fehr and Gabriele Spini EUROCRYPT 2015. [Full version]

Antonio Faonio, Jesper Buus Nielsen, Daniele Venturi : Mind Your Coins: Fully Leakage-Resilient Signatures with Graceful. ICALP 2015. Pages 456-468. [Full version]

Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo: Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions. Journal of Cryptology 2015. [Full version]

Bernardo Machado David, Rafael Dowsley, Jeroen van de Graaf, Davidson Marques, Anderson C. A. Nascimento, Adriana C. B. Pinto : Unconditionally Secure, Universally Composable Privacy Preserving Linear Algebra. IEEE Transactions on Information Forensics and Security 11(1). Pages 59-73. [Full version]

Irene Giacomelli, Ruxandra F. Olimid, Samuel Ranellucci : Security of Linear Secret-Sharing Schemes Against Mass Surveillance. CANS 2015. Pages 43-58. [Full version]

Bernardo Machado David, Ryo Nishimaki, Samuel Ranellucci, Alain Tapp : Generalizing Efficient Multiparty Computation. ICITS 2015. Pages 15-32. [Full version]

Bernardo David, Rafael Dowsley and Anderson Nascimento: Efficient Unconditionally Secure Comparison and Privacy Preserving Machine Learning Classification Protocols. ProvSec 2015. Pages 354-367. [Full version]

Nico Döttling, Daniel Kraschewski, Jörn Müller-Quade, Tobias Niles : General Statistically Secure Computation with Bounded-Resettable Hardware Tokens. TCC 2015. [Full version]

Ignacio Cascudo, Ivan Damgård, Bernardo David, Irene Giacomelli, Jesper Buus Nielsen, Roberto Trifiletti: Additively Homomorphic UC commitments with Optimal Amortized Overhead. PKC 2015. [Full version]

2014

Thomas Pelle Jakobsen, Jesper Buus Nielsen, Claudio Orlandi: Framework for Outsourcing of Secure Computation. CCSW 2014. Pages 81-92. [Full version]

Pavel Hubáček, Sunoo Park: Cryptographically blinded games: leveraging players' limitations for equilibria and profiit. EC'14. Pages 207-208. [Full version]

Ivan Damgård, Bernardo David, Irene Giacomelli, Jesper Buus Nielsen: Compact VSS and Efficient Homomorphic UC Commitments. ASIACRYPT 2014. Pages 213-232. [Full version]

Ivan Damgård, Jesper Buus Nielsen: Adaptive versus Static Security in the UC Model. ProvSec 2014. Pages 10-28. [Full version]

Ivan Damgård, Rasmus Lauritsen, Tomas Toft: An Empirical Study and Some Improvements of the MiniMac Protocol for Secure Computation. SCN 2014. Pages 398-415. [Full version]

Tore Kasper Frederiksen, Thomas P. Jakobsen, Jesper Buus Nielsen: Faster Maliciously Secure Two-Party Computation Using the GPU. SCN 2014. Pages 339-356. [Full version]

Bernardo David, Rafael Dowsley and Anderson Nascimento: Universally Composable Oblivious Transfer based on a variant of LPN. CANS 2014. Pages 143-158. [Full version]

Sebastian Faust, Pratyay Mukherjee, Jesper Buus Nielsen, Daniele Venturi: Continuous Non-malleable Codes. TCC 2014. Pages 465-488. [Full version]

Sebastian Faust, Pratyay Mukherjee, Daniele Venturi, Daniel Wichs: Efficient Non-malleable Codes and Key-Derivation for Poly-size Tampering Circuits. EUROCRYPT 2014. Pages 111-128. [Full version]

Jesper Buus Nielsen, Daniele Venturi, Angela Zottarel: Leakage-Resilient Signatures with Graceful Degradation. PKC 2014. Pages 362-379. [Full version]

2013

Ivan Damgård, Sebastian Faust, Pratyay Mukherjee, Daniele Venturi: Bounded Tamper Resilience: How to Go beyond the Algebraic Barrier. ASIACRYPT 2013. Pages 140-160. [Full version]

Helger Lipmaa, Tomas Toft: Secure Equality and Greater-Than Tests with Sublinear Online Complexity. ICALP (2) 2013. Pages 645-656. [Full version]

Jesper Buus Nielsen, Daniele Venturi, Angela Zottarel: On the Connection between Leakage Tolerance and Adaptive Security. PKC 2013. Pages 497-515. [Full version]

Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, Louis Salvail: Superposition Attacks on Cryptographic Protocols. ICITS 2013. Pages 142-161. [Full version]

Tore Kasper Frederiksen, Thomas Pelle Jakobsen, Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi: MiniLEGO: Efficient Secure Two-Party Computation from General Assumptions. EUROCRYPT 2013. Pages 537-556. [Full version]

Pavel Hubáček, Jesper Buus Nielsen, Alon Rosen: Limits on the Power of Cryptographic Cheap Talk. CRYPTO 2013. Pages 277-297. [Full version]

Tore Kasper Frederiksen, Jesper Buus Nielsen: Fast and Maliciously Secure Two-Party Computation Using the GPU. ACNS 2013. Pages 339-356. [Full version]

2012

Frédéric Dupuis, Jesper Buus Nielsen, Louis Salvail: Actively Secure Two-Party Evaluation of Any Quantum Operation. CRYPTO 2012. Pages 794-811. [Full version]

Sebastian Faust, Carmit Hazay, Jesper Buus Nielsen, Peter Sebastian Nordholt, Angela Zottarel: Signature Schemes Secure against Hard-to-Invert Leakage. ASIACRYPT 2012. Pages 98-115. [Full version]

Team Members

The following people are hired as part of the research team:

Bernardo Machado David

Bernardo Machado David

PhD Student
Period: 01.03.2013-30.11.2016
Personal Website: http://cs.au.dk/~bernardo/

Nico Döttling

Nico Döttling

Post Doc
Period: 01.06.2014-31.05.2015
Personal Website: http://cs.au.dk/~nico/

Antonio Faonio

Antonio Faonio

Post Doc
Period: 01.12.2014-30.11.2015
Personal Website: http://cs.au.dk/~faonio

Tore Kasper Frederiksen

Tore Kasper Frederiksen

PhD Student
Period: 01.01.2015-31.07.2015
Personal Website:

Pavel Hubáček

Pavel Hubáček

Post Doc
Period: 01.07.2014-31.08.2014
Personal Website: http://cs.au.dk/~hubacek/

Thomas Pelle Jakobsen

Thomas Pelle Jakobsen

PhD Student
Period: 01.01.2015-14.06.2015
Personal Website: http://www.cs.au.dk/~tpj/

Pratyay Mukherjee

Pratyay Mukherjee

PhD Student
Period: 01.08.2012-30.10.2015
Personal Website: http://cs.au.dk/~pratyay/

Jesper Buus Nielsen

Jesper Buus Nielsen

Associate Professor (Principal Investigator)
Period: 01.12.2011-30.11.2016
Personal Website: http://cs.au.dk/~jbn/

Samuel Ranellucci

Samuel Ranellucci

Post Doc
Period: 01.04.2014-31.03.2015
Personal Website: http://cs.au.dk/~samuel/

Tomas Toft

Tomas Toft

Post Doc
Period: 01.01.2013-16.05.2014
Personal Website: http://cs.au.dk/~ttoft/

Roberto Trifiletti

Roberto Trifiletti

PhD Student
Period: 01.01.2015-31.07.2017
Personal Website: http://cs.au.dk/~fulnir/

Angela Zottarel

Angela Zottarel

PhD Student
Period: 01.12.2011-31.10.2013
Personal Website: http://cs.au.dk/~angela/

Lines of Research

The research team currently focuses on the following lines of research:

Security Models

Modern cryptographic research is based on rigorous mathematical proofs of security that show that a given cryptographic scheme is secure as long a given set of assumptions are true. For example, an encryption scheme can be proven secure as long as factoring large prime numbers is hard and a multiparty computation scheme can be proven secure as long as the parties have access to secure channels. However, in order to achieve such rigorous proofs, it is necessary to precisely define what it means for a cryptographic scheme to be secure. An important part of designing cryptographic schemes consists in defining secure models and understanding the exact security guarantees that they provide. As a general goal, security models should be as close as possible to the real environments where the cryptopgraphic schemes are supposed to be deployed in. For example, if a given scheme is intended to be used in the Internet (e.g. TLS), where it might be employed in cojunction with other schemes or other instances of itself, the security model used to analyse its properties must capture this situation. It turns out that defining meaningful security models that take into consideration all real world characteristics is a non trivial task due to the sheer complexity of real world scenarios. To meet the need for better and more robust security models, new models are continously proposed and analysed. It is also important to study the relations between different security models, determining their basic limits.

Rational Cryptography

Traditional cryptographic security models assume that the parties involved in cryptographic schemes either behave honestly or maliciously with no regards to what they might gain by behaving one way or the other. For example, in a given scenario, a party involved in a cryptographic protocol might be easily detected as dishonest when behaving maliciously and still not obtain any useful outcome (i.e. secret data). On the other hand, there are some scenarios where the risk of getting caught acting maliciously are low compared to the amount of useful outcome. Rational cryptography is an emerging research area which in particular uses the methodologies and techniques of game theory to analyze cryptographic protocols and which uses cryptographic protocol theory to implement game theoretic mechanisms. Using game theoretical models, rational cryptography can formally capture the notion that a parties interacting through a cryptographic protocol will only act maliciously if the possible outcome of their dishonest actions is high enough to justify the risk of being caught. This field also investigates how to use cryptographic techniques to ensure that parties interacting according to a game theoretic model follow the premisses regarding their behaviro in such model.

Quantum Cryptography

Quantum Cryptography consists of using quantum mechanical effects to implement cryptographic schemes. As opposed to their classical counterparts, quantum computers and communication channels are governed by the laws of quantum mechanics. This implies that every measurement of information transmitted or processed by such means is subject to the uncetainty principle and also allows cryptographic scheme designers to explore quantum phenomena such as state entanglement. Since the seminal results that showed how to obtain key exchange protocols with security guarantees superior to those offered by any classical protocol, the properties of quantum mechanics have been used to both construct and break different cryptographic schemes. It was shown that, if quantum computers with sufficient computing power exist, it is possible to obtain efficient solutions to computational problems that are believed to be hard in the classical world, such as factoring large prime numbers, whose hardness is the basis of the widely utilized RSA encryption scheme. Besides using quantum phenomena to implement new schemes or devise more efficient attacks to existing classical schemes, research in this realm also focus on obtaining classical schemes that are (to best of current knowledge) impervious to quantum attacks, representing an alternative to current schemes in case a powerful enough quantum computer is ever invented.

Leakage and Tamper Resilience

Classical models of cryptography often fail to match the practical scenario as traditional security proofs assume that the attacker can access any cryptographic functionality (typically having a secret key) only in a black-box manner which excludes the possibility for physical attacks. In practice, the attacker can execute physical attacks on the implementation of the functionality and get side-information about the secret, making the access rather non-blackbox. These types of attacks are easy to execute (e.g. by measuring power consumption, timing, injecting fault etc.) and numerous works in the past decade showed how to completely break some provably secure scheme (like RSA signature) completely by such attacks. The main goal of leakage and tamper resilient cryptography is to protect against these physical attacks from theoretical perspective. More precisely, leakage-resilient cryptography tries to capture side-channel attacks where the attacker can learn some information about the secret-key. In contrast, tamper-resilient cryptography models the scenario, where the attacker injects fault(s) into the device and then tries to execute it in hope of learning some useful secret information (or breaking the security of the scheme). A large number of recent works has been published in this direction, however, still there are gaps between the practical model and its theoretical approximation. The current goal in this direction is to fill in these gaps or proving some lower bound.

Examples of Results

Here we give some examples of our results. For more details, have a look at the corresponding publications.

Limits on the Power of Cryptographic Cheap Talk

In this work we proved that contrary to folklore not all utility profiles of correlated equilibria of two-player strategic form games can be implemented by cryptographic cheap-talk between the two parties, if the protocol is required to be empty-threat free.

Implementing a correlated equilibrium using cryptographic cheap-talk means that the parties first get to send messages to each other, and after that they have to simultaneously pick an action in a simultaneous move game.

The parties are modeled as computationally bounded, as to allow them to use cryptography, like secure multiparty computation, in the phase where they send messages to each other, the so-called cheap-talk phase.

Our result can be interpreted as meaning that cryptography not always will allow two parties to play as well as would a real-life trusted mediator. Our result is significant, as it prior to our result was widely believed that cryptography could always be used to by two parties to do as well as they could if they had access to a mediator.

Leakage-resilient signatures with graceful degradation

In this work we address the problem of modeling and designing signature schemes which remain secure even if the might leak some information about the secret key to the attacker. This is an important issue in practice, as various side channels of a physical implementation of a signature scheme might leak information on the secret key.

In the usual theoretical model of this, the adversary gets to submit a function to a leakage oracle, which then applies the function to the secret key and gives the adversary the result. Then the adversary has to break the scheme by constructing a valid signature scheme, a so-called forgery. This way to model the setting prevents us from tolerating leakage which is longer than a signature, even if the secret key is much longer: the adversary can simply leak a signature and then use that signature to "break" the scheme.

We propose the model where to "break" the scheme, the adversary has to produce more than one valid signatures, namely more than the length of his leakage divided by the length of a signature. This model says that if there is a little leakage, it can not have a worse effect than if it had been used to leak a small number of signatures, and the new model is thus meaningful even if the length of the leakage exceeds the length of a signature.

We also propose a signature scheme secure in this new model.

This work is an example of our work on leakage resilience but is also an example of how we pursue the problem of developing new and better security models.

Actively Secure Two-Party Evaluation of Any Quantum Operation

In this work we provide a protocol which allows two parties, to apply any quantum operation on a joint quantum state, where the parties each holds only a part of the state, and where the parties do not want the other party to learn any other information than the intended output. This property is guaranteed to hold even if one of the parties is cheating arbitrarily. Prior to our work it was known how two parties could securely compute any classical function on any classical inputs, even in the presence of cheating, but prior to our work it was a fundamental open problem if the same task was possible in the case of a quantum operation on quantum states.

Continuous Non-malleable Codes

Non-malleable codes are a natural relaxation of error correcting/detecting codes that have useful applications in the context of tamper resilient cryptography and tamper resilient computation.

Informally, a code is non-malleable if an adversary trying to tamper with an encoding of a given message can only leave it unchanged or modify it to the encoding of a completely unrelated value. This is an important tool in constructing tamper resilient computation, i.e., computation which is guaranteed to be correct and secure, even if the adversary can introduce errors into the computation.

This paper introduces an extension of the standard non-malleability security notion – so-called continuous non-malleability – where we allow the adversary to tamper with an encoding many times and observe the effect on the computation in which it is used. This is in contrast to the standard notion of non-malleable codes where the adversary only is allowed to tamper a single time with an encoding.

Tolerating continuous tampering is important for a code to be useful in practice, as it is not reasonable to assume that an adversary who can tamper with the computation once cannot do it twice, so our new model and code is an important step towards bring basic research on tamper resilience into practice.

We also show how to construct continuous non-malleable codes in the common split-state model where an encoding consists of two parts and the tampering can be arbitrary but has to work independently on the parts. This model is interesting as it might be implemented in practice by keeping the two parts on separate computational devices or different and distant parts of the same computational device.

Information for Team Members

Publication Footnote

Team members, please remember to add the footnote on the front page of all relevant publications, and remember to make a green open access version of all relevant publications.

Travels

To book a relevant travel you are required to use the travel booking system of Aarhus University, click here for more information.

You should always make a travel application before buying the travel. The workflow system will then let me approve the travel. When you make the travel application, use Grant holder: Jesper Buus Nielsen, Project name: 901649, Project number: 901649, Activity number: 82420.