1;3409;0c Matrix Signatures: From MACs to Digital Signatures in Distributed Systems

Matrix Signatures: From MACs to Digital Signatures in Distributed Systems

Distributed Computing, 22nd International Symposium, DISC 2008, vol. 5218, 2008
Pages: 16-31DOI: 10.1007/978-3-540-87779-0_2

DISC

bibtex

We present the first general implementation to provide the properties of digital signature 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. 1 1