Matrix signatures: From MACs to digital signatures in distributed systems

Amitanand S. Aiyer, Lorenzo Alvisi, Rida Bazzi, Allen Clement

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


We present a general implementation for providing the properties of digital signatures using MACs in a system consisting of any number of untrusted clients and n servers, up to f of which are Byzantine. At the heart of the implementation is a novel matrix signature that captures the collective knowledge of the servers about the authenticity of a message. Matrix signatures can be generated or verified by the servers in response to client requests and they can be transmitted and exchanged between clients independently of the servers. The implementation requires that no more than one third of the servers be faulty, which we show to be optimal. The implementation places no synchrony requirements on the communication and only require fair channels between clients and servers.

Original languageEnglish (US)
Title of host publicationDistributed Computing - 22nd International Symposium, DISC 2008, Proceedings
Number of pages16
StatePublished - 2008
Event22nd International Symposium on Distributed Computing, DISC 2008 - Arcachon, France
Duration: Sep 22 2008Sep 24 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5218 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other22nd International Symposium on Distributed Computing, DISC 2008

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Matrix signatures: From MACs to digital signatures in distributed systems'. Together they form a unique fingerprint.

Cite this