Paper 2018/543

Practical and Tightly-Secure Digital Signatures and Authenticated Key Exchange

Kristian Gjøsteen and Tibor Jager

Abstract

Tight security is increasingly gaining importance in real-world cryptography, as it allows to choose cryptographic parameters in a way that is supported by a security proof, without the need to sacrifice efficiency by compensating the security loss of a reduction with larger parameters. However, for many important cryptographic primitives, including digital signatures and authenticated key exchange (AKE), we are still lacking constructions that are suitable for real-world deployment. We construct the first truly practical signature scheme with tight security in a real-world multi-user setting with adaptive corruptions. The scheme is based on a new way of applying the Fiat-Shamir approach to construct tightly-secure signatures from certain identification schemes. Then we use this scheme as a building block to construct the first practical AKE protocol with tight security. It allows the establishment of a key within 1 RTT in a practical client-server setting, provides forward security, is simple and easy to implement, and thus very suitable for practical deployment. It is essentially the ``signed Diffie-Hellman'' protocol, but with an additional message, which is crucial to achieve tight security. This additional message is used to overcome a technical difficulty in constructing tightly-secure AKE protocols. For a theoretically-sound choice of parameters and a moderate number of users and sessions, our protocol has comparable computational efficiency to the simple signed Diffie-Hellman protocol with EC-DSA, while for large-scale settings our protocol has even better computational performance, at moderately increased communication complexity.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2018
Keywords
Tight securitydigital signaturesFiat-Shamir
Contact author(s)
tibor jager @ gmail com
History
2018-06-04: received
Short URL
https://ia.cr/2018/543
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/543,
      author = {Kristian Gjøsteen and Tibor Jager},
      title = {Practical and Tightly-Secure Digital Signatures and Authenticated Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2018/543},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/543}},
      url = {https://eprint.iacr.org/2018/543}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.