In this work, we translate the high-level vision of the proposed legislation into technical requirements and design a cryptographic protocol that meets them. Roughly speaking, the protocol can be viewed as a decentralized system of locally-managed end-to-end encrypted databases. Our design relies on various cryptographic building blocks including structured encryption, secure multi-party computation and secret sharing. We propose a formal security definition and prove that our design meets it. We implemented our protocol and evaluated its performance empirically at the scale it would have to run if it were deployed in the United States. Our results show that a decentralized and end-to-end encrypted national gun registry is not only possible in theory but feasible in practice.
Category / Keywords: applications / public policy, searchable encryption,secure multi-party computation, secure two-party computation, structured encryption Original Publication (with minor differences): IEEE Symposium on Security and Privacy 2021 Date: received 28 Jan 2021, last revised 29 Jan 2021 Contact author: lucyq at brown edu Available format(s): PDF | BibTeX Citation Note: This version of the publication includes a full proof of security, which is omitted in the conference publication. Version: 20210201:072105 (All versions of this report) Short URL: ia.cr/2021/107