Poster Presentations by Students and Postdocs PORTIA Project Site Visit Stanford CA, May 12-13, 2005 http://crypto.stanford.edu/portia/ Paper: “Secure Computation of the k-th ranked element” (Eurocrypt 2004) PORTIA PI: Rajeev Motwani Institution: Stanford University Authors: Gagan Aggarwal, Nina Mishra, Benny Pinkas Research Objectives: Different organizations with related datasets want to compute the median (or the k-th largest element) of the union of these datasets. We ask how they can do so without revealing anything about the datasets except what the median itself reveals. Significant Results: k = rank of the element to be computed D = size of the domain Protocol overhead: Approach: We adopt the security framework of secure multiparty computation. Any function (including the median) can be computed with polynomial overhead, using protocols developed by Yao and others. However, these generic protocols are not efficient for large datasets. We develop protocols for computing the median that have polylogarithmic overhead. Broader Impact: • Make system developers aware of multi-party protocols to compute functions securely. • Build an efficient toolkit of privacy-preserving protocols for distributed applications. Two-party case: O( log k log D ) t-party case: O( t (log D)2 ) Earlier work: O( min {k log D, D} ) Graphic: 1. 2. 3. 4. 5. What is the median of our datasets? … … … … … 1. 2. 3. 4. 5. The median is 4254.34. … … … … … Paper: “Enterprise privacy promises and enforcement” (WITS 2005) PORTIA PI: John C. Mitchell Institution: Stanford University Authors: Adam Barth, John C. Mitchell Research Objectives: Allow an enterprise to determine whether its detailed internal privacy policy meets its published privacy promises. Provide an algorithm for summarizing complex privacy policies as simple privacy promises. Approach: We propose a data-centric, unified model for the semantics of several formal languages for privacy policies (including P3P and EPAL) and equip the model with a modal logic for reasoning about permission inheritance across data hierarchies. Policies are represented by Kripke structures, and queries are represented by modal formulae. The modalities reflect the differing perspectives of consumers and service providers. Policies are related by comparing the modal theory of their models. Broader Impact: • Promulgate an end-to-end approach to the study of privacy guarantees of complex systems. • Improve understanding of the semantics of privacy policy languages, including the impact of differing perspectives on privacy. Significant Results: • APPEL and XPref can express unsafe preferences, such as “Block providers who do not telemarket,” which are not respected by the system as a whole. • A P3P policy enforces its compact representation, allowing precise interpretation of compact policies. • We give an algorithm for summarizing policies (e.g., translating an EPAL policy into a P3P policy). Graphic: Paper: “Vision Paper: Enabling Privacy for the Paranoids” (VLDB 2004) PORTIA PI: H. Garcia-Molina, R. Motwani Institution: Stanford University Authors: Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, et al. Research Objectives: P3P and Hippocratic databases assume that organizations will implement privacy safeguards for individuals’ information. Recent, well publicized breaches have led people to mistrust organizations’ use of these mechanisms. We seek solutions that restore control to individuals. Significant Results: Approach: Graphic: We propose that individuals release information to organizations in such a way that the released information is unusable for illegitimate tasks. We provide a small set of “information types” and a set of mechanisms to retain control. Our overall framework of types and mechanisms is called P4P: Paranoid Platform for Privacy Preferences. • Present information types as points in a 3D space: (ownership, type, level of control). • Present the TRIM (Traceability, Revocability, Isolation, Minimality) interaction model to enable individual control in information exchanges. P4P[c] complements traditional security methods[a,b] Broader Impact: • Demonstrate that an individual can retain control over his or her information even after its release to an organization. • Initiate a radical re-think of modeling, release, and management of personal information. P4P: Example [A] Example [B] Paper: “Privacy-Preserving Indexing of Documents on the Network” (VLDB 2003) PORTIA PI: Hector Garcia-Molina Institution: Stanford University Authors: Mayank Bawa, Roberto J. Bayardo Jr., Rakesh Agrawal Research Objectives: Individuals want to share content selectively but lack mechanisms to do so. We address the problem of privacy-preserving search over distributed access-controlled content. Approach: We propose to use a centralized privacy-preserving index (PPI) in conjunction with a distributed accesscontrol-enforcing protocol. The new index provides strong and quantifiable privacy guarantees that hold even if the entire index is made public. The degree of privacy provided by the index is tunable, and search overhead is proportional to degree of privacy. Broader Impact: • Raise public awareness of and research interest in search tools for access-controlled content. • Build privacy tools that give each provider complete control over how much information is shared, when it is shared, and with whom it is shared. Significant Results: • Define a centralized inverted-index data structure (the PPI) that guarantees Probable Innocence (in the Reiter-Rubin sense). • Provide an efficient randomized algorithm that builds the PPI and guarantees Possible Innocence during construction. Graphic: P2 Group Z P4 P1 Group F P6 P3 PPI Group A P9 Group F Q Paper: “A network security game and sum of squares partition” PORTIA PI: Ravi Kannan Institution: Yale University Authors: Jim Aspnes, Kevin Chang, Aleksandr Yampolskiy Research Objectives: The overall security of a network is very much dependent on the choices made by individual users. We ask whether the system is adversely affected if users act selfishly. Approach: We model network security as a graph in which the nodes (users) choose whether or not to install antivirus software (their strategies). The ability of a virus to spread through the network is determined by user strategies and the network topology. We define notions of cost to each user and cost to the entire network. We study the game-theoretic properties of the system if user strategies are chosen to be in a Nash Equilibrium and give algorithms to find nearoptimum strategies in terms of cost to the network. (SODA 2005) Significant Results: • A Nash Equilibrium can be much costlier than the optimum strategy; in the worst case, Nash costs a factor Θ(n) more than optimum. • It is NP-Hard to compute an optimum strategy, as well as the pure Nash Equilibria with highest and lowest costs. • There is an O(log2 n) approximation algorithm for finding optimum strategies. It solves a new graphpartitioning problem -- the sum of squares partition -by recursively removing sparse cuts. Graphic: 0 1 2 3 Broader Impact: • Raise awareness in the security community of game-theoretic methods and their limitations. • Provide algorithmic techniques to combat virus propagation. 4 5 Paper: “Database Engines for Bioscience” PORTIA PI: Avi Silberschatz Institution: Yale University Authors: J. Corwin, A. Silberschatz, S. Yadlapalli Research Objectives: Biomedical and Bioinformatics applications have new requirements for persistent data storage. Our work focuses on developing new algorithms and tools to better support these applications. Approach: In collaboration with Yale University's neuroinformatics research group, we have observed that bioscience data have characteristics that complicate their storage in and retrieval from a conventional database system, e.g., heterogeneous, sparse data and frequently modified database schema. We introduce dynamic tables, sparse attributes, and row-level security, and we are working to implement these features in a conventional relational-database engine. Broader Impact: • Develop tools capable of working with data not traditionally suited for relational databases. • Improve the productivity of researchers working with bioinformatics data. Significant Results: We have created an extension to PostgreSQL, a modern, open-source database engine. Our system supports: • New storage mechanisms for heterogeneous data and frequently modified schema • New syntax to access these features through SQL Graphic: Paper: “Compositional Analysis of Contract Signing Protocols” (CSFW 2005) PORTIA PI: John C. Mitchell Institution: Stanford University Authors: M. Backes, A.Datta, A. Derek, J. C. Mitchell, M. Turuani Research Objectives: Contract-signing protocols allow two or more users to exchange signatures fairly, so that no party receives a contract unless all do. In this work, we seek a systematic method for proving correctness of such protocols. Approach: We develop a method for reasoning about contractsigning protocols using a specialized protocol logic. Our proof method is compositional: Security properties (like fairness) are proved for each protocol by combining independent proofs of its three subprotocols. Proofs are carried out in a “template” form, yielding reusable proofs that may be instantiated for a number of different protocols. Game-theoretic properties are proved by demonstrating that the specific strategies achieve their desired outcomes. Broader Impact: • Develop compositional techniques for reasoning about security and privacy. • Develop provably secure protocols for exchanging privacy-related contracts over the Internet. Significant Results: General contract-signing protocol template • Properties addressed are fairness, abuse-freeness, and trusted third-party accountability. • Instantiates to protocols of: Asokan-Shoup-Waidner, Garay-Jacobson-MacKenzie, Markowitch-Kremer, Markowitch-Sacednia, Zhou-Deng-Bao. Graphic: Paper: “On-line Negative Databases” (ICARIS 2004)* PORTIA PI: Stephanie Forrest Institution: University of New Mexico Authors: F. Esponda, E. S. Ackley, S. Forrest, P. Helman Research Objectives: • Create a representation of data that naturally protects privacy. • Dynamically construct and maintain collections of private data. Approach: • Store the negative image of a set of data records rather than the records themselves. • Logically divide the space of possible records (fixed length binary strings) into two disjoint sets: DB and U-DB. • Construct a compressed version of U-DB that can be efficiently created and updated. • Negative databases (NDB) are defined over the {0,1,*} alphabet, where * is the “wild card” symbol and stands for both a 1 and a 0 at the position where it appears. Broader Impact: • Privacy is an inherent property of the representation. • Negative representations of information have many potential applications, e.g., set intersection, surveys, and secret sharing. * Best paper award. Significant Results: • If an insider acquires a proper subset of the negative database, she acquires little useful information. • If an insider obtains the entire negative database, it is an NP-hard problem for her to recover the original positive set of strings DB: • A tractable query: “Is string x in DB?” • An intractable query: “What strings matching x in fields F1...Fk are in DB?” Graphic: Ex. of negative-db construction DB U-DB NDB 000 001 01* 101 010 0*1 111 011 1*0 100 110 Paper: “Two Can Keep a Secret: A Distributed Architecture for Secure Database Services” (CIDR 2005) PORTIA PI: H. Garcia-Molina, R. Motwani Institution: Stanford University Authors: G. Aggarwal, M. Bawa, P. Ganesan, et al. Research Objectives: Organizations want to outsource database services but are concerned about data privacy. In this work, we ask how one can protect outsourced data by exploiting multiple service providers. Approach: We propose that data be partitioned across two service providers in such a way that neither provider has useful information that can breach privacy. Queries are answered by formulating appropriate subqueries at each provider and combining the results intelligently. By modeling privacy constraints realistically, it is possible to avoid encrypting data and to execute queries efficiently while still preserving privacy. Broader Impact: • Introduce alternatives to encryption for enabling secure database services. • Formulate open problems, in both theory and systems, in the area of distributed architecture for database outsourcing. Significant Results: • New privacy model based on compliance needs • Proof-of-concept distributed architecture for secure database services • Query optimization and database design heuristics for partitioned operation Graphic: Paper: “Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems” (VLDB 2004) PORTIA PI: Hector Garcia-Molina Institution: Stanford University Authors: Prasanna Ganesan, Mayank Bawa, Hector Garcia-Molina Research Objectives: We seek to support range queries in a large P2P system while ensuring load balance. More generally, we seek to enable SQL-style queries in P2P systems and to automate physical design of parallel databases. Significant Results: • (Largest load / smallest load) 4.24. • Amortized O(1) tuples are migrated per insertion or deletion. • Fully distributed asymptotically optimal solution Approach: In both P2P and parallel database systems, we partition data into ranges and have each node store data in one contiguous range. Online load balancing is used to modify the partitions while migrating as little data as possible. Graphic: Broader Impact: • Enlarge the class of powerful multi-dimensional queries that can be executed in P2P systems. • Transfer successful P2P techniques to the realm of parallel databases. Two “universal” operations used for load balancing: (a) NbrAdjust: Data handed off to adjacent node (b) Reorder: Empty node reordered to split load Paper: “Evaluating 2-DNF Formulas on Ciphertext” (TCC 2005) PORTIA PI: Dan Boneh Institution: Stanford University Authors: Dan Boneh, Eu-Jin Goh, Kobbi Nissim Research Objectives: Encryption protects data from unauthorized access but makes it hard to use. In this work, we seek new encryption schemes that enable arbitrary computation on ciphertexts. Approach: An encryption scheme E is homomorphic to function f (or “f homomorphic”) if, given E[A] and E[B], anyone can compute E[f(A,B)]. All known efficient homomorphic encryption schemes are x homomorphic or + homomorphic but not both. We seek a fully homomorphic encryption scheme, i.e., one that is homomorphic to a logically complete operation (e.g., NAND) or set of operations. A scheme that is both x and + homomorphic is logically complete. Broader Impact: • Enable one-round, secure two-party computation. • Improve applications such as grid computing on sensitive data that use homomorphic encryption. Significant Results: We provide an encryption scheme that is both homomorphic up to a single and + homomorphic. Applications include: • One-round, secure two-party evaluation of 2-DNFs and dot products • Improved PIR and e-voting Graphic: Evaluating 2-DNFs Bob A = (a1,…,an) Invoke Keygen(). Encrypt A Alice (x1,…,xn) = ki=1(yi,1yi,2) = arith. of replace by +, by , xi by (1- xi). PK, E[a1],…,E[an] E[r (A)] If decrypt = 0, emit 0. Else, 1. Eval. E[r (A)] for random r Paper: “Stronger Pwd. Auth. with Browser Extensions” (USENIX Security 05) PORTIA PIs: D. Boneh, J. Mitchell Institution: Stanford University Authors: B. Ross, C. Jackson, N. Miyake, D. Boneh, J. Mitchell Research Objectives: Phishing sites and weak passwords have led to Internet identity theft. We want to provide increased security against these attacks with minimal change for both the user and the server. Approach: We have developed a web-browser extension, called PwdHash, that applies a cryptographic hash function to the user’s password (using data associated with the web site and an optional global password as salt). The original password is discarded, and the hashed password is sent to the website instead. A web-based interface provides an alternate mechanism for generating passwords if the browser extension is not available. Broader Impact: • Enable further innovation in authentication protocols by providing secure password entry into a web browser. • Enable design of web browsers that prevent userinterface spoofing in Javascript and Flash. Significant Results: • Theft of hashed password will not yield a password that can be used to log in to another site. • Theft of user’s computer will not yield any passwords. • Unobtrusive user interface provides security against password-field spoofing and other Javascript attacks. Graphic: Secure Authentication User Interface Remote Authentication User Interface Paper: “Stably Computable Properties of Network Graphs” (DCOSS 2005) PORTIA PI: Joan Feigenbaum Institution: Yale University Authors: D. Angluin, J. Aspnes, M. Chan, M. J. Fischer, H. Jiang, R. Peralta Research Objectives: Significant Results: Anonymous, finite-state sensing devices can be deployed in an ad-hoc communication network of arbitrary size and unknown topology. We seek to characterize the computations that can be done by these sensors. • Presburger graph predicates are stably computable with stabilizing inputs in the family of complete interaction graphs. Approach: We ask what properties of the network the sensors can detect and how they can use the properties to organize computation. We define the notion of stabilizing inputs to such devices and consider the class of predicates that are stably computable in weakly connected networks. We also study the effects of nondeterministic transition functions. Broader Impact: • Explore new models of computation that arise from new technologies such as sensor nets. • Improve understanding of the effects of anonymity and nondeterministic interaction on computational systems and their users. • One can stably determine whether the interaction graph contains a fixed subgraph, a directed cycle, or a directed cycle of odd size. • Nondeterministic transition functions do not increase the class of stably computable predicates. Graphic: Paper: “Simulatable Auditing” (PODS 2005) PORTIA PI: Rajeev Motwani Institution: Stanford University Authors: K. Kenthapadi, N. Mishra, K. Nissim Research Objectives: In online query auditing, one is given a sequence of (query, answer) pairs, together with a new query; one should refuse to answer the new query if privacy may be breached and give the true answer otherwise. We seek auditing methods in which query denials provably do not leak information. Approach: In naïve query-auditing systems, denials may leak information. We propose a model in which the decision to deny can be made by either the auditor or the user. We introduce a new definition of privacy and construct simulatable auditors for sum and max queries. Broader Impact: • Broaden and deepen researchers’ understanding of the notion of privacy in this context. • Raise awareness of the facts that denials can leak information and, hence, that query auditing must be done carefully. Significant Results: • Expose weaknesses of earlier query auditors. • Provide new definitions and models. • Devise simulatable auditing algorithms for fundamental classes of queries. Graphic: Paper: “Anonymizing Tables” (ICDT 2005) PORTIA PI: Rajeev Motwani Institution: Stanford University Authors: Aggarwal, Feder, Kenthapadi, Motwani, Panigrahy, Thomas, Zhu Research Objectives: Significant Results: A k-anonymous relational database containing personal information provides individual privacy and data integrity. In this work, we investigate the computational complexity of the k-anonymity problem. • The k-anonymity problem is NP-hard. Approach: We seek to minimize the number of cells suppressed while ensuring that, for each tuple in the modified table, there are at least k-1 other tuples in the modified table that are identical to it in the columns that will be made public. Although the general problem is NP-hard, we use a graph representation to obtain good approximation algorithms. We also show a matching lower bound for any algorithm that uses only the graph representation. • There is a polynomial-time O(k)-approximation algorithm for the general k-anonymity problem. • There are polynomial-time 1.5-approximation and 2-approximation algorithms for 2-anonymity and 3-anonymity, respectively. Graphic: Original table Broader Impact: Improve understanding of the algorithmic properties of a popular approach to deidentification of personal data. 2-anonymized version of the table Paper: “Fast Monte Carlo Algorithms for Massive Matrices” PORTIA PI: Ravi Kannan Institution: Yale University Authors: P. Drineas, R. Kannan, M. W. Mahoney Research Objectives: As the capacity of external storage devices has increased enormously, random access to their contents has become prohibitively slow. We seek efficient algorithms for computations on massive matrices that are stored externally. Approach: We formulate the pass-efficient model of computation. In this model, algorithm-design goals are faster running time and fewer passes over the matrices. To achieve these, we devise approximation algorithms that use sampling techniques. The algorithms compute not on whole matrices but rather on a small sample of rows and columns of the matrices. Significant Results: We give pass-efficient algorithms for: • Matrix mult., SVD, and CUR Decomposition • Feasibility testing for Linear Programs • Gram-Matrix approximation for Statistical Learning Graphic: U V C C Broader Impact: • Stimulate research on massive-data-set algorithms in the field of computational linear algebra. • Improve applications such as Latent Semantic Indexing that are based on matrix computation. H(=UC) A Y(=VC) T CC Diagram of the SVD Algorithm Paper: “Secure Computation of Surveys” (SMP 2004) PORTIA PI: Joan Feigenbaum Institution: Yale University Authors: J. Feigenbaum, B. Pinkas, R. Ryger, F. Saint-Jean Research Objectives: Many people and organizations decline to participate in surveys because of potential misuse of sensitive data. We investigate privacy-preserving surveys, using the Taulbee faculty-salary survey as a concrete example. Approach: Every function can be computed in a privacypreserving manner, using a general-purpose secure, multiparty function-evaluation (SMFE) protocol; however, this is not efficient enough for practical salary surveys. We use the run-time system of FairPlay, a general-purpose SMFE system, and a special-purpose compiler that generates an oddeven sorting-network circuit for the specified number and lengths of inputs. Significant Results: • User-friendly implementation of privacy-preserving data-mining protocols is an achievable goal. FairPlay is useful. • There are significant barriers to adoption, including the need for privacy-preserving data cleaning uncertainty about compliance with laws and policies Graphic: Broader Impact: • Raise awareness of barriers to adoption of privacypreserving data mining. • Release an open-source, privacy-preserving salary-survey package that can be used by other researchers. M input providers (outside) and N computation servers (inside) Papers: “Short Group Signatures” (Crypto 2004, CCS 2004) PORTIA PI: Dan Boneh Institution: Stanford University Authors: D. Boneh, X. Boyen, H. Shacham Research Objectives: Group signatures provide privacy for signers. Signer privacy is important, but existing groupsignature schemes are impractical. We seek to construct new, practical group signatures. Approach: We construct short group signatures from a zeroknowledge proof of knowledge for possession of a Strong Diffie-Hellman tuple in bilinear groups. Signing and verification is faster in our scheme than in previous schemes, and signatures are 20 times shorter. We also provide a new revocation mechanism for group signatures, Verifier-Local Revocation (VLR), that is better suited for trustedcomputing applications. Broader Impact: • Group sigs are a powerful privacy mechanism. • They can be applied to Trusted Computing and Vehicle Safety. • We plan to release an open-source library implementing our group signatures. Significant Results: • Short and efficient group signatures • Suitable for: – Private attestation in Trusted Computing – Vehicle Safety Ad-hoc Networks • Verifier-Local Revocation (VLR) enables simple TPM revocation in Trusted Computing. Signature Scheme Signature size Ordinary RSA signatures 1,024 bits ACJT00 group signatures 32,000 bits BBS04 group signatures 1,536 bits Graphic: Private Attestation Desktop Computer with TPM Support Online Merchant Paper: “Personal Information & the U.S. Census: A Model of Contextual Integrity” PORTIA PI: Helen Nissenbaum Institution: New York University Author: Timothy Weber PORTIA Collaborator: Sam Hawala, US Census Bureau Research Objectives: • Better understand the development of informationhandling norms within a firmly established context. • Use the theory of contextual integrity as a model with which to analyze current policies that regulate the flow of census information. • Develop policy heuristics aimed at upholding a model of privacy as contextual integrity. Approach: • Examine the U.S. Census as a context in which significant attention has been focused on developing good information-handling policies. • Trace the historical evolution of practices and policies regulating the flow of census data to understand the rationale underlying current policies. Broader Impact: • Highlight the importance of census policies regulating categories of information and access to identifiable data. • Render explicit the reasons that certain datahandling practices matter. Significant Results: • Provide an opportunity for the user community (Statistical Research Division, U.S. Census Bureau) to reflect on its policies and purposes. • Articulate historical transformations in census policies to provide better perspective on possible responses to new challenges, e.g., data mining that may increase the probability of reidentifying personal information. Graphic: Norms of Appropriateness are Brought to bear on Categories of Information, such as the questions Asked on census schedules. Disclosure-avoidance techniques are applied To aggregated micro-data to prevent identification Of individuals in small sets. Personal Info. Race Income Age Norms of Transmission are Brought to bear on determining Who has access to what information And under what conditions. Paper: “Privacy-Preserving Classification of Customer Data” (SDM 2005) PORTIA PI: Rebecca N. Wright Institution: Stevens Institute of Technology Authors: Z. Yang, S. Zhong, R. N. Wright Many data-mining algorithms compute frequencies of combinations of attributes. We ask how data miners can learn frequencies in customer data without compromising customer privacy. Approach: We propose a privacy-preserving frequencymining protocol with which an online data miner can compute the frequency of customer’s data without collecting the customer’s actual data. Complex datamining models can be learned using this protocol, e.g., naïve Bayes classifiers, ID3 trees, and association rules. The experimental results show that the proposed solutions are very efficient when learning data-mining models in the fully distributed setting. Broader Impact: • Explore a new direction for privacy-preserving data mining in the fully distributed setting. • Show that both privacy and accuracy in data mining can be achieved using cryptographic techniques. Significant Results (for Naïve Bayes): 19 Learning Time (Secs) Research Objectives: 14 9 4 2000 4000 6000 8000 10000 Num. of Customers Graphic: Protocol in Fully Distributed Setting Customers …. …. Miner Cryptographic Frequency Mining Protocol Paper: “Graph Distances in the Streaming Model: the Value of Space” (SODA 2005) PORTIA PI: Joan Feigenbaum Institution: Yale University Authors: J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, J. Zhang Research Objectives: Massive graphs arise naturally when large data sets model interactions. In this setting, traditional graph algorithms are not efficient. We investigate efficient graph algorithms in the streaming model. Approach: There is a tradeoff between the accuracy of the computation and the time-space efficiency of the algorithm. We consider approximation algorithms that give a result with bounded error but use nearlinear time and much less space than traditional algorithms. In particular, we devise streaming algorithms that construct graph spanners and use the spanners to approximate distances in the graph. Broader Impact: Significant Results: • We present a streaming algorithm that, for a graph G=(V,E), constructs a spanner in one pass and uses |V|•polylog(|V|) space. • We show a lower bound on the number of passes needed to find the vertices at distance d from a specific vertex. Graphic: 3 5 1 4 2 (1,2) (1,3) (1,5) (2,3) (2,4) (3,4) (3,5) (4,5) 3 the streaming model. computation and spanners in massive graphs. Stream of Edges Streaming Algorithm • Initiate the study of massive-graph problems in • Broaden and deepen understanding of distance Input Graph 5 1 4 2 Graph Spanner Paper: “Towards a Theory of Data Entanglement” (ESORICS 2004) PORTIA PI: Joan Feigenbaum Institution: Yale University Authors: J. Aspnes, J. Feigenbaum, A. Yampolskiy, S. Zhong Research Objectives: Organizations can offer high-capacity, low-cost storage services, but users typically do not trust them. In this work, we ask how one can protect data stored on an untrusted server. Approach: We propose that users cryptographically entangle their data in such a way that, if one user’s data were corrupted, other users’ data would also be corrupted. The strongest form of entanglement is called all-ornothing integrity (AONI) ― either all users’ data are fine, or nobody’s are fine. We formalize the notion of entanglement in various models. All-or-nothing integrity, if feasible, would achieve our goals, because a well known, visible storage service cannot risk offending all its users. Broader Impact: • Raise public awareness of and research interest in cryptographically protected storage services. • Improve understanding of entanglement and of systems (e.g., Dagster and Tangler) that use it. Significant Results: Recovery Alg. Standar d Adversary Public Private Arbitrary AONI AONI AONI Entropy-Reducing AONI AONI AONI Graphic: Paper: “Privacy-Enhancing k-Anonymization of Customer Data” (PODS 2005) PORTIA PI: Rebecca N. Wright Institution: Stevens Institute of Technology Authors: S. Zhong, Z. Yang, R. N. Wright Research Objectives: The technique of k-anonymization is a powerful tool for data de-identification. In this work, we ask how one can k-anonymize customer data while maintaining end-to-end privacy. Approach: We consider two versions of the problem. For our first version, we develop a protocol in which the miner extracts the k-anonymous part of the customer data. For our second version, we present a distributed version of Meyerson and Williams's algorithm [MW] for k-anonymization. For both solutions, we rigorously define and prove the security guarantee achieved. Significant Results: Metric Privacy Guarantee Solution Computational Overhead Extraction of kanonymous part O(#customers) Ideal Privacy customer customer Cryptographic kanonymization process Broader Impact: customer Learning only k-anonymous customer data • Promote research interest in cryptographically secure protocols for databases. • Extend the study of data de-identification to distributed settings. O((#customers)2 k) Distributed MW Revealing row algorithm distances only Graphic: Solution Overview customer customer miner Paper: “Personal Information & the Design of Vehicle Safety Communication Technologies: An Application of Privacy as Contextual Integrity” PORTIA PI: Helen Nissenbaum Institution: New York University Author: Michael Zimmer PORTIA Collaborator: Dan Boneh, Stanford Research Objectives: • Determine how the design of VSC technologies might alter data flows of personal information. • Raise awareness among the researchers and engineers designing and writing the standards for VSC applications of the privacy implications of their design decisions. • Produce policy analyses and design heuristics to ensure that contextual integrity is preserved in the design of VSC technologies. Approach: • Conceptualize the privacy of personal information flows in the context of highway travel in terms of the theory of privacy as contextual integrity. • Enter the VSC design community to ensure that the value of privacy is a constitutive part of the design process, not merely retrofitted after completion. Broader Impact: • Improve understanding of the theory of privacy as contextual integrity. • Reveal how close attention to values can inform and guide the design of information technologies. Significant Results: • VSC technologies have the potential to disrupt the contextual integrity of personal information flows in the context of highway travel. • But, our acceptance into the VSC design community has been limited, threatening our ability to ensure that the value of privacy is a constitutive part of the technological design process. • Successfully entering the design community remains an open research problem. Before VSC Cameras and police can visually record information under favorable conditions, only if vehicle happens to pass in front of camera/police. No information shared Visual information available: License plate, vehicle description, general location With VSC Digital data transmitted: Unique identifier, GPS location, telemetry Widely dispersed receivers or police can digitally record data from all vehicles within 1000 meters.

Descargar
# Paper: “Secure Computation of the k