IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
11 November 2022
Gongxian Zeng, Junzuo Lai, Zhengan Huang, Yu Wang, Zhiming Zheng
At CRYPTO 1994, Cramer, Damg{\aa}rd and Schoenmakers proposed a general method to construct proofs of knowledge (PoKs), especially for $k$-out-of-$n$ partial knowledge, of which relations can be expressed in disjunctive normal form (DNF). Since then, proofs of $k$-out-of-$n$ partial knowledge have attracted much attention and some efficient constructions have been proposed. However, many practical scenarios require efficient PoK protocols for partial knowledge in other forms.
In this paper, we mainly focus on PoK protocols for $k$-conjunctive normal form ($k$-CNF) relations, which have $n$ statements and can be expressed as follows: (i) $k$ statements constitute a clause via ``OR'' operations, and (ii) the relation consists of multiple clauses via ``AND'' operations. We propose an alternative Sigma protocol (called DAG-$\Sigma$ protocol) for $k$-CNF relations (in the discrete logarithm setting), by converting these relations to directed acyclic graphs (DAGs). Our DAG-$\Sigma$ protocol achieves less communication cost and smaller computational overhead compared with Cramer et al.'s general method.
In this paper, we mainly focus on PoK protocols for $k$-conjunctive normal form ($k$-CNF) relations, which have $n$ statements and can be expressed as follows: (i) $k$ statements constitute a clause via ``OR'' operations, and (ii) the relation consists of multiple clauses via ``AND'' operations. We propose an alternative Sigma protocol (called DAG-$\Sigma$ protocol) for $k$-CNF relations (in the discrete logarithm setting), by converting these relations to directed acyclic graphs (DAGs). Our DAG-$\Sigma$ protocol achieves less communication cost and smaller computational overhead compared with Cramer et al.'s general method.
Gennaro Avitabile, Vincenzo Botta, Dario Fiore
Threshold ring signatures are digital signatures that allow $t$ parties to sign a message while hiding their identity in a larger set of $n$ users called ''ring''.
Recently, Aranha et al. [PKC 2022] introduced the notion of \emph{extendable} threshold ring signatures (ETRS).
ETRS allow one to update, in a non-interactive manner, a threshold ring signature on a certain message so that the updated signature has a greater threshold, and/or an augmented set of potential signers.
An application of this primitive is anonymous count me in.
A first signer creates a ring signature with a sufficiently large ring announcing a proposition in the signed message. After such cause becomes \emph{public}, other parties can anonymously decide to support that proposal by producing an updated signature. Crucially, such applications rely on partial signatures being posted on a \emph{publicly accessible} bulletin board since users may not know/trust each other.
In this paper, we first point out that even if anonymous count me in was suggested as an application of ETRS, the anonymity notion proposed in the previous work is insufficient in many application scenarios. Indeed, the existing notion guarantees anonymity only against adversaries who just see the last signature, and are not allowed to access the ''full evolution" of an ETRS. This is in stark contrast with applications where partial signatures are posted in a public bulletin board. We therefore propose stronger anonymity definitions and construct a new ETRS that satisfies such definitions. Interestingly, while satisfying stronger anonymity properties, our ETRS asymptotically improves on the two ETRS presented in prior work [PKC 2022] in terms of both time complexity and signature size. Our ETRS relies on extendable non-interactive witness-indistinguishable proof of knowledge (ENIWI PoK), a novel technical tool that we formalize and construct, and that may be of independent interest. We build our constructions from pairing groups under the SXDH assumption.
In this paper, we first point out that even if anonymous count me in was suggested as an application of ETRS, the anonymity notion proposed in the previous work is insufficient in many application scenarios. Indeed, the existing notion guarantees anonymity only against adversaries who just see the last signature, and are not allowed to access the ''full evolution" of an ETRS. This is in stark contrast with applications where partial signatures are posted in a public bulletin board. We therefore propose stronger anonymity definitions and construct a new ETRS that satisfies such definitions. Interestingly, while satisfying stronger anonymity properties, our ETRS asymptotically improves on the two ETRS presented in prior work [PKC 2022] in terms of both time complexity and signature size. Our ETRS relies on extendable non-interactive witness-indistinguishable proof of knowledge (ENIWI PoK), a novel technical tool that we formalize and construct, and that may be of independent interest. We build our constructions from pairing groups under the SXDH assumption.
Orr Dunkelman, Shibam Ghosh, Eran Lambooij
TinyJAMBU is one of the finalists in the NIST lightweight
standardization competition. This paper presents full round practical
zero-sum distinguishers on the keyed permutation used in TinyJAMBU.
We propose a full round zero-sum distinguisher on the 128- and 192-bit
key variants and a reduced round zero-sum distinguisher for the 256-bit
key variant in the known-key settings. Our best known-key distinguisher
works with $2^{16}$ data/time complexity on the full 128-bit version and with
$2^{23}$ data/time complexity on the full 192-bit version. For the 256-bit ver-
sion, we can distinguish 1152 rounds (out of 1280 rounds) in the known-
key settings. In addition, we present the best zero-sum distinguishers
in the secret-key settings: with complexity $2^{23}$ we can distinguish 544
rounds in the forward direction or 576 rounds in the backward direction.
For finding the zero-sum distinguisher, we bound the algebraic degree of
the TinyJAMBU permutation using the monomial prediction technique
proposed by Hu et al. at ASIACRYPT 2020. We model the monomial
prediction rule on TinyJAMBU in MILP and find upper bounds on the
degree by computing the parity of the number of solutions.
10 November 2022
Kaisa Nyberg
Various systematic modifications of vectorial Boolean functions have been used for finding new previously unknown classes of S-boxes with good or even optimal differential uniformity and nonlinearity. Recently, a new method was proposed for modification a component of a bijective vectorial Boolean function by using a linear function. It was shown that the modified function remains bijective under the assumption that the inverse of the function admits a linear structure. A previously known construction of such a modification based on bijective Gold functions in odd dimension is a special case of this type of modification. In this paper, we show that the existence of a linear structure is necessary. Further, we consider replacement of a component of a bijective vectorial Boolean function in the general case. We prove that a permutation on $\mathbb{F}_2^n$ remains bijective if and only if the replacement is done by composing the permutation with an unbalanced Feistel transformation where the round function is any Boolean function on $\mathbb{F}_2^{n-1}$.
Arantxa Zapico, Ariel Gabizon, Dmitry Khovratovich, Mary Maller, Carla Ràfols
We present Baloo, the first protocol for lookup tables where the prover work is linear on the amount of lookups and independent of the size of the table. Baloo is built over the lookup arguments of Caulk and Caulk+, and the framework for linear relations of Rafols and Zapico.
Our protocol supports commit-and-prove expansions: the prover selects the subtable containing the elements used in the lookup, that is unknown to the verifier, commits to it and later prove relation with the committed element. This feature makes Baloo especially suitable for prover input-ouput relations on hash functions, and in particular to instantiate the Ethereum Virtual Machine (EVM).
Pranav Verma, Anish Mathuria, Sourish Dasgupta
The existing works on privacy-preserving recommender systems based on homomorphic encryption do not filter top-k most relevant items on the server side. As a result, sending the encrypted rating vector for all items to the user retrieving the top-k items is necessary. This incurs significant computation and communication costs on the user side.
In this work, we employ private sorting at the server to reduce the user-side overheads. In private sorting, the values and corresponding positions of elements must remain private. We use an existing private sorting protocol by Foteini and Olga and tailor it to the privacy-preserving top-k recommendation applications. We enhance it to use secure bit decomposition in the private comparison routine of the protocol. This leads to a notable reduction in cost overheads of users as well as the servers, especially at the keyserver where the computation cost is reduced to half. The dataserver does not have to perform costly encryption and decryption operations. It performs computationally less expensive modular exponentiation operations. Since the private comparison operation contributes significantly to the overall cost overhead, making it efficient enhances the sorting protocol’s performance. Our security analysis concludes that the proposed scheme is as secure as the original protocol.
In this work, we employ private sorting at the server to reduce the user-side overheads. In private sorting, the values and corresponding positions of elements must remain private. We use an existing private sorting protocol by Foteini and Olga and tailor it to the privacy-preserving top-k recommendation applications. We enhance it to use secure bit decomposition in the private comparison routine of the protocol. This leads to a notable reduction in cost overheads of users as well as the servers, especially at the keyserver where the computation cost is reduced to half. The dataserver does not have to perform costly encryption and decryption operations. It performs computationally less expensive modular exponentiation operations. Since the private comparison operation contributes significantly to the overall cost overhead, making it efficient enhances the sorting protocol’s performance. Our security analysis concludes that the proposed scheme is as secure as the original protocol.
Bhuvnesh Chaturvedi, Anirban Chakraborty, Ayantika Chatterjee, Debdeep Mukhopadhyay
Fully Homomorphic Encryption (FHE) promises to
secure our data on the untrusted cloud, while allowing arbitrary
computations. Present research shows that while there are pos-
sibilities of side channel exploitations on the client side targeting
the encryption or key-generation processes, the encrypted data on
the cloud is secure against practical attacks. The current paper
shows that it is possible for adversaries to inject perturbations in
the ciphertexts stored in the cloud to result in decryption errors.
Most importantly, we highlight that when the client reports of
such aberrations to the cloud service provider the complete
secret key can be extracted in few attempts. Technically, this
implies a break of the IND-CVA (Indistinguishability against
Ciphertext Verification Attacks) security of the FHE schemes.
The underlying core methodology of the attack is to exploit
the dependence of the error in the ciphertexts to the timing
of homomorphic computations. These correlations can lead to
timing templates which when used in conjunction with the error-
induced decryption errors as reported by the client can lead to
an accurate estimation of the ciphertext errors. As the security
of the underlying Learning with Errors (LWE) collapse with the
leakage of the errors, the adversary is capable of ascertaining the
secret keys. We demonstrate this attack on two well-known FHE
libraries, namely FHEW and TFHE, where we need 7, 23 and
28 queries to the client for each error recovery respectively. We
mounted full key recovery attack on TFHE (without and with
bootstrapping) and FHEW with key sizes 630 and 500 bits with
1260, 703 and 1003 correct errors and 31948, 21273 and 9073
client queries respectively.
Jack Cable, Andrés Fábrega, Sunoo Park, Michael A. Specter
Voter registration is an essential part of almost any election process, and its security is a critical component of election security. Yet, despite notable compromises of voter registration systems, relatively little academic work has been devoted to securing voter registration systems, compared to research on other aspects of election security. In this paper, we present a systematic treatment of voter registration system security. We propose the first rigorous definitional framework for voter registration systems, describing the entities and core functionalities inherent in most voter registration systems, the jurisdictional policies that constrain specific implementations, and key security properties. Our definitions are configurable based on jurisdiction-specific parameters and policies. We provide a template for the structured presentation of detailed jurisdictional policy information, via a series of tables, and illustrate its application with detailed case studies of the voter registration systems of three U.S. states and Panama. Throughout our research, with the aim of realism and practical applicability, we consulted current and former U.S. election officials, civil society, and non-profits in the elections space. We conclude with a list of critical questions regarding voter registration security.
Pranav Jangir, Nishat Koti, Varsha Bhat Kukkala, Arpita Patra, Bhavish Raj Gopal, Somya Sangal
Consider the problem of securely identifying τ -heavy hitters, where given a set of client inputs, the goal is to identify those inputs which are held by at least τ clients in a privacy-preserving manner. Towards this, we design a novel system Vogue, whose key highlight in comparison to prior works, is that it ensures complete privacy and does not leak any information other than the heavy hitters. In doing so, Vogue aims to achieve as efficient a solution as possible. To showcase these efficiency improvements, we benchmark our solution and observe that it requires around 14 minutes to compute the heavy hitters for τ = 900 on 256-bit inputs when considering 400K clients. This is in contrast to the state of the art solution that requires over an hour for the same. In addition to the static input setting described above, Vogue also accounts for streaming inputs and provides a protocol that outperforms the state-of-the-art therein. The efficiency improvements witnessed while computing heavy hitters in both, the static and streaming input settings, are attributed to our new secure stable compaction protocol, whose round complexity is independent of the size of the input array to be compacted
Shany Ben-David, Yael Tauman Kalai, Omer Paneth
A computational PIR scheme allows a client to privately query a database hosted on a single server without downloading the entire database.
We introduce the notion of verifiable PIR (vPIR) where the server can convince the client that the database satisfies certain properties without additional rounds and while keeping the communication sub-linear. For example, the server can prove that the number of rows in the database that satisfy a predicate $P$ is exactly $n$.
We define security by modeling vPIR as an ideal functionality and following the real-ideal paradigm. Starting from a standard PIR scheme, we construct a vPIR scheme for any database property that can be verified by a machine that reads the database once and maintains a bounded size state between rows. We also construct vPIR with public verification based on LWE or on DLIN. The main technical hurdle is to demonstrate a simulator that extracts a long input from an adversary that sends a single short message.
Our vPIR constructions are based on the notion of batch argument for NP. As contribution of independent interest, we show that batch arguments are equivalent to quasi-arguments---a relaxation of SNARKs which is known to imply succinct argument for various sub-classes of NP.
We define security by modeling vPIR as an ideal functionality and following the real-ideal paradigm. Starting from a standard PIR scheme, we construct a vPIR scheme for any database property that can be verified by a machine that reads the database once and maintains a bounded size state between rows. We also construct vPIR with public verification based on LWE or on DLIN. The main technical hurdle is to demonstrate a simulator that extracts a long input from an adversary that sends a single short message.
Our vPIR constructions are based on the notion of batch argument for NP. As contribution of independent interest, we show that batch arguments are equivalent to quasi-arguments---a relaxation of SNARKs which is known to imply succinct argument for various sub-classes of NP.
Tung Chou, Ruben Niederhagen, Edoardo Persichetti, Tovohery Hajatiana Randrianarisoa, Krijn Reijnders, Simona Samardjiska, Monika Trimoska
In this paper, we show how to use the Matrix Code Equivalence (MCE) problem as a new basis to construct signature schemes. This extends previous work on using isomorphism problems for signature schemes, a trend that has recently emerged in post-quantum cryptography. Our new formulation leverages a more general problem and allows for smaller data sizes, achieving competitive performance and great flexibility. Using MCE, we construct a zero-knowledge protocol which we turn into a signature scheme named Matrix Equivalence Digital Signature (MEDS). We provide an initial choice of parameters for MEDS, tailored to NIST's Category 1 security level, yielding public keys as small as 2.7 kB and signatures ranging from 18.8 kB to just around 10 kB, along with a reference implementation in C.
Akinori Hosoyamada
This paper shows how to achieve quantum speed-up for multidimensional (zero correlation) linear and integral distinguishers. To understand post-quantum security of symmetric-key cryptosystems, it is important to study how much quantum speed-up we can obtain for classical cryptanalytic techniques such as differential, linear, and integral cryptanalysis. A previous work by Kaplan et al. already showed a quantum quadratic speed-up for one-dimensional linear distinguishers, but it is unclear how to extend their technique to multidimensional linear distinguishers. To remedy this, we investigate how to speed-up multidimensional linear distinguishers in the quantum setting. Firstly, we observe that there is a close relationship between the subroutine of Simon's algorithm and linear correlations via Fourier transform, and a slightly modified version of Simon's subroutine can be used to speed-up multidimensional linear distinguishers. The modified Simon's subroutine also leads to speed-ups for multidimensional zero correlation and some integral distinguishers. Surprisingly, our technique achieves more-than-quadratic speed-ups for some special types of integral distinguishers. This is because the modified Simon's subroutine can exploit the existence of multiple multidimensional zero correlation linear approximations. Our attacks are the first examples achieving such speed-up on classical cryptanalytic techniques without relying on any algebraic structures such as hidden periods or shifts. The speed-ups for multidimensional (zero correlation) linear distinguishers are at-most-quadratic, and all of our attacks require quantum superposition queries.
Kunming Jiang, Devora Chait-Roth, Zachary DeStefano, Michael Walfish, Thomas Wies
There has been intense interest over the last decade in implementations of _probabilistic proofs_ (IPs, SNARKs, PCPs, and so on): protocols in which an untrusted party proves to a verifier that a given computation was executed properly, possibly in zero knowledge. Nevertheless, implementations still do not scale beyond small computations. A central source of overhead is the _front-end_: translating from the abstract computation to a set of equivalent arithmetic constraints. This paper introduces a general-purpose framework, called Distiller, in which a user translates to constraints not the original computation but an abstracted _specification_ of it. Distiller is the first in this area to perform such transformations in a way that is provably safe. Furthermore, by taking the idea of "encode a check in the constraints" to its literal logical extreme, Distiller exposes many new opportunities for constraint reduction, resulting in cost reductions for benchmark computations of 1.3–50$\times$, and in some cases, better asymptotics.
Dimitrios Sikeridis, Sean Huntley, David Ott, Michael Devetsikiotis
Quantum computing advances threaten the security of today's public key infrastructure, and have led to the pending standardization of alternative, quantum-resistant key encapsulation and digital signature cryptography schemes. Unfortunately, authentication algorithms based on the new post-quantum (PQ) cryptography create significant performance bottlenecks for TLS due to larger certificate chains which introduce additional packets and round-trips. The TLS handshake slowdown will be unacceptable to many applications, and detrimental to the broader adoption of quantum safe cryptography standards. In this paper, we propose a novel framework for Intermediate Certificate Authority (ICA) certificate suppression in TLS that reduces the authentication message size and prevents excessive round-trip delays. Our approach utilizes an approximate membership query (AMQ) data structure (probabilistic filter) to advertise known ICA certs to remote TLS endpoints so that unnecessary ICA certificates are omitted from the TLS handshake exchange. We showcase the extend of the PQ authentication overhead challenge in TLS, and evaluate the feasibility of AMQ filters for ICA suppression in terms of space and computational overhead. Finally, we experimentally evaluate the potential gains form our approach and showcase a $70\%$ reduction in exchanged ICA cert data that translates to 15-50 MB of savings in PQ TLS and for certain Web-based application scenarios.
Sunpreet S. Arora, Saikrishna Badrinarayanan, Srinivasan Raghuraman, Maliheh Shirvanian, Kim Wagner, Gaven Watson
Passwords are difficult to remember, easy to guess and prone to hacking. While there have been several attempts to solve the aforementioned problems commonly associated with passwords, one of the most successful ones to date has been by the Fast Identity Online (FIDO) alliance. FIDO introduced a series of protocols that combine local authentication on a user device with remote validation on relying party servers using public-key cryptography.
One of the fundamental problems of FIDO protocols is complete reliance on a single user device for authentication. More specifically, the private key used for signing relying party challenges can only be stored on a single device. Each FIDO authenticator key is linked uniquely to an account with a relying party service. As a result a lost or stolen user device necessitates creation of new user account, using a new device, with each (previously enrolled) relying party service.
To overcome this limitation, we introduce a dynamic managerless group signature scheme that organizes authenticators into groups. Each authenticator in a group has a unique private key that links it to an account with a relying party, which can sign relying party challenges. The relying party server has a group verification key that can validate challenges signed using the private key of any authenticator in a group. Our approach provides additional redundancy and usability to the FIDO protocol whilst still achieving the security properties expected in the FIDO setting such as unforgeability and unlinkability.
Christos Stefo, Zhuolun Xiang, Lefteris Kokoris-Kogias
Scaling blockchain protocols to perform on par with the expected needs of Web3.0 has been proven to be a challenging task with almost a decade of research. In the forefront of the current solution is the idea of separating the execution of the updates encoded in a block from the ordering of blocks. In order to achieve this, a new class of protocols called rollups has emerged. Rollups have as input a total ordering of valid and invalid transactions and as output a new valid state-transition.
If we study rollups from a distributed computing perspective, we uncover that rollups take as input the output of a Byzantine Atomic Broadcast (BAB) protocol and convert it to a State Machine Replication (SMR) protocol. BAB and SMR, however, are considered equivalent as far as distributed computing is concerned and a solution to one can easily be retrofitted to solve the other simply by adding/removing an execution step before the validation of the input.
This ``easy'' step of retrofitting an atomic broadcast solution to implement an SMR has, however, been overlooked in practice. In this paper, we formalize the problem and show that after BAB is solved, traditional impossibility results for consensus no longer apply towards an SMR. Leveraging this we propose a distributed execution protocol that allows reduced execution and storage cost per executor ($O(\frac{log^2n}{n})$) without relaxing the network assumptions of the underlying BAB protocol and providing censorship-resistance. Finally, we propose efficient non-interactive light client constructions that leverage our efficient execution protocols and do not require any synchrony assumptions or expensive ZK-proofs.
If we study rollups from a distributed computing perspective, we uncover that rollups take as input the output of a Byzantine Atomic Broadcast (BAB) protocol and convert it to a State Machine Replication (SMR) protocol. BAB and SMR, however, are considered equivalent as far as distributed computing is concerned and a solution to one can easily be retrofitted to solve the other simply by adding/removing an execution step before the validation of the input.
This ``easy'' step of retrofitting an atomic broadcast solution to implement an SMR has, however, been overlooked in practice. In this paper, we formalize the problem and show that after BAB is solved, traditional impossibility results for consensus no longer apply towards an SMR. Leveraging this we propose a distributed execution protocol that allows reduced execution and storage cost per executor ($O(\frac{log^2n}{n})$) without relaxing the network assumptions of the underlying BAB protocol and providing censorship-resistance. Finally, we propose efficient non-interactive light client constructions that leverage our efficient execution protocols and do not require any synchrony assumptions or expensive ZK-proofs.
Giuseppe Persiano, Kevin Yeo
In recent years, there has been significant work in studying data structures that provide privacy for the operations that are executed. These primitives aim to guarantee that observable access patterns to physical memory do not reveal substantial information about the queries and updates executed on the data structure. Multiple recent works, including Larsen and Nielsen [Crypto'18], Persiano and Yeo [Eurocrypt'19], Hubáček et al. [TCC'19] and Komargodski and Lin [Crypto'21], have shown that logarithmic overhead is required to support even basic RAM (array) operations for various privacy notions including obliviousness and differential privacy as well as different choices of sizes for RAM blocks $b$ and memory cells $\omega$.
We continue along this line of work and present the first logarithmic lower bounds for differentially private RAMs (DPRAMs) that apply regardless of the sizes of blocks $b$ and cells $\omega$. This is the first logarithmic lower bounds for DPRAMs when blocks are significantly smaller than cells, that is $b \ll \omega$. Furthermore, we present new logarithmic lower bounds for differentially private variants of classical data structure problems including sets, predecessor (successor) and disjoint sets (union-find) for which sub-logarithmic plaintext constructions are known. All our lower bounds extend to the multiple non-colluding servers setting.
We also address an unfortunate issue with this rich line of work where the lower bound techniques are difficult to use and require customization for each new result. To make the techniques more accessible, we generalize our proofs into a framework that reduces proving logarithmic lower bounds to showing that a specific problem satisfies two simple, minimal conditions. We show our framework is easy-to-use as all the lower bounds in our paper utilize the framework and hope our framework will spur more usage of these lower bound techniques.
We continue along this line of work and present the first logarithmic lower bounds for differentially private RAMs (DPRAMs) that apply regardless of the sizes of blocks $b$ and cells $\omega$. This is the first logarithmic lower bounds for DPRAMs when blocks are significantly smaller than cells, that is $b \ll \omega$. Furthermore, we present new logarithmic lower bounds for differentially private variants of classical data structure problems including sets, predecessor (successor) and disjoint sets (union-find) for which sub-logarithmic plaintext constructions are known. All our lower bounds extend to the multiple non-colluding servers setting.
We also address an unfortunate issue with this rich line of work where the lower bound techniques are difficult to use and require customization for each new result. To make the techniques more accessible, we generalize our proofs into a framework that reduces proving logarithmic lower bounds to showing that a specific problem satisfies two simple, minimal conditions. We show our framework is easy-to-use as all the lower bounds in our paper utilize the framework and hope our framework will spur more usage of these lower bound techniques.
Siwei Sun, Tianyu Liu, Zhi Guan, Yifei He, Jiwu Jing, Lei Hu, Zhenfeng Zhang, Hailun Yan
We instantiate the hash-based post-quantum stateful signature schemes XMSS and its multi-tree version described in RFC 8391 and NIST SP 800-208 with SM3, and report on the results of the preliminary performance test.
08 November 2022
This is a reminder that the 2022 IACR Election is open. Last day to vote is Nov. 15th.
More details can be found here: https://www.iacr.org/elections/2022/candidates.php
More details can be found here: https://www.iacr.org/elections/2022/candidates.php
Emiliano De Cristofaro, Paolo Gasti, Gene Tsudik
In many everyday scenarios, sensitive information must be shared between parties without complete mutual trust. Private set operations are particularly useful to enable sharing information with privacy, as they allow two or more parties to jointly compute operations on their sets (e.g., intersection, union, etc.), such that only the minimum required amount of information is disclosed. In the last few years, the research community has proposed a number of secure and efficient techniques for Private Set Intersection (PSI), however, somewhat less explored is the problem of computing the magnitude, rather than the contents, of the intersection - we denote this problem as Private Set Intersection Cardinality (PSI-CA).
This paper explores a few PSI-CA variations and constructs several protocols that are more efficient than the state-of-the-art.