Signature Schemes Secure Against Hard-to-Invert Leakage

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Sebastian Faust, École Polytechnique Fédérale de Lausanne
  • ,
  • Carmit Hazay, Bar Ilan Univ, Bar Ilan University, Fac Engn
  • ,
  • Jesper Buus Nielsen
  • Peter Sebastian Nordholt
  • ,
  • Angela Zottarel

Side-channel attacks allow the adversary to gain partial knowledge of the secret key when cryptographic protocols are implemented in real-world hardware. The goal of leakage resilient cryptography is to design cryptosystems that withstand such attacks. In the auxiliary input model, an adversary is allowed to see a computationally hard-to-invert function of the secret key. The auxiliary input model weakens the bounded leakage assumption commonly made in leakage resilient cryptography as the hard-to-invert function may information-theoretically reveal the entire secret key. In this work, we propose the first constructions of digital signature schemes that are secure in the auxiliary input model. Our main contribution is a digital signature scheme that is secure against chosen message attacks when given any exponentially hard-to-invert function of the secret key. As a second contribution, we construct a signature scheme that achieves security for random messages assuming that the adversary is given a polynomial-time hard-to-invert function (where both the challenge as well as the signatures seen prior to that are computed on random messages). Here, polynomial hardness is required even when given the entire public key. We further show that such signature schemes readily give us auxiliary input secure identification schemes.

Original languageEnglish
JournalJournal of Cryptology
Pages (from-to)422-455
Number of pages34
Publication statusPublished - Apr 2016

    Research areas


See relations at Aarhus University Citationformats

ID: 108371084