TY - JOUR
T1 - Key-homomorphic signatures
T2 - definitions and applications to multiparty signatures and non-interactive zero-knowledge
AU - Derler, David
AU - Slamanig, Daniel
PY - 2019
Y1 - 2019
N2 - Key-homomorphic properties of cryptographic objects, i.e., homomorphisms on their key space, have proven to be useful, both from a theoretical as well as a practical perspective. Important cryptographic objects such as pseudorandom functions or (public key) encryption have been studied previously with respect to key-homomorphisms. Interestingly, however, signature schemes have not been explicitly investigated in this context so far. We close this gap and initiate the study of key-homomorphic signatures, which turns out to be an interesting and versatile concept. In doing so, we firstly propose a definitional framework for key-homomorphic signatures distilling various natural flavours of key-homomorphic properties. Those properties aim to classify existing signature schemes and thus allow to infer general statements about signature schemes from those classes by simply making black-box use of the respective properties. We apply our definitional framework to show elegant and simple compilers from classes of signature schemes admitting different types of key-homomorphisms to a number of other interesting primitives such as ring signature schemes, (universal) designated verifier signature schemes, simulation-sound extractable non-interactive zero-knowledge arguments, and multisignature schemes. Additionally, using the formalisms provided by our framework, we can prove a tight implication from single-user security to key-prefixed multi-user security for a class of schemes admitting a certain key-homomorphism.
AB - Key-homomorphic properties of cryptographic objects, i.e., homomorphisms on their key space, have proven to be useful, both from a theoretical as well as a practical perspective. Important cryptographic objects such as pseudorandom functions or (public key) encryption have been studied previously with respect to key-homomorphisms. Interestingly, however, signature schemes have not been explicitly investigated in this context so far. We close this gap and initiate the study of key-homomorphic signatures, which turns out to be an interesting and versatile concept. In doing so, we firstly propose a definitional framework for key-homomorphic signatures distilling various natural flavours of key-homomorphic properties. Those properties aim to classify existing signature schemes and thus allow to infer general statements about signature schemes from those classes by simply making black-box use of the respective properties. We apply our definitional framework to show elegant and simple compilers from classes of signature schemes admitting different types of key-homomorphisms to a number of other interesting primitives such as ring signature schemes, (universal) designated verifier signature schemes, simulation-sound extractable non-interactive zero-knowledge arguments, and multisignature schemes. Additionally, using the formalisms provided by our framework, we can prove a tight implication from single-user security to key-prefixed multi-user security for a class of schemes admitting a certain key-homomorphism.
KW - (Universal) designated verifier signatures
KW - Key-homomorphic signatures
KW - Multi-user signatures
KW - Multisignatures
KW - Ring signatures
KW - Simulation-sound extractable non-interactive zero-knowledge
UR - http://www.scopus.com/inward/record.url?scp=85052526408&partnerID=8YFLogxK
U2 - 10.1007/s10623-018-0535-9
DO - 10.1007/s10623-018-0535-9
M3 - Article
AN - SCOPUS:85052526408
SN - 0925-1022
VL - 87
SP - 1373
EP - 1413
JO - Designs, Codes and Cryptography
JF - Designs, Codes and Cryptography
IS - 6
ER -