Auditing without Leaks Despite Curiosity Conference: ACM Symposium on Principles of Distributed Computing; June 16–20, 2025; Huatulco, Mexico ACM Symposium on Principles of Distributed Computing (PODC ’25), June 16–20, 2025, Huatulco, Mexico DOI: 10.1145/3732772.3733516 ISBN: 979-8-4007-1885-4/25/06

Hagit Attiya, Antonio Fernández Anta, Alessia Milani, Alexandre Rapetti, Corentin Travers · 2025

Read Auditing without Leaks Despite Curiosity Conference: ACM Symposium on Principles of Distributed Computing; June 16–20, 2025; Huatulco, Mexico ACM Symposium on Principles of Distributed Computing (PODC ’25), June 16–20, 2025, Huatulco, Mexico DOI: 10.1145/3732772.3733516 ISBN: 979-8-4007-1885-4/25/06 by Hagit Attiya, Antonio Fernández Anta, Alessia Milani, Alexandre Rapetti, Corentin Travers (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00665.txt.

Introduction

Hagit Attiya and co-authors tackle private auditing of shared data in a 2025 distributed computing paper. Auditing records who accessed sensitive information, but a curious reader might learn values without reading them openly, or spy on other readers' accesses, and older definitions missed those leaks.

The authors refine the definition of auditability around the moment a read becomes effective, not when it returns. They then give a wait-free design for a shared register with many writers and readers that logs effective reads at once with the access itself. A one-time pad scheme hides the log from the readers it tracks.

Catalog record

CREATORHagit Attiya, Antonio Fernández Anta, Alessia Milani, Alexandre Rapetti, Corentin Travers
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-00665

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Auditing without Leaks Despite Curiosity Conference: ACM Symposium on Principles of Distributed Computing; June 16–20, 2025; Huatulco, Mexico ACM Symposium on Principles of Distributed Computing (PODC ’25), June 16–20, 2025, Huatulco, Mexico DOI: 10.1145/3732772.3733516 ISBN: 979-8-4007-1885-4/25/06 CCS: Theory of computation Distributed algorithms Hagit Attiya, Antonio Fernández Anta, Alessia Milani, Alexandre Rapetti, Corentin Travers Abstract . Auditing data accesses helps preserve privacy and ensures accountability by allowing one to determine who accessed (potentially sensitive) information. A prior formal definition of register auditability was based on the values returned by read operations, without accounting for cases where a reader might learn a value without explicitly reading it or gain knowledge of data access without being an auditor . This paper introduces a refined definition of auditability that focuses on when a read operation is effective , rather than relying on its completion and return of a value. Furthermore, we formally specify the constraints that prevent readers from learning values they did not explicitly read or from auditing other readers’ accesses. Our primary algorithmic contribution is a wait-free implementation of a multi-writer, multi-reader register that tracks effective reads while preventing unauthorized audits. The key challenge is ensuring that a read is auditable as soon as it becomes effective, which we achieve by combining value access and access logging into a single atomic operation. Another challenge is recording accesses without exposing them to readers, which we address using a simple encryption technique (one-time pad). We extend this implementation to an auditable max register that tracks the largest value ever written. The implementation deals with the additional challenge posed by the max register semantics, which allows readers to learn prior values without reading them. The max register, in turn, serves as the foundation for implementing an auditable snapshot object and, more generally, versioned types . These extensions maintain the strengthened notion of auditability, appropriately adapted from multi-writer, multi-reader registers. 1. Introduction Auditing is a powerful tool for determining who had access to which (potentially sensitive) information. Auditability is crucial for preserving data privacy, as it ensures accountability for data access. This is particularly important in shared, remotely accessed storage systems, where understanding the extent of a data breach can help mitigate its impact. 1.1. Auditable Read/Write Registers Auditability was introduced by Cogo and Bessani ( Cogo and Bessani 2021 ) in the context of replicated read/write registers . An auditable register extends traditional read and write operations with an additional audit operation that reports which register values have been read and by whom. The auditability definition by Cogo and Bessani is tightly coupled with their multi-writer, multi-reader register emulation in a replicated storage system using an information-dispersal scheme. An implementation-agnostic auditability definition was later proposed ( Attiya et al. 2023 ) , based on collectively linearizing read, write, and audit operations. This work also analyzes the consensus number required for implementing auditable single-writer registers, showing that it scales with the number of readers and auditors. However, this definition assumes that a reader only gains access to values that are explicitly returned by its read operations. This assumption does not account for situations where a reader learns the register’s value before it has officially returned, making the read operation effective . Hence, a notable limitation of this definition is that a process with an effective read can refuse to complete the operation, thereby avoiding detection by the audit mechanism. Prior work has also overlooked the risk of non-auditors learning values without explicitly reading them or inferring accesses of other processes. Even when processes follow their prescribed algorithms without active misbehavior, existing auditable register implementations allow an “honest but curious” process to learn more than what its read operations officially return. Additionally, extending auditability beyond read/write registers remained an unexplored territory. 1.2. Our Contributions and Techniques In this work, we propose a stronger form of auditability for read/write registers, ensuring that all effective reads are auditable and that non-auditors cannot infer the values read by other processes. We further extend these properties to other data structures and propose new algorithms that fulfill these guarantees. We define new properties that ensure operations do not leak information when processes are honest-but-curious ( Goldreich 2003 ) (see Section 2 ). Firstly, we introduce an implementation-agnostic definition of an effective operation , which is applicable, for instance, to read operations in an auditable register. An operation is effective if a process has determined its return value in all executions indistinguishable to it. Secondly, we define uncompromised operations , saying, for example, that in a register, readers do not learn which values were read by other readers or gain information about values they do not read. This definition is extended beyond registers. For arbitrary data objects, we specify that an operation is uncompromised if there is an indistinguishable execution where the operation does not occur. Enforcing uncompromised operations in auditable objects poses a challenge since it is, in a sense, antithetical to securely logging data accesses. Our primary algorithmic contribution (Section 3 ) is a wait-free, linearizable implementation of an auditable multi-writer, multi-reader register. Our implementation ensures that all effective reads are auditable while preventing information leaks: reads are uncompromised by other readers, and cannot learn previous values — unless they actually read them. As a consequence, the implementation is immune to a honest-but-curious attacker. To achieve these properties, our algorithm carefully combines value access with access logging. Additionally, access logs are encrypted using one-time pads known only to writers and auditors. The subtle synchronization required in our implementation is achieved by using \mathsf{compare\&swap} and \mathsf{fetch\&xor} (in addition to ordinary reads and writes). Such strong synchronization primitives are necessary since even simple single-writer auditable registers can solve consensus ( Attiya et al. 2023 ) . The correctness proof of the algorithm, of basic linearizability properties as well as of advanced auditability properties, is intricate and relies on a careful linearization function. Our second algorithmic contribution is an elegant extension of the register implementation to other commonly-used objects. We first extend our framework to a wait-free, linearizable implementation of an auditable multi-writer, multi-reader max register ( Aspnes et al. 2012 ) , which returns the largest value ever written. The semantics of a max register, together with tracking the number of operations applied to it (needed for logging accesses), may leak information to the reader about values it has not effectively read. We avoid this leakage by adding a random nonce , serving to introduce some noisiness, to the values written. (See Section 4 .) As before, all effective reads are auditable, and no additional information is leaked. In Section 5 , we demonstrate how an auditable max register enables auditability in other data structures. Specifically, we implement auditable extension of atomic snapshots ( Afek et al. 1993 ) and more generally, of versioned types ( Denysyuk and Woelfel 2015 ) . Many useful objects, such as counters and logical clocks, are naturally versioned or can be made so with minimal modification. 1.3. Related Work Cogo and Bessani ( Cogo and Bessani 2021 ) present an algorithm to implement an auditable regular register, using n\geq 4f+1 atomic read/write shared objects, f of which may fail by crashing. Their high-level register implementation relies on

Read the complete text