Byzantine-Tolerant Privacy-Preserving Atomic Register
Vincent Kowalski, Achour Mostéfaoui, Matthieu Perrin, Sinchan Sengupta · Theoretical Computer Science · 2025
This paper extends and improves upon our work [Kowalski et al., ICDCN 2025], which proposed the construction of a privacy-preserving single-writer multi-reader (SWMR) atomic register in a Byzantine-prone distributed model. Specifically, we consider a closed model in which one process can write values in the register and only a subset of the other processes are allowed to read them. The goal is to ensure that processes without the requisite read permission are unable to read the content of the register, even when they are Byzantine. This guarantees the privacy of the stored value. We achieve this privacy by encoding the value written by the writer using secret sharing, thereby splitting it into multiple shards that are disseminated among the participating reader processes. The technical challenge is then to coordinate the correct reader processes so as to achieve Byzantine linearizability without revealing the register’s contents. The main contribution of this work is an improved resilience bound of the linearizable read-write (R/W) privacy-preserving register construction from t < n 7 to t < n 5 , where t is the number of Byzantine processes and n denotes the total number of processes in the system. Despite being more resilient than the previous version, the new construction algorithm is significantly simpler and more appealing, and it comes with a clearer and more concise correctness proof.