  Recent data protection regulations (such as GDPR and CCPA) grant consumers
various rights, including the right to access, modify or delete any personal
information collected about them (and retained) by a service provider. To
exercise these rights, one must submit a verifiable consumer request proving
that the collected data indeed pertains to them. This action is straightforward
for consumers with active accounts with a service provider at the time of data
collection, since they can use standard (e.g., password-based) means of
authentication to validate their requests. However, a major conundrum arises
from the need to support consumers without accounts to exercise their rights.
To this end, some service providers began requiring such accountless consumers
to reveal and prove their identities (e.g., using government-issued documents,
utility bills, or credit card numbers) as part of issuing a verifiable consumer
request. While understandable as a short-term cure, this approach is cumbersome
and expensive for service providers as well as privacy-invasive for consumers.
Consequently, there is a strong need to provide better means of authenticating
requests from accountless consumers. To achieve this, we propose VICEROY, a
privacy-preserving and scalable framework for producing proofs of data
ownership, which form a basis for verifiable consumer requests. Building upon
existing web techniques and features, VICEROY allows accountless consumers to
interact with service providers, and later prove that they are the same person
in a privacy-preserving manner, while requiring minimal changes for both
parties. We design and implement VICEROY with emphasis on security/privacy,
deployability and usability. We also thoroughly assess its practicality via
extensive experiments.
