  The unique properties of blockchain enable central requirements of
distributed secure logging: Immutability, integrity, and availability.
Especially when providing transparency about data usages, a blockchain-based
secure log can be beneficial, as no trusted third party is required. Yet, with
data governed by privacy legislation such as the GDPR or CCPA, the core
advantage of immutability becomes a liability. After a rightful request, an
individual's personal data need to be rectified or deleted, which is impossible
in an immutable blockchain. To solve this issue, we exploit a legal property of
pseudonymized data: They are only regarded personal data if they can be
associated with an individual's identity. We make use of this fact by
presenting P3, a pseudonym provisioning system for secure usage logs including
a protocol for recording new usages. For each new block, a one-time transaction
pseudonym is generated. The pseudonym generation algorithm guarantees
unlinkability and enables proof of ownership. These properties enable
GDPR-compliant use of blockchain, as data subjects can exercise their legal
rights with regards to their personal data. The new-usage protocol ensures
non-repudiation, and therefore accountability and liability. Most importantly,
our approach does not require a trusted third party and is independent of the
utilized blockchain software.
