2018 Symposium Posters

Primary Investigator:
Aniket Kate

Project Members
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. 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 2/3rd 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 environments.