VeRSA: Verifiable Registries with Efficient Client Audits from RSA Authenticated Dictionaries

Alice ae7b Bob 422a Cindy 87bd e.g. public key identities software binary checksums domain name routing info Digest d Server Setting: Verifiable registries 4 Key-value Mapping Alice ae7b Bob 422a Cindy 87bd e.g. public key identities software binary checksums domain name routing info Digest Users can lookup values and verify they are consistent with what other users receive. Goal 1 Lo ok up A lic e ae 7b , d, π Ali ce Bob Carol Lookup Alice ae7b, d, π Alice d Server Setting: Verifiable registries 5 Users can monitor key-value mappings to detect unexpected modifications. Key-value Mapping Alice ae7b Bob 422a Cindy 87bd e.g. public key identities software binary checksums domain name routing info Digest Goal 2 d 0 d 1 d 2 New digests published over time d 3 Alice ae7b Bob 422a Cindy 87bd Alice 31cc Bob 422a Cindy 87bd Alice ae7b Bob 422a Cindy 87bd Alice Server Setting: Verifiable registries 6 a e 7 b ae 7b 3 1 c c a e 7 b Users can monitor key-value mappings to detect unexpected modifications. Key-value Mapping Alice ae7b Bob 422a Cindy 87bd Previous approaches: Trusted third-party auditors Key-value Mapping Alice ae7b Bob 422a Cindy 87bd Digest d 0 d 1 d 2 New digests published over time d 3 Trusted third-party auditors verify version-only invariant is preserved between digests. Invariant allows efficient detection of unexpected changes by user.