File(s) not publicly available

Optimal Clock Synchronization with Signatures

conference contribution
posted on 2023-11-29, 18:20 authored by Christoph LenzenChristoph Lenzen, Julian LossJulian Loss
Cryptographic signatures can be used to increase the resilience of distributed systems against adversarial attacks, by increasing the number of faulty parties that can be tolerated. While this is well-studied for consensus, it has been underexplored in the context of fault-tolerant clock synchronization, even in fully connected systems. Here, the honest parties of an n-node system are required to compute output clocks of small skew (i.e., maximum phase offset) despite local clock rates varying between 1 and ϑ>1, end-to-end communication delays varying between d−u and d, and the interference from malicious parties. So far, it is only known that clock pulses of skew d can be generated with (trivially optimal) resilience of ⌈n/2⌉−1 (PODC `19), improving over the tight bound of ⌈n/3⌉−1 holding without signatures for \emph{any} skew bound (STOC `84, PODC `85). Since typically d≫u and ϑ−1≪1, this is far from the lower bound of u+(ϑ−1)d that applies even in the fault-free case (IPL `01). We prove matching upper and lower bounds of Θ(u+(ϑ−1)d) on the skew for the resilience range from ⌈n/3⌉ to ⌈n/2⌉−1. The algorithm showing the upper bound is, under the assumption that the adversary cannot forge signatures, deterministic. The lower bound holds even if clocks are initially perfectly synchronized, message delays between honest nodes are known, ϑ is arbitrarily close to one, and the synchronization algorithm is randomized. This has crucial implications for network designers that seek to leverage signatures for providing more robust time. In contrast to the setting without signatures, they must ensure that an attacker cannot easily bypass the lower bound on the delay on links with a faulty endpoint.


Preferred Citation

Christoph Lenzen and Julian Loss. Optimal Clock Synchronization with Signatures. In: ACM Symposium on Principles of Distributed Computing (PODC). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM Symposium on Principles of Distributed Computing (PODC)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_3688, title = "Optimal Clock Synchronization with Signatures", author = "Lenzen, Christoph and Loss, Julian", booktitle="{ACM Symposium on Principles of Distributed Computing (PODC)}", year="2022", }

Usage metrics


    No categories selected


    Ref. manager