Abstract
Multi-verifier signatures generalize public-key signatures to a secret-key setting. Just like public-key signatures, these signatures are both transferable and secure under arbitrary (unbounded) adaptive chosen-message attacks. In contrast to public-key signature schemes, however, we exhibit practical constructions of multi-verifier signature schemes that are provably secure and are based only on pseudorandom functions in the plain model without any random oracles.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A.S. Aiyer, L. Alvisi, R.A. Bazzi, A. Clement, Matrix signatures: From MACs to digital signatures in distributed systems, in Proc. 22nd International Symposium on Distributed Computing. Lecture Notes in Computer Science, vol. 5218 (Springer, Berlin, 2008), pp. 16–31
M. Bellare, J. Kilian, P. Rogaway, The security of cipher block chaining, in Advances in Cryptology—CRYPTO’94, Proc. 14th Annual International Cryptology Conference, ed. by Y. Desmedt. Lecture Notes in Computer Science, vol. 839 (Springer, Berlin, 1994), pp. 341–358
M. Bellare, O. Goldreich, A. Mityagin, The power of verification queries in message authentication and authenticated encryption. Cryptology ePrint Archive, 2004. Report 2004/309, 2004
D. Boneh, G. Durfee, M. Franklin, Lower bounds for multicast message authentication, in Advances in Cryptology—Eurocrypt’01, Proc. International Conference on the Theory and Applications of Cryptographic Techniques, ed. by B. Pfitzmann. Lecture Notes in Computer Science, vol. 2045 (Springer, Berlin, 2001), pp. 437–452
D. Boneh, B. Lynn, H. Shacham, Short signatures from the Weil pairing. J. Cryptol. 17(4), 297–319 (2004)
R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, B. Pinkas. Multicast security: A taxonomy and some efficient constructions, in IEEE INFOCOM’99. Proc. 18th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2 (IEEE Computer Society, Los Alamitos, 1999), pp. 706–716
M. Castro, B. Liskov, Practical Byzantine fault tolerance, in Proc. 3rd Symposium on Operating Systems Design and Implementation, Berkeley, CA, February 1999. USENIX Association, Co-sponsored by IEEE TOCS and ACM SIGOPS, pp. 173–186
L.S. Charlap, H.D. Rees, D.P. Robbins, The asymptotic probability that a random biased matrix is invertible. Discrete Math. 82(2), 153–163 (1990)
D. Chaum, S. Roijakkers, Unconditionally secure digital signatures, in Advances in Cryptology—CRYPTO’90, Proc. 10th Annual Cryptology Conference, ed. by A. Menezes, S.A. Vanstone. Lecture Notes in Computer Science, vol. 537 (Springer, Berlin, 1990), pp. 206–214
R. Cramer, V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, in Advances in Cryptology—CRYPTO’98, Proc. 18th Annual International Cryptology Conference, ed. by H. Krawczyk. Lecture Notes in Computer Science, vol. 1462 (Springer, Berlin, 1998), pp. 13–25
Y. Desmedt, Y. Frankel, M. Yung. Multi-receiver/multi-sender network security: efficient authenticated multicast/feedback, in IEEE INFOCOM’92: Proc. 11th Annual Joint Conference of the IEEE Computer and Communications Societies on One World through Communications (IEEE Computer Society, Los Alamitos, 1992), pp. 2045–2054
W. Diffie, M.E. Hellman, New directions in cryptography. IEEE Trans. Inf. Theory IT-22(6), 644–654 (1976)
D. Dolev, The Byzantine Generals strike again. J. Algorithms 3(1), 14–30 (1982)
R. Fagin, J.Y. Halpern, Y. Moses, M.Y. Vardi, Reasoning about Knowledge (MIT Press, Cambridge, 2003)
U. Feige, A. Shamir, Witness indistinguishable and witness hiding protocols, in STOC’90: Proc. 22nd Annual ACM Symposium on Theory of Computing, ed. by H. Ortiz (ACM, New York, 1990), pp. 416–426
O. Goldreich, Foundations of Cryptography, vol. I (Cambridge University Press, Cambridge, 2001)
S. Goldwasser, S. Micali, R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)
G. Hanaoka, J. Shikata, Y. Zheng, H. Imai, Unconditionally secure digital signature schemes admitting transferability, in Advances in Cryptology—Asiacrypt’00, Proc. 6th International Conference on the Theory and Application of Cryptology and Information Security, ed. by T. Okamoto. Lecture Notes in Computer Science, vol. 1976 (Springer, Berlin, 2000), pp. 130–142
T. Johansson, Further results on asymmetric authentication schemes. Inf. Comput. 151(1–2), 100–133 (1999)
L. Lamport, Personal communication
M. Marsh, F.B. Schneider, CODEX: A robust and secure secret distribution system. IEEE Trans. Dependable Secure Comput. 1(1), 34–47 (2004)
M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in STOC’89: Proc. 21st Annual ACM Symposium on Theory of Computing (ACM, New York, 1989), pp. 33–43
OpenSSL Project, Available at http://www.openssl.org
B. Pfitzmann, M. Waidner, Unconditional Byzantine agreement for any number of faulty processors, in Proc. 9th Annual Symposium on Theoretical Aspects of Computer Science, ed. by A. Finkel, M. Jantzen. Lecture Notes in Computer Science, vol. 577 (Springer, Berlin, 1992), pp. 339–350
R.L. Rivest, A. Shamir, L. Adelman, A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
J. Rompel, One-way functions are necessary and sufficient for secure signatures, in STOC’90: Proc. 22nd Annual ACM Symposium on Theory of Computing (ACM, New York, 1990), pp. 387–394.
R. Safavi-Naini, L. McAven, M. Yung, General group authentication codes and their relation to “Unconditionally-secure signatures”, in Public Key Cryptography—PKC 2004, Proc. 7th International Workshop on Theory and Practice in Public Key Cryptography, ed. by F. Bao, R.H. Deng, J. Zhou. Lecture Notes in Computer Science, vol. 2947 (Springer, Berlin, 2004), pp. 231–247
FIPS 180-1. Secure Hash Standard. Federal Information Processing Standard (FIPS), Publication 180-1, National Institute of Standards and Technology, US Department of Commerce, Washington, DC, April 1995
J. Shikata, G. Hanaoka, Y. Zheng, H. Imai, Security notions for unconditionally secure signature schemes, in Advances in Cryptology—Eurocrypt’02, Proc. 21st International Conference on the Theory and Applications of Cryptographic Techniques, ed. by L.R. Knudsen. Lecture Notes in Computer Science, vol. 2332 (Springer, Berlin, 2002), pp. 434–449
L. Zhou, F.B. Schneider, R. van Renesse, COCA: A secure distributed online certification authority. ACM T. Comput. Syst. 20(4), 329–368 (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Ran Canetti
Research supported in part by AFOSR grant F9550-06-0019, National Science Foundation Grants 0430161 and CCF-0424422 (TRUST), and Microsoft Corporation.
Work for this paper from T. Roeder performed in part while at Cornell University.
Rights and permissions
About this article
Cite this article
Roeder, T., Pass, R. & Schneider, F.B. Multi-Verifier Signatures. J Cryptol 25, 310–348 (2012). https://doi.org/10.1007/s00145-010-9096-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-010-9096-4