We construct new leakage-resilient signature schemes. Our schemes remain unforgeable against an adversary leaking arbitrary (yet bounded) information on the entire state of the signer (sometimes known as fully leakage resilience), including the random coin tosses of the signing algorithm. The main feature of our constructions is that they offer a graceful degradation of security in situations where standard existential unforgeability is impossible. This property was recently put forward by Nielsen, Venturi, and Zottarel (PKC 2014) to deal with settings in which the secret key is much larger than the size of a signature. One remarkable such case is the so-called Bounded-Retrieval Model (BRM), where one intentionally inflates the size of the secret key while keeping constant the signature size and the computational complexity of the scheme. Our main constructions have leakage rate 1−o(1), and are proven secure in the standard model. We additionally give a construction in the BRM, relying on a random oracle. All of our schemes are described in terms of generic building blocks, but also admit efficient instantiations under fairly standard number-theoretic assumptions. Finally, we explain how to extend some of our schemes to the setting of noisy leakage, where the only restriction on the leakage functions is that the output does not decrease the min-entropy of the secret key by too much.

Fully Leakage-Resilient Signatures Revisited: Graceful Degradation, Noisy Leakage, and Construction in the Bounded-Retrieval Model / Faonio, Antonio; Nielsen, Jesper Buus; Venturi, Daniele. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 2017, 660:(2017), pp. 23-56. [http://dx.doi.org/10.1016/j.tcs.2016.11.016]

Fully Leakage-Resilient Signatures Revisited: Graceful Degradation, Noisy Leakage, and Construction in the Bounded-Retrieval Model

Venturi, Daniele
2017

Abstract

We construct new leakage-resilient signature schemes. Our schemes remain unforgeable against an adversary leaking arbitrary (yet bounded) information on the entire state of the signer (sometimes known as fully leakage resilience), including the random coin tosses of the signing algorithm. The main feature of our constructions is that they offer a graceful degradation of security in situations where standard existential unforgeability is impossible. This property was recently put forward by Nielsen, Venturi, and Zottarel (PKC 2014) to deal with settings in which the secret key is much larger than the size of a signature. One remarkable such case is the so-called Bounded-Retrieval Model (BRM), where one intentionally inflates the size of the secret key while keeping constant the signature size and the computational complexity of the scheme. Our main constructions have leakage rate 1−o(1), and are proven secure in the standard model. We additionally give a construction in the BRM, relying on a random oracle. All of our schemes are described in terms of generic building blocks, but also admit efficient instantiations under fairly standard number-theoretic assumptions. Finally, we explain how to extend some of our schemes to the setting of noisy leakage, where the only restriction on the leakage functions is that the output does not decrease the min-entropy of the secret key by too much.
Faonio, Antonio; Nielsen, Jesper Buus; Venturi, Daniele
Fully Leakage-Resilient Signatures Revisited: Graceful Degradation, Noisy Leakage, and Construction in the Bounded-Retrieval Model / Faonio, Antonio; Nielsen, Jesper Buus; Venturi, Daniele. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 2017, 660:(2017), pp. 23-56. [http://dx.doi.org/10.1016/j.tcs.2016.11.016]
File in questo prodotto:
File Dimensione Formato  
913.pdf

embargo fino al 17/01/2019

Descrizione: Full version
Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 705.71 kB
Formato Adobe PDF
705.71 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11572/160261
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact