ABSTRACT. Motivated by the recent advances in practical secure computation, we design and implement a framework for scaling solutions for the problem of private set intersection (PSI) into the realm of big data. A protocol for PSI enables two parties each holding a set of elements to jointly compute the intersection of these sets without revealing the elements that are not in the intersection. Following a long line of research, recent protocols for PSI only have approximately 5x computation and communication overhead over an insecure set intersection. However, this performance is typically demonstrated for set sizes in the order of ten million. In this work, we aim to scale these protocols to efficiently handle set sizes of one billion elements or more.

We achieve this via a careful application of a binning approach that enables parallelizing any arbitrary PSI protocol. Building on this idea, we designed and implemented a framework that takes a pair of PSI executables (i.e., for each of the two parties) that typically works for million-sized sets, and then scales it to billion sized sets (and beyond). For example, our framework can perform a join of billion-sized sets in 83 minutes compared to 2000 minutes of Pinkas et al. (ACM TPS 2018), an improvement of 25x. Furthermore, we present an end-to-end Spark application where two enterprises, each possessing private databases, can perform a restricted class of database join operations (specifically, join operations with only an on clause which is a conjunction of equality checks involving attributes from both parties, followed by a where clause which can be split into conjunctive clauses where each conjunction is a function of a single table) without revealing any data that is not part of the output.

ABSTRACT. Cheating detectable secret sharing schemes (CDSS) protect against an active adversary who modifies the shares of an unauthorized set of participants that they control, with the goal of modifying the reconstructed secret. We consider leakage resilient cheating detectable secret sharing schemes (LRCDSS) where protection is against an adversary who, in addition to the shares of an unauthorized set, has access to the leakages from all other shares. We give lower bounds on the share size of these schemes when the scheme provides $\epsilon$-indistinguishability security, and the adversary's modification of shares can be detected with probability at least $1-\delta$. We discuss our bounds in relation to other known results, relate CDSS with non-malleable secret sharing, and suggest directions for future work.

ABSTRACT. Blockchain plays an important role in distributed file systems, such as cryptocurrency. One of the important building blocks of blockchain is the key-value commitment scheme, which constructs a commitment value from two inputs: a key and a value. In an ordinal commitment scheme, a single user creates a commitment value from an input value, whereas in a key-value commitment scheme, multiple users create a commitment value from their own key and value. Nonetheless, both commitment schemes need to satisfy both binding and hiding properties. The concept of key-value commitment scheme was first proposed by Agrawal et al. in 2020 using the strong RSA assumption. They also proved its key-binding property of their key-value commitment scheme. However, key-hiding property was not yet proved. The key-hiding property was then proposed by Campaneli et al. in 2022. In this paper, we propose two lattice-based key-value commitment schemes, InsertKVC, and KVC. Furthermore, we prove the key-binding and key-hiding of both lattice-based InsertKVC and KVC for the first time. We prove the key-binding of both InsertKVC and KVC based on the short integer solutions (SIS) problem. Furthermore, we prove key-hiding of both InsertKVC and KVC based on the Decisional-SIS form problem, which we first introduced in this paper. We also discuss the difficulty of the Decisional-SIS form problem.

ABSTRACT. Ring signature allows a signer to generate a signature on behalf of a set of public keys, while a verifier can verify the signature without identifying who the actual signer is. In Crypto 2021, Yuen et al. proposed a new type of ring signature scheme called DualRing. However, it lacks forward security. The security of DualRing cannot be guaranteed if the signer's secret key is compromised. To address this problem, we introduce forward-secure DualRing, in which a signer can periodically update their secret key using a ``split-and-combine" method. A practical instantiation of our scheme enjoys a logarithmic complexity in signature size and key size. Implementation and evaluation further validate the practicality of our proposed scheme.

ABSTRACT. In 1993, Benaloh and De Mare introduced cryptographic accumulator, a primitive that allows the representation of a set of values by a short object (the accumulator) and offers the possibility to prove that some input values are in the accumulator. For this purpose, so-called asymmetric accumulators require the creation of an additional cryptographic object, called a witness. Through the years, several instantiations of accumulators were proposed either based on number theoretic assumptions, hash functions, bilinear pairings or more recently lattices. In this work, we present the first instantiation of an asymmetric cryptographic accumulator that allows private computation of the accumulator but public witness creation. This is obtained thanks to our unique combination of the pairing based accumulator of Nguyen with dual pairing vector spaces. We moreover introduce the new concept of dually computable cryptographic accumulators, in which we offer two ways to compute the representation of a set: either privately (using a dedicated secret key) or publicly (using only the scheme's public key), while there is a unique witness creation for both cases. All our constructions of accumulators have constant size accumulated value and witness, and satisfy the accumulator security property of collision resistance, meaning that it is not possible to forge a witness for an element that is not in the accumulated set. As a second contribution, we show how our new concept of dually computable cryptographic accumulator can be used to build a Ciphertext Policy Attribute Based Encryption (CP-ABE). Our resulting scheme permits policies expressed as disjunctions of conjunctions (without ``NO'' gates), and is adaptively secure in the standard model. This is the first CP-ABE scheme having both constant-size user secret keys and ciphertexts (i.e. independent of the number of attributes in the scheme, or the policy size). For the first time, we provide a way to use cryptographic accumulators for both key management and encryption process.

ABSTRACT. This paper puts forth a simpler construction for indistinguishability obfuscation (iO) for general circuits. The scheme is concocted from four main ingredients: (1) selectively indistinguishably-secure functional encryption for general circuits having its encryption procedure in complexity class NC 1 ; (2) universal circuits; (3) puncturable pseudo-random functions having evaluation in NC 1 ; (4) indistinguishably-secure affine-determinant programs, a notion proposed by works in submission that particularizes iO for specific circuit classes and acts as “depleted” obfuscators. The scheme can be used to build iO for all polynomial-sized circuits in a simplified way. Instantiations can be obtained from sub-exponentially secure learning with errors (LWE).