In an era dominated by big data and machine learning, establishing valuable data collaboration has never been more critical. However, such collaborations must operate under regulatory and legal constraints. Two-party Privacy-Preserving Record Linkage (PPRL) emerges to assess the potential collaboration value and also ensure the privacy and security of the involved data. Nevertheless, the substantial computational and communication overheads associated with PPRL hinder its practical adoption in data markets with numerous potential collaborators. Therefore, we present the Screening-then-Linkage framework, which incorporates a lightweight Screening phase prior to the resource-intensive PPRL phase, i.e., PPRS, to mitigate the scalability issue of PPRL. We propose a circuit-PSI-based system, named Appraisal to realize a secure, effective, and efficient PPRS. To reconcile the approximate matching and/or schema-aware setting required in PPRS with the limitations of the circuit-PSI supporting only symmetric functions, we propose a more communication-efficient secure permutation, i.e., Oblivious Attribute/Feature Alignment protocol tailored for PPRS. This protocol supports a broader range of comparison functions and significantly improves efficiency, i.e., reducing communication costs by a factor of 14 compared to the conventional protocol. Our rigorous analysis and comprehensive empirical evaluations demonstrate the security, effectiveness, and efficiency of Appraisal. Appraisal can accommodate up to 850x more records than the SOTA PPRS system, SFour, within the same constraints. Moreover, it is 165x faster than SOTA PPRL, indicating the Screening-then-Linkage framework substantially decreases the computation time required to identify the most valuable collaborators from a large pool of candidates.

Multi-party computation (MPC) allows parties to interact with cloud-based data and services while maintaining privacy and confidentiality of their private data. As a special case of MPC, private set intersection (PSI) protocols focus on securely computing the intersection between a server and a client of their private set. Our research extends the threshold functionality for PSI within the realm of cloud computing, where the server possesses a larger set than the client. This paper fills this gap by proposing new private intersection cardinality (PSI-CA) protocol, and more broadly, threshold private set intersection (tPSI) protocol using fully homomorphic encryption (FHE). In tPSI protocol, two parties holding two private sets collaboratively compute the intersection and reveal the result if and only if the size of the intersection exceeds some predefined threshold. In this process, no other information, in particular, elements not in the intersection remain hidden. The problem of PSI-CA and tPSI has many applications in online collaboration,e.g., fingerprint matching, online dating, and ride sharing. At a high level, we use FHE to encrypt a Bloom filter (BF) that encodes the small set and homomorphically check whether the elements in the larger set belongs to the small set,e.g., homomorphic membership test. Counting the number of positive membership directly already yields a PSI-CA protocol with optimal asymptotic communication complexity Ω(n) = Ω(min(N,n)), whereN(resp.n) is the size of the large (resp. small) set. To construct a tPSI protocol, we develop a novel secret token generation protocol: a shared secret token is generated if and only if the intersection size satisfies the threshold condition, by exploiting the programmable bootstrapping technique in FHE. This new secret token generation protocol, when composed with any standard PSI protocol, yields a tPSI with the same asymptotic communication complexity as the chosen plain PSI. Along the way, we develop specific FHE optimizations that might be of independent interest. These optimizations overcome the weakness of low precision in programmable bootstrapping. As a result, tPSI over relatively large sets can be supported.

Reputation/trust-based blockchain systems have attracted considerable research interests for better integrating Internet of Things with blockchain in terms of throughput, scalability, energy efficiency, and incentive aspects. However, most existing works only consider static adversaries. Hence, they are vulnerable to slowly adaptive attackers, who can target validators with high reputation value to severely degrade the system performance. Therefore, we introduce$\textsf{zkRep}$, a privacy-preserving scheme tailored for reputation-based blockchains. Our basic idea is to hide both the identity and reputation of the validators by periodically changing the identity and reputation commitments (i.e., aliases), which makes it much more difficult for slowly adaptive attackers to identify validators with high reputation value. To realize this idea, we utilize privacy-preserving Pedersen-commitment-based reputation updating and leader election schemes that operate on concealed reputations within an epoch. We also introduce a privacy-preserving identity update protocol that changes the identity and time-window-based cumulative reputation commitments during each epoch transition. We have implemented and evaluated$\textsf{zkRep}$on the Amazon Web Service. The experimental results and analysis show that$\textsf{zkRep}$achieves great privacy-preserving features against slowly adaptive attacks with little overhead.

Deep learning unlocks applications with societal impacts, e.g., detecting child exploitation imagery and genomic analysis of rare diseases. Deployment, however, needs compliance with stringent privacy regulations. Training algorithms that preserve the privacy of training data are in pressing need. Purely cryptographic approaches can protect privacy, but they are still costly, even when they rely on two or more non-colluding servers. Seemingly-"trivial" operations in plaintext quickly become prohibitively inefficient when a series of them are "crypto-processed," e.g., (dynamic) quantization for ensuring the intermediate values would not overflow. Slalom, recently proposed by Tramer and Boneh, is the first solution that leverages both GPU (for efficient batch computation) and a trusted execution environment (TEE) (for minimizing the use of cryptography). Roughly, it works by a lot of pre-computation over known and fixed weights, and hence it only supports private inference. Five related problems for private training are left unaddressed. Goten, our privacy-preserving training and prediction framework, tackles all five problems simultaneously via our careful design over the "mismatched" cryptographic and GPU data types (due to the tension between precision and efficiency) and our round-optimal GPU-outsourcing protocol (hence minimizing the communication cost between servers). It 1) stochastically trains a low-bitwidth yet accurate model, 2) supports dynamic quantization (a challenge left by Slalom), 3) minimizes the memory-swapping overhead of the memory-limited TEE and its communication with GPU, 4) crypto-protects the (dynamic) model weight from untrusted GPU, and 5) outperforms a pure-TEE system, even without pre-computation (needed by Slalom). As a baseline, we build CaffeScone that secures Caffe using TEE but not GPU; Goten shows a 6.84x speed-up of the whole VGG-11. Goten also outperforms Falcon proposed by Wagh et al., the latest secure multi-server cryptographic solution, by 132.64x using VGG-11. Lastly, we demonstrate Goten's efficacy in training models for breast cancer diagnosis over sensitive images.

Cyber-physical systems revolutionize how we interact with physical systems. Smart grid is a prominent example. With new features such as fine-grained billing, user privacy is at a greater risk than before. For instance, a utility company () can infer users’ (fine-grained) usage patterns from their payment. The literature only focuses on hiding individual meter readings in bill calculation. It is unclear how to preserve amount privacy when the needs to assert that each user has settled the amount as calculated in the bill.

Deduplication is widely used for reducing the storage requirement for storage service providers. Nevertheless, it is unclear how to support deduplication of encrypted data securely until the study of Bellare et al. on message-locked encryption (MLE, Eurocrypt 2013). While updating (shared) files is natural, existing MLE solutions do not allow efficient update of encrypted files stored remotely. Even modifying a single bit requires the expensive way of downloading and decrypting a large ciphertext (then re-uploading). This paper initiates the study of updatable block-level MLE, a new primitive in incremental cryptography and cloud cryptography. Our proposed provably-secure construction is updatable with computation cost logarithmic in the file size. It naturally supports block-level deduplication. It also supports proof-of-ownership which protects storage providers from being abused as a free content distribution network. Our experiments show its practical performance relative to the original MLE and existing non-updatable block-level MLE.

Deduplication is a widely used technique for reducing storage space of cloud service providers. Yet, it is unclear how to support deduplication of encrypted data securely until the study of Bellareetal on message-locked encryption (Eurocrypt 2013). Since then, there are many improvements such as strengthening its security, reducing client storage, etc. While updating a (shared) file is common, there is little attention on how to efficiently update large encrypted files in a remote storage with deduplication. To modify even a single bit, existing solutions require the trivial and expensive way of downloading and decrypting the large ciphertext.

Abstract Sharing information to others is common nowadays, but the question is with whom to share. To address this problem, we propose the notion of secret transfer with access structure (STAS). STAS is a twoparty computation protocol that enables the server to transfer a secret to a client who satisfies the prescribed access structure. In this paper, we focus on threshold secret transfer (TST), which is STAS for threshold policy and can be made more expressive by using linear secret sharing. TST enables a number of applications including a simple construction of oblivious transfer (OT) with threshold access control, and (a variant of) threshold private set intersection (t-PSI), which are the first of their kinds in the literature to the best of our knowledge. The underlying primitive of STAS is a variant of OT, which we call OT for a sparse array. We provide two constructions which are inspired by state-of-the-art PSI techniques including oblivious polynomial evaluation (OPE) and garbled Bloom filter (GBF). The OPEbased construction is secure in the malicious model, while the GBF-based one is more efficient. We implemented the latter one and showed its performance in applications such as privacy-preserving matchmaking.