We propose a scheme for outsourcing Private Information Retrieval (PIR) to untrusted servers while protecting the privacy of the database owner as well as that of the database clients. We observe that by layering PIR on top of an Oblivious RAM (ORAM) data layout, we provide the ability for the database owner to perform private writes, while database clients can perform private reads from the database even while the owner is offline. We can also enforce pricing and access control on a per-record basis for these reads. This extends the usual ORAM model by allowing multiple database readers without requiring trusted hardware; indeed, almost all of the computation in our scheme during reads is performed by untrusted cloud servers. Built on top of a simple ORAM protocol, we implement a real system as a proof of concept. Our system privately updates a 1 MB record in a 16 GB database with an average end-to-end overhead of 1.22 seconds and answers a PIR query within 3.5 seconds over a 2 GB database. We make an observation that the database owner can always conduct a private read as an ordinary database client, and the private write protocol does not have to provide a "read" functionality as a standard ORAM protocol does. Based on this observation, we propose a second construction with the same privacy guarantee, but much faster. We also implement a real system for this construction, which privately writes a 1 MB record in a 1 TB database with an amortized end-to-end response time of 313 ms. Our first construction demonstrates the fact that a standard ORAM protocol can be used for outsourcing PIR computations in a privacy-friendly manner, while our second construction shows that an ad-hoc modification of the standard ORAM protocol is possible for our purpose and allows more efficient record updates.

Cryptographic credentials allow user authorizations to be granted and verified. and have such applications as e-Passports, e-Commerce, and electronic cash. This thesis proposes a privacy protecting approach of binding biometrically derived keys to cryptographic credentials to prevent unauthorized lending. Our approach builds on the 2011 work of Adams, offering additional benefits of privacy protection of biometric information, generality on biometric modalities, and performance. Our protocol integrates into Brands’ Digital Credential scheme, and the Anonymous Credentials scheme of Camenisch and Lysyanskaya. We describe a detailed integration with the Digital Credential Scheme and sketch the integration into the Anonymous Credentials scheme. Security proofs for non-transferability, correctness of ownership, and unlinkability are provided for the protocol’s instantiation into Digital Credentials. Our approach uses specialized biometric devices in both the issue and show protocols. These devices are configured with our proposed primitive, the fuzzy ex-tractor indistinguishability adaptor which uses a traditional fuzzy extractor to create and regenerate cryptographic keys from biometric data and IND-CCA2 secure en-cryption protect the generated public data against multiplicity attacks. Pedersen commitments are used to hold the key at issue and show time, and A zero-knowledge proof of knowledge is used to ensure correspondence of key created at issue-time and regenerated at show-time. The above is done in a manner which preserves biometric privacy, as and delivers non-transferability of digital credentials. The biometric itself is not stored or divulged to any of the parties involved in the protocol. Privacy protection in multiple enrollments scenarios is achieved by the fuzzy extractor indistinguishability adapter. The zero knowledge proof of knowledge is used in the showing protocol to prove knowledge of values without divulging them.

Cryptographic credentials allow user authorizations to be granted and verified. and have such applications as e-Passports, e-Commerce, and electronic cash. This thesis proposes a privacy protecting approach of binding biometrically derived keys to cryptographic credentials to prevent unauthorized lending. Our approach builds on the 2011 work of Adams, offering additional benefits of privacy protection of biometric information, generality on biometric modalities, and performance. Our protocol integrates into Brands’ Digital Credential scheme, and the Anonymous Credentials scheme of Camenisch and Lysyanskaya. We describe a detailed integration with the Digital Credential Scheme and sketch the integration into the Anonymous Credentials scheme. Security proofs for non-transferability, correctness of ownership, and unlinkability are provided for the protocol’s instantiation into Digital Credentials. Our approach uses specialized biometric devices in both the issue and show protocols. These devices are configured with our proposed primitive, the fuzzy ex-tractor indistinguishability adaptor which uses a traditional fuzzy extractor to create and regenerate cryptographic keys from biometric data and IND-CCA2 secure en-cryption protect the generated public data against multiplicity attacks. Pedersen commitments are used to hold the key at issue and show time, and A zero-knowledge proof of knowledge is used to ensure correspondence of key created at issue-time and regenerated at show-time. The above is done in a manner which preserves biometric privacy, as and delivers non-transferability of digital credentials. The biometric itself is not stored or divulged to any of the parties involved in the protocol. Privacy protection in multiple enrollments scenarios is achieved by the fuzzy extractor indistinguishability adapter. The zero knowledge proof of knowledge is used in the showing protocol to prove knowledge of values without divulging them.

We propose a scheme for outsourcing Private Information Retrieval (PIR) to untrusted servers while protecting the privacy of the database owner as well as that of the database clients. We observe that by layering PIR on top of an Oblivious RAM (ORAM) data layout, we provide the ability for the database owner to perform private writes, while database clients can perform private reads from the database even while the owner is offline. We can also enforce pricing and access control on a per-record basis for these reads. This extends the usual ORAM model by allowing multiple database readers without requiring trusted hardware; indeed, almost all of the computation in our scheme during reads is performed by untrusted cloud servers. Built on top of a simple ORAM protocol, we implement a real system as a proof of concept. Our system privately updates a 1 MB record in a 16 GB database with an average end-to-end overhead of 1.22 seconds and answers a PIR query within 3.5 seconds over a 2 GB database. We make an observation that the database owner can always conduct a private read as an ordinary database client, and the private write protocol does not have to provide a "read" functionality as a standard ORAM protocol does. Based on this observation, we propose a second construction with the same privacy guarantee, but much faster. We also implement a real system for this construction, which privately writes a 1 MB record in a 1 TB database with an amortized end-to-end response time of 313 ms. Our first construction demonstrates the fact that a standard ORAM protocol can be used for outsourcing PIR computations in a privacy-friendly manner, while our second construction shows that an ad-hoc modification of the standard ORAM protocol is possible for our purpose and allows more efficient record updates.

Cryptographic credentials allow user authorizations to be granted and verified. and have such applications as e-Passports, e-Commerce, and electronic cash. This thesis proposes a privacy protecting approach of binding biometrically derived keys to cryptographic credentials to prevent unauthorized lending. Our approach builds on the 2011 work of Adams, offering additional benefits of privacy protection of biometric information, generality on biometric modalities, and performance. Our protocol integrates into Brands’ Digital Credential scheme, and the Anonymous Credentials scheme of Camenisch and Lysyanskaya. We describe a detailed integration with the Digital Credential Scheme and sketch the integration into the Anonymous Credentials scheme. Security proofs for non-transferability, correctness of ownership, and unlinkability are provided for the protocol’s instantiation into Digital Credentials. Our approach uses specialized biometric devices in both the issue and show protocols. These devices are configured with our proposed primitive, the fuzzy ex-tractor indistinguishability adaptor which uses a traditional fuzzy extractor to create and regenerate cryptographic keys from biometric data and IND-CCA2 secure en-cryption protect the generated public data against multiplicity attacks. Pedersen commitments are used to hold the key at issue and show time, and A zero-knowledge proof of knowledge is used to ensure correspondence of key created at issue-time and regenerated at show-time. The above is done in a manner which preserves biometric privacy, as and delivers non-transferability of digital credentials. The biometric itself is not stored or divulged to any of the parties involved in the protocol. Privacy protection in multiple enrollments scenarios is achieved by the fuzzy extractor indistinguishability adapter. The zero knowledge proof of knowledge is used in the showing protocol to prove knowledge of values without divulging them.

While advances to the Internet have enabled users to easily interact and exchange information online, they have also created several opportunities for adversaries to prey on users’ private information. Whether the motivation for data collection is commercial, where service providers sell data for marketers, or political, where a government censors, blocks and tracks its people, or even personal, for cyberstalking purposes, there is no doubt that the consequences of personal information leaks can be severe. Low-latency anonymity networks have thus emerged as a solution to allow people to surf the Internet without the fear of revealing their identities or locations. In order to provide anonymity to users, anonymity networks route users’ traffic through several intermediate relays, which causes unavoidable extra delays. However, although these networks have been originally designed to support interactive applications, due to a variety of design weaknesses, these networks offer anonymity at the expense of further intolerable performance costs, which disincentivize users from adopting these systems. In this thesis, we seek to improve the network performance of low-latency anonymity networks while maintaining the anonymity guarantees they provide to users today. As an experimentation platform, we use Tor, the most widely used privacy-preserving network that empowers people with low-latency anonymous online access. Since its introduction in 2003, Tor has successfully evolved to support hundreds of thousands of users using thousands of volunteer-operated routers run all around the world. Incidents of sudden increases in Tor’s usage, coinciding with global political events, confirm the importance of the Tor network for Internet users today. We identify four key contributors to the performance problems in low-latency anonymity networks, exemplified by Tor, that significantly impact the experience of low-latency application users. We first consider the lack of resources problem due to the resource-constrained routers, and propose multipath routing and traffic splitting to increase throughput and improve load balancing. Second, we explore the poor quality of service problem, which is exacerbated by the existence of bandwidth-consuming greedy applications in the network. We propose online traffic classification as a means of enabling quality of service for every traffic class. Next, we investigate the poor transport design problem and propose a new transport layer design for anonymous communication networks which addresses the drawbacks of previous proposals. Finally, we address the problem of the lack of congestion control by proposing an ATM-style credit-based hop-by-hop flow control algorithm which caps the queue sizes and allows all relays to react to congestion in the network. Our experimental results confirm the significant performance benefits that can be obtained using our privacy-preserving approaches.

While advances to the Internet have enabled users to easily interact and exchange information online, they have also created several opportunities for adversaries to prey on users’ private information. Whether the motivation for data collection is commercial, where service providers sell data for marketers, or political, where a government censors, blocks and tracks its people, or even personal, for cyberstalking purposes, there is no doubt that the consequences of personal information leaks can be severe. Low-latency anonymity networks have thus emerged as a solution to allow people to surf the Internet without the fear of revealing their identities or locations. In order to provide anonymity to users, anonymity networks route users’ traffic through several intermediate relays, which causes unavoidable extra delays. However, although these networks have been originally designed to support interactive applications, due to a variety of design weaknesses, these networks offer anonymity at the expense of further intolerable performance costs, which disincentivize users from adopting these systems. In this thesis, we seek to improve the network performance of low-latency anonymity networks while maintaining the anonymity guarantees they provide to users today. As an experimentation platform, we use Tor, the most widely used privacy-preserving network that empowers people with low-latency anonymous online access. Since its introduction in 2003, Tor has successfully evolved to support hundreds of thousands of users using thousands of volunteer-operated routers run all around the world. Incidents of sudden increases in Tor’s usage, coinciding with global political events, confirm the importance of the Tor network for Internet users today. We identify four key contributors to the performance problems in low-latency anonymity networks, exemplified by Tor, that significantly impact the experience of low-latency application users. We first consider the lack of resources problem due to the resource-constrained routers, and propose multipath routing and traffic splitting to increase throughput and improve load balancing. Second, we explore the poor quality of service problem, which is exacerbated by the existence of bandwidth-consuming greedy applications in the network. We propose online traffic classification as a means of enabling quality of service for every traffic class. Next, we investigate the poor transport design problem and propose a new transport layer design for anonymous communication networks which addresses the drawbacks of previous proposals. Finally, we address the problem of the lack of congestion control by proposing an ATM-style credit-based hop-by-hop flow control algorithm which caps the queue sizes and allows all relays to react to congestion in the network. Our experimental results confirm the significant performance benefits that can be obtained using our privacy-preserving approaches.

On the Internet today, users are accustomed to disclosing personal information when accessing a new service. When a user does so, there is rarely a system in place which allows the user to monitor how his or her information is actually shared or used by services. One proposed solution to this problem is to have services perform transparency logging on behalf of users, informing them how their data is processed as processing is taking place. We have recently participated in a collaboration to develop a privacy-preserving secure logging scheme that can be used for the purpose of transparency logging. As part of that collaboration we created a proof of concept implementation. In this thesis, we elaborate on that implementation and integrate it with a minimalistic open source issue-tracking system. We evaluate the amount of work required to integrate the logging system and attempt to identify potential integration problems. Using this issue-tracking system we then design and implement a scenario that demonstrates the value of the logging system to the average user.

User tracking and profiling is a growing threat to online privacy. Whilst Internet users can choose to withhold their personal information, their Internet usage can still be traced back to a unique IP address. This study considers anonymity as a strong and useful form of privacy protection. More specifically, we examine how current anonymity solutions suffer from a number of deficiencies: they are not commonly used, are vulnerable to a host of attacks or are impractical or too cumbersome for daily use. Most anonymity solutions are centralised or partially centralised and require trust in the operators. It is additionally noted how current solutions fail to promote anonymity for common Web activities such as performing online search queries and general day-to-day Web browsing. A primary objective of this research is to develop an anonymising Web browsing protocol which aims to be (1) fully distributed, (2) offer adequate levels of anonymity and (3) enable users to browse the Internet anonymously without overly complex mixing techniques. Our research has led to an anonymising protocol called Polar. Polar is a peer-to-peer network which relays Web requests amongst peers before forwarding it to a Web server, thus protecting the requester's identity. This dissertation presents the Polar model. Design choices and enhancements to the model are discussed. The author's implementation of Polar is also presented demonstrating that an implementation of Polar is feasible. / Dissertation (MSc (Computer Science))--University of Pretoria, 2007. / Computer Science / unrestricted

Proving and verifying remotely a user's identity information have become a critical and challenging problem in the online world, with the increased number of sensitive services offered online. The digital identity management ecosystem has been evolving over the years to address this problem. However, the limitations in existing identity management approaches in handling this problem in a privacy preserving and secure manner have caused disruptions to users' digital lives and damages to revenue and reputation of service providers.<br><br>In this dissertation, we analyze different areas of the identity management ecosystem in terms of privacy and security. In our analysis, we observe three critical aspects to take into account when identifying the privacy and security requirements to address in identity management scenarios, namely: i) protecting privacy and security of digital identity and online transactions of users; ii) providing other stakeholders with assurance about user identity information and accountability of transactions; iii) preserving utility (e.g. accuracy, efficiency and deployability).<br>We show that existing authentication models and identity management protocols fail to address critical privacy and security requirements related to all these three aspects, mainly because of inherent conflicts among these requirements. <br>For example, existing authentication protocols, which aim to protect service providers from imposters by involving strong authentication factors, such as biometrics, fail to protect privacy and security of users' biometrics. Protecting an identity management system against counterfeits of identity assets, while preserving unlinkability of the transactions carried out using the identity assets, is another example of conflicting yet critical privacy and security requirements.<br>We demonstrate that careful combinations of cryptographic techniques and other technologies make it feasible to design privacy preserving identity management protocols which address critical and conflicting requirements related to the aforementioned three aspects. Certain techniques, that we have developed for these protocols, are independent contributions with applications beyond the domain of digital identity management. We validate our contributions by providing prototype implementations, experimental evaluations and security proofs.