Abstract
Intentional or unintentional leakage of confidential data is undoubtedly one of the most severe security threats that organizations face in the digital era. The threat now extends to our personal lives: a plethora of personal information is available to social networks and smartphone providers and is indirectly transferred to untrustworthy third party and fourth party applications. In this work, we present a generic data lineage framework LIME for data flow across multiple entities that take two characteristic, principal roles (i.e., owner and consumer). We define the exact security guarantees required by such a data lineage mechanism toward identification of a guilty entity, and identify the simplifying non repudiation and honesty assumptions. We then develop and analyze a novel accountable data transfer protocol between two entities within a malicious environment by building upon oblivious transfer, robust watermarking, and signature primitives. Finally, we perform an experimental evaluation to demonstrate the practicality of our protocol.
Introduction
In the digital age, data leakage represents a massive liability for both corporations and individuals. Once sensitive data is shared with a third party, the original owner loses control. If that data later appears publicly, proving the source of the leak is difficult, especially in multi-step outsourcing chains. Existing solutions like simple watermarking suffer from the framing problem: a malicious sender could embed a receiver's ID into a document, leak it themselves, and blame the receiver. Conversely, a receiver might deny receiving the specific version that was leaked. LIME (Lineage in the Malicious Environment) addresses these challenges by providing "accountability by design."
The LIME Framework
LIME defines three primary roles: the Owner (data source), the Consumer (data user), and the Auditor (neutral party for identification). The framework manages data flow and lineage across these entities while accounting for varying trust assumptions.
The model is flexible: while mutual trust might suffice between two government agencies, the framework provides a robust protocol for untrusted "Consumers" (e.g., third-party contractors) where malicious behavior is a concern.
Accountable Data Transfer Protocol
The core of LIME is a novel transfer protocol that combines robust watermarking, 1-out-of-2 Oblivious Transfer (OT), and digital signatures. To prevent framing, the sender divides a document into $n$ parts, creating two versions of each part with different watermarks (representing '0' or '1'). The receiver uses OT to select one version of each part.
Because of the OT mechanism, the sender remains "blind" to the specific bitstring (fingerprint) the receiver possesses. If the data is leaked, the auditor extracts this bitstring. Since the sender could not have known the specific pattern chosen by the receiver, they cannot fabricate it to frame them.
Experimental Evaluation
The authors evaluated LIME using image files as a proof-of-concept. Testing images from 256 × 256 pixels (65KB) to 2048 × 2048 pixels (4.1MB) using the Cox spread-spectrum watermarking algorithm, they found:
- Security: The probability of framing is $1/2^n$. With $n=256$, this is cryptographically negligible.
- Performance: For a 512 × 512 image split into 256 parts, total computation (watermarking, signatures, OT, and encryption) took approximately 5–8 seconds on 2014-era hardware.
- Scalability: Computation time scales linearly with the number of document parts and total pixel count.
Limitations and Future Work
While effective for multimedia, LIME faces challenges with "derived" data (e.g., leaking an average of numerical values) where watermarks may be lost. It is also dependent on the robustness of the underlying watermarking scheme. Future work may address "fair exchange" guarantees and broader data types beyond images.
Summary updated