[Resource Topic] 2018/343: Flexible Signatures: Towards Making Authentication Suitable for Real-Time Environments

Welcome to the resource topic for 2018/343

Flexible Signatures: Towards Making Authentication Suitable for Real-Time Environments

Authors: Duc Viet Le, Mahimna Kelkar, Aniket Kate


This work introduces the concept of flexible signatures. In a flexible signature scheme, the verification algorithm quantifies the validity of a signature based on the number of computations performed such that the signature’s validation (or confidence) level in [0,1] improves as the algorithm performs more computations. Importantly, the definition of flexible signatures does not assume the resource restriction to be known in advance until the verification process is hard stopped by a system interrupt. Although prominent traditional signature schemes such as RSA, (EC)DSA, EdDSA seem unfit towards building flexible signatures, we find updated versions of the Lamport-Diffie one-time signature and Merkle authentication tree to be suitable for building flexible signatures. We present a flexible signature construction based on these hash-based primitives and prove its security with a concrete security analysis. We also perform a thorough validity-level analysis demonstrating an attractive computation-vs-validity trade-off offered by our construction: a security level of 80 bits can be ensured by performing only around $\frac{2}{3}$rd of the total hash computations for our flexible signature construction with a Merkle tree of height 20. We see this work as the first step towards realizing flexible-security cryptographic primitives. Beyond flexible signatures, our flexible-security conceptualization offers an interesting opportunity to build similar primitives in the asymmetric as well as symmetric cryptographic domains. Apart from being theoretically interesting, these flexible security primitives can be of particular interest to real-time systems as well as the Internet of things: rigid all-or-nothing guarantees offered by the traditional cryptographic primitives have been particularly unattractive to these unpredictably resource-constrained

ePrint: https://eprint.iacr.org/2018/343

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .