Cryptology ePrint Archive: Report 2013/326

Key-Versatile Signatures and Applications: RKA, KDM and Joint Enc/Sig

Mihir Bellare and Sarah Meiklejohn and Susan Thomson

Abstract: Given an *arbitrary* one-way function F, is it possible to design a signature scheme where the secret key is an input x to F and the public key is y = F(x)? We show that signatures that are "key-versatile" in this sense, while also meeting stronger-than-usual security conditions we define, enable us to add signature-based integrity that is "for-free" in terms of key material, meaning we can sign with keys already in use for another purpose without impacting the security of the original purpose or in turn being impacted by it. We show applications across diverse areas including (1) security against related-key attack (RKA) (2) security for key-dependent messages (KDM), and (3) joint encryption and signing. We show how to build key-versatile signature schemes and then obtain new results in all these application domains in a modular way.

Category / Keywords: foundations / Signatures, Related-Key attack, Tampering, Key-Dependent Messages, NIZKs

Date: received 27 May 2013, last revised 10 Jun 2013

Contact author: mihir at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20130610:125325 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]