The Edge of Privacy
-------------------
Stanislaw Jarecki (University of California, Irvine)
Patrick Lincoln (SRI International)
Vitaly Shmatikov (SRI International)

We propose a novel approach for privacy-preserving data mining and 
escrow that balances the citizens' desire for privacy and the need of 
government agencies to collect accurate information about financial, 
commercial and other transactions, and quickly identify certain patterns 
of activities.  Our transaction escrow technology will ensure selective, 
privacy-preserving disclosure by cryptographically protecting all data 
unless it matches a certain pattern or is subpoenaed by a court warrant. 
By default, individual records remain completely anonymous to the escrow 
agency.  As soon as the disclosure pattern is matched, all relevant 
escrows are automatically opened and revealed in the clear to the agency 
in charge of the escrow database.  Also, if a particular individual is 
subpoenaed, all of his or her records can be efficiently identified and 
presented for disclosure. 
 
Neither selective disclosure, nor efficient subpoena can be implemented 
using conventional public-key escrow mechanisms.  Moreover, traditional 
escrow schemes for protecting keys, identities, and data assume that 
the escrow agency is trusted not to perform unauthorized searches on the 
data, leak the keys to third parties, and so on.  Because of this, they 
are vulnerable to the insider threat: a malicious or careless employee 
can exploit or disclose citizens' personal data without authorization. 
By contrast, our proposed transaction escrow scheme is provably secure 
against potential misbehavior by the escrow agency's employees. 
 
The key innovation underlying our technology is "verifiable transaction
escrow."  We propose to equip existing commercial and governmental
databases and other information processing centers with transaction
escrowing capabilities.  Transaction participants will encrypt the data
themselves, but correctness of the escrows will be verified, in a
privacy-preserving way, using efficient variations on zero-knowledge
cryptography.  This will guarantee that the escrow agent can de-anonymize
the entries and remove the encryption *if and only if* the data match a
certain pattern or one of the transaction participants has been
subpoenaed.  For example, a national security agency may collect encrypted
passenger itineraries from commercial airlines and require automatic
disclosure for the records of any passenger who traveled to the Middle
East 5 times or more within a year.  In another application, a financial
regulator may require automatic disclosure of all transfers to a
particular group of accounts as soon as the total amount of these
transfers exceeds $10,000 - even if the transfers are performed using
different banks and wire services!  The transfers not matching this
pattern will remain completely anonymous and undecipherable even while
stored in government-controlled databases, thus alleviating concerns of
privacy advocates.  Until the creator of the escrows is subpoenaed, it is
provably infeasible even to determine whether two entries refer to the
same individual or not.
 
The most important advantages of our approach to transaction escrow are i)
selective disclosure for transaction records that match certain patterns,
and ii) complete anonymity and privacy for all other records without
asking the escrow agency to trust the subjects of monitoring or vice
versa, and without involving a trusted intermediary in every transaction,
and iii) practical efficiency.  Our approach also obviates the need for
independent auditing of database access.  We provide strong cryptographic
guarantees that it is simply impossible to access the database in any
manner other than that explicitly permitted by the selective disclosure
policy.
 
The fruits of successful completion of this research could enable 
deployment of the data collection infrastructure for law enforcement and 
national security tasks, while addressing privacy concerns and complying 
with the relevant privacy legislation.  We also envision that personal 
data escrow with selective disclosure will find applications in many other 
areas such as health care monitoring, disease control and prevention, 
financial regulation, etc.  For example, government centers for disease 
control have a need to identify dangerous new epidemics as rapidly 
as possible, but staffers in that organization must not have complete 
access to specific patient records at their whim.  Another application 
is secure audit: our transaction escrow scheme can assure integrity and 
privacy of audit logs containing information about individuals' behavior 
in the system, while keeping them available as unforgeable evidence for 
future investigations. 
 
The bottom line goal of this project is to provide a cryptographically 
protected balance between citizens' privacy and the requirements of 
authorities to collect certain well-defined information.  In health 
reporting, law enforcement, anti-terror, secure audit, and other 
applications, if honest users were actually assured of the privacy of 
their data, there would be higher levels of compliance and less need 
for privacy-by-obscurity.