International Association
for Cryptologic Research

Multiparty Private Set Intersection (mPSI), enables $n$ parties, each holding private sets (each of size $m$) to compute the intersection of these private sets, without revealing any other information to each other. While several protocols for this task are known, the only concretely efficient protocol is due to the work of Kolesnikov et al. (KMPRT, CCS 2017), who gave a semi-honest secure protocol with communication complexity $\mathcal{O}(nmt\lambda)$, where $t<n$ is the number of corrupt parties and $\lambda$ is the security parameter. In this work, we make the following contributions: $-$ First, for the natural adversarial setting of semi-honest honest majority (i.e. $t<n/2$), we asymptotically improve upon the above result and provide a concretely efficient protocol with total communication of $\mathcal{O}(nm\lambda)$. $-$ Second, concretely, our protocol has $6(t+2)/5$ times lesser communication than KMPRT and is upto $5\times$ and $6.2\times$ faster than KMPRT in the LAN and WAN setting even for 15 parties. $-$ Finally, we introduce and consider two important variants of mPSI - circuit PSI (that allows the parties to compute a function over the intersection set without revealing the intersection itself) and quorum PSI (that allows $P_1$ to learn all the elements in his/her set that are present in at least $k$ other sets) and provide concretely efficient protocols for these variants.

Let $E_a/ \mathbb{F}_{2}: y^2+xy=x^3+ax^2+1$ be a Koblitz curve. The window $\tau$-adic non-adjacent form (window $\tau$NAF) is currently the standard representation system to perform scalar multiplications on $E_a/ \mathbb{F}_{2^m}$ utilizing the Frobenius map $\tau$. This work focuses on the pre-computation part of scalar multiplication. We first introduce $\mu\bar{\tau}$-operations where $\mu=(-1)^{1-a}$ and $\bar{\tau}$ is the complex conjugate of $\tau$. Efficient formulas of $\mu\bar{\tau}$-operations are then derived and used in a novel pre-computation scheme. Our pre-computation scheme requires $6${\bf M}$+6${\bf S}, $18${\bf M}$+17${\bf S}, $44${\bf M}$+32${\bf S}, and $88${\bf M}$+62${\bf S} ($a=0$) and $6${\bf M}$+6${\bf S}, $19${\bf M}$+17${\bf S}, $46${\bf M}$+32${\bf S}, and $90${\bf M}$+62${\bf S} ($a=1$) for window $\tau$NAF with widths from $4$ to $7$ respectively. It is about two times faster, compared to the state-of-the-art technique of pre-computation in the literature. The impact of our new efficient pre-computation is also reflected by the significant improvement of scalar multiplication. Traditionally, window $\tau$NAF with width at most $6$ is used to achieve the best scalar multiplication. Because of the dramatic cost reduction of the proposed pre-computation, we are able to increase the width for window $\tau$NAF to $7$ for a better scalar multiplication. This indicates that the pre-computation part becomes more important in performing scalar multiplication. With our efficient pre-computation and the new window width, our scalar multiplication runs in at least 85.2\% the time of Kohel's work (Eurocrypt'2017) combining the best previous pre-computation. Our results push the scalar multiplication of Koblitz curves, a very well-studied and long-standing research area, to a significant new stage.

Group signature with verifier-local revocation (VLR-GS) is a special type of revocable group sig- nature which enables a user to sign messages without referring to information regarding revoked users. Although there have been several proposals of VLR-GS schemes since the first scheme proposed by Boneh and Shacham [CCS 2004], all of these schemes only achieve a security notion called selfless anonymity, which is strictly weaker than the de facto standard security notion, full anonymity. Thus, for more than a decade, it has been an open problem whether a fully anonymous VLR-GS scheme can be achieved. In this paper, we give an affirmative answer to this problem. Concretely, we show the construction of a fully anonymous VLR-GS scheme from a digital signature scheme, a key-private public key encryption scheme, and a non-interactive zero-knowledge proof system. Also, we show that backward unlinkability, which ensures that even after a user is revoked, signatures produced by the user before the revocation remain anonymous, can be realized without additional building blocks. Although the size of group public key and signing key depend on the number of time periods, finally, we show that the size of these keys can be reduced by employing an identity-based encryption scheme.

Isomorphism of polynomials with two secrets (IP2S) problem was proposed by Patarin et al. at Eurocrypt 1996 and the problem is to find two secret linear maps filling in the gap between two polynomial maps over a finite field. At PQC 2020, Santoso proposed a problem originated from IP2S, which is called block isomorphism of polynomials with circulant matrices (BIPC) problem. The BIPC problem is obtained by linearizing IP2S and restricting secret linear maps to linear maps represented by circulant matrices. Using the commutativity of products of circulant matrices, Santoso also proposed an El-Gamal-like encryption scheme based on the BIPC problem. In this paper, we give a new security analysis on the El-Gamal-like encryption scheme. In particular, we introduce a new attack (called linear stack attack) which finds an equivalent key of the El-Gamal-like encryption scheme by using the linearity of the BIPC problem. We see that the attack is a polynomial-time algorithm and can break some 128-bit proposed parameters of the El-Gamal-like encryption scheme within 10 hours on a standard PC.

NTRU is regarded as an appealing finalist due to its long history against all known attacks and relatively high efficiency. In the third round of the NIST competition, the submitted NTRU cryptosystem is the merger of NTRU-HPS and NTRU-HRSS. In 2019, Ding et al. have analyzed the case when the public key is reused for the original NTRU scheme. However, NTRU-HRSS selects coefficients in an arbitrary way, instead of fixed-weight sample spaces in the original NTRU and NTRU-HPS. Therefore, their method cannot be applied to NTRU-HRSS. To address this problem, we propose a full key mismatch attack on NTRU-HRSS. Firstly, we find a longest chain which helps us in recovering the following coefficients. Next, the most influential interference factors are eliminated by increasing the weight of targeted coefficients. In this step, we adaptively select the weights according to the feedbacks of the oracle to avoid errors. Finally, experiments show that we succeed in recovering all coefficients of the secret key in NTRU-HRSS with a success rate of $93.6\%$. Furthermore, we illustrate the trade-off among the success rate, average number of queries, and average time. Particularly, we show that when the success rate is 93.6\%, it has the minimum number of queries at the same time.

Stealing trained machine learning (ML) models is a new and growing concern due to the model's development cost. Existing work on ML model extraction either applies a mathematical attack or exploits hardware vulnerabilities such as side-channel leakage. This paper shows a new style of attack, for the first time, on ML models running on embedded devices by abusing the scan-chain infrastructure. We illustrate that having course-grained scan-chain access to non-linear layer outputs is sufficient to steal ML models. To that end, we propose a novel small-signal analysis inspired attack that applies small perturbations into the input signals, identifies the quiescent operating points and, selectively activates certain neurons. We then couple this with a Linear Constraint Satisfaction based approach to efficiently extract model parameters such as weights and biases. We conduct our attack on neural network inference topologies defined in earlier works, and we automate our attack. The results show that our attack outperforms mathematical model extraction proposed in CRYPTO 2020, USENIX 2020, and ICML 2020 by an increase in accuracy of 2^20.7x, 2^50.7x, and 2^33.9x, respectively, and a reduction in queries by 2^6.5x, 2^4.6x, and 2^14.2x, respectively.

Blockchains can guarantee fairness during the exchange of digital goods such that in a two-party exchange no one is defrauded by a malicious opponent. While several notions of fairness have been discussed in the literature, they all ignore that damage cannot only be incurred by the malicious failure of the exchange, but also by an unfair allocation of transaction costs. To address this issue we: 1. define the novel concept of cost fairness, which 2. builds on the notion of maximum cost matrices that formalize transaction costs in different combinations of benevolent and malicious behavior. 3. We show how limited notions of cost fairness can be achieved by modifying an existing exchange protocol or using a container protocol. In particular, we also provide 4. a tool that let us predict the maximum cost matrix for a specific protocol execution and, thus, gives trade exchange parties the possibility to weigh not only the value of transaction of exchanged goods but also the associated transaction costs.

Zero-knowledge succinct non-interactive arguments (zk-SNARKs) rely on knowledge assumptions for their security. Meanwhile, as the complexity and scale of cryptographic systems continues to grow, the composition of secure protocols is of vital importance. The current gold standards of composable security, the Universal Composability and Constructive Cryptography frameworks cannot capture knowledge assumptions, as their core proofs of composition prohibit white-box extraction. In this paper, we present a formal model allowing the composition of knowledge assumptions. Despite showing impossibility for the general case, we demonstrate the model’s usefulness when limiting knowledge assumptions to few instances of protocols at a time. We finish by providing the first instance of a simultaneously succinct and composable zk-SNARK, by using existing results within our framework.

Non-malleable codes protect communications against adversarial tampering of data, which can be seen as a relaxation of error-correcting codes and error-detecting codes. Recently, Rasmussen and Sahai (ITC2020) explicitly constructed non-malleable codes in the split-state model using expander graphs. In this paper we extend their construction by means of bipartite expander graphs. The resulted codes can have flexible parameters and reduce the encoding space cost in comparison with the explicit codes by Rasmussen and Sahai.

Function Secret Sharing (FSS), introduced by Boyle, Gilboa and Ishai [BGI15], extends the classical notion of secret-sharing a {\em value} to secret sharing a {\em function}. Namely, for a secret function $f$ (from a class $\cal F$), FSS provides a sharing of $f$ whereby {\em succinct} shares (``keys'') are distributed to a set of parties, so that later the parties can non-interactively compute an additive sharing of $f(x)$, for any input $x$ in the domain of $f$. Previous work on FSS concentrated mostly on the two-party case, where highly efficient schemes are obtained for some simple, yet extremely useful, classes $\cal F$ (in particular, FSS for the class of point functions, a task referred to as DPF~--~Distributed Point Functions[GI14,BGI15]).

In this paper, we concentrate on the multi-party case, with $p\ge 3$ parties and $t$-security ($1\le t<p$). First, we introduce the notion of {\em CNF-DPF} (or, more generally, {\em CNF-FSS}), where the scheme uses the CNF version of secret sharing (rather than additive sharing) to share each value $f(x)$. We then demonstrate the utility of CNF-DPF by providing several applications. Our main results are:

(i) We show how CNF-DPF can be used to achieve substantial asymptotic improvement in communication complexity when using it as a building block for constructing {\em standard} $(t,p)$-DPF protocols that tolerate $t>1$ (semi-honest) corruptions. For example, we build a 2-out-of-5 secure (standard) DPF scheme of communication complexity $O(N^{1/4})$, where $N$ is the domain size of $f$ (compared with the current best-known of $O(N^{1/2})$ for $(2,5)$-DPF). More generally, with $p>dt$ parties, we give a $(t,p)$-DPF whose complexity grows as $O(N^{1/2d})$ (rather than $O(\sqrt{N})$ that follows from the $(p-1,p)$-DPF scheme of \cite{BGI15}).\footnote{We ignore here terms that depend on the number of parties, $p$, the security parameter, etc. See precise statements in the main body of the paper below.} (ii) We construct a 1-out-of-3 secure CNF-DPF scheme, in which each party holds two of the three keys, with poly-logarithmic communication complexity. These results have some immediate implications to scenarios where (multi-server) DPF was shown to be applicable. For example, we show how to use such a scheme to obtain asymptotic improvement ($O(\log^2N)$ versus $O(\sqrt{N})$) in communication complexity over currently best-known black-box results for the 3-party protocol of~\cite{BKKO20}.

We initiate the study of verifiable capacity-bound function (VCBF). The main VCBF property imposes a lower bound on the number of bits read from memory during evaluation (referred to as minimum capacity). No adversary, even with unbounded resources, should produce an output without spending this minimum memory capacity. Moreover, a VCBF allows for an efficient public verification process: Given a proof-of-correctness, checking the validity of the output takes significantly fewer memory resources, sublinear in the target minimum capacity. Finally, it achieves soundness, i.e., no computationally bounded adversary can produce a proof that passes verification for a false output. With these properties, we believe a VCBF can be viewed as a “space” analog of a verifiable delay function. We then propose the first VCBF construction relying on evaluating a degree-$d$ polynomial $f$ from $\mathbb{F}_p[x]$ at a random point. We leverage ideas from Kolmogorov complexity to prove that sampling $f$ from a large set (i.e., for high-enough $d$) ensures that evaluation must entail reading a number of bits proportional to the size of its coefficients. Moreover, our construction benefits from existing verifiable polynomial evaluation schemes to realize our efficient verification requirements. In practice, for a field of order $O(2^\lambda)$ our VCBF achieves $O((d + 1)\lambda)$ minimum capacity, whereas verification requires just $O(\lambda)$.

Adaptor signature is becoming an increasingly important tool in solving the scalability and interoperability issues of blockchain applications. It has many useful properties. Firstly, it can reduce on-chain cost when it is used in off-chain authenticated communication. Secondly, it can increase the fungibility of transactions using it as the signature. Thirdly, it can help circumvent the limitation of the blockchain's scripting language.

In this paper, we propose the first generic construction of adaptor signatures which is compatible with different signature schemes. It can be used as a general framework to combine with different privacy-preserving cryptosystems. Finally, we propose blind adaptor signature and linkable ring adaptor signature. We believe they are of independent interests.

We construct more efficient cryptosystems with provable security against adaptive attacks, based on simple and natural hardness assumptions in the standard model. Concretely, we describe:

- An adaptively-secure variant of the efficient, selectively-secure LWE-based identity-based encryption (IBE) scheme of Agrawal, Boneh, and Boyen (EUROCRYPT 2010). In comparison to the previously most efficient such scheme by Yamada (CRYPTO 2017) we achieve smaller lattice parameters and shorter public keys of size $\mathcal{O}(\log \lambda)$, where $\lambda$ is the security parameter.

- Adaptively-secure variants of two efficient selectively-secure pairing-based IBEs of Boneh and Boyen (EUROCRYPT 2004). One is based on the DBDH assumption, has the same ciphertext size as the corresponding BB04 scheme, and achieves full adaptive security with public parameters of size only $\mathcal{O}(\log \lambda)$. The other is based on a $q$-type assumption and has public key size $\mathcal{O}(\lambda)$, but a ciphertext is only a single group element and the security reduction is quadratically tighter than the corresponding scheme by Jager and Kurek (ASIACRYPT 2018).

- A very efficient adaptively-secure verifiable random function where proofs, public keys, and secret keys have size $\mathcal{O}(\log \lambda)$.

As a technical contribution we introduce blockwise partitioning, which leverages the assumption that a cryptographic hash function is weak near-collision resistant to prove full adaptive security of cryptosystems.

Despite significant recent progress toward making multi-party computation (MPC) practical, no existing MPC library offers complete robustness---meaning guaranteed output delivery, including in the offline phase---in a network that even has intermittent delays. Importantly, several theoretical MPC constructions already ensure robustness in this setting. We observe that the key reason for this gap between theory and practice is the absence of efficient verifiable/complete secret sharing (VSS/CSS) constructions; existing CSS protocols either require a) challenging broadcast channels in practice or b) introducing computation and communication overhead that is at least quadratic in the number of players.

This work presents hbACSS, a suite of optimal-resilience asynchronous complete secret sharing protocols that are (quasi)linear in both computation and communication overhead. Towards developing hbACSS, we develop hbPolyCommit, an efficient polynomial commitment scheme that is (quasi)linear (in the polynomial degree) in terms of computation and communication overhead without requiring a trusted setup. We implement our hbACSS protocols, extensively analyze their practicality, and observe that our protocols scale well with an increasing number of parties. In particular, we use hbACSS to generate MPC input masks: a useful primitive which had previously only been calculated nonrobustly in practice.

In the model of Perfectly Secure Message Transmission (PSMT), a sender Alice is connected to a receiver Bob via $n$ parallel two-way channels, and Alice holds an $\ell$ symbol secret that she wishes to communicate to Bob. There is an unbounded adversary Eve that controls $t$ of the channels, where $n=2t+1$. Eve is able to corrupt any symbol sent through the channels she controls, and furthermore may attempt to infer Alice's secret by observing the symbols sent through the channels she controls. The transmission is required to be (a) reliable, i.e., Bob must always be able to recover Alice's secret, regardless of Eve's corruptions; and (b) private, i.e., Eve may not learn anything about the Alice's secret. We focus on the two-round model, where Bob is permitted to first transmit to Alice, and then Alice responds to Bob.

In this work we provide tight upper and lower bounds for the PSMT model when the length of the communicated secret $\ell$ is asymptotically large. Specifically, we first construct a protocol that allows Alice to communicate an $\ell$ symbol secret to Bob by transmitting at most $2(1+o(1))n\ell$ symbols. We complement this with a lower bound showing that $2n\ell$ symbols are necessary for Alice to privately and reliably communicate her secret. Thus, we completely determine the optimal transmission rate in this regime, even up to the leading constant.

ASCON is one of the elegant designs of authenticated encryption with associated data (AEAD) that was selected as the first choice for lightweight ap- plications in the CAESAR competition, which also has been submitted to NIST lightweight cryptography standardization. ASCON has been in the literature for a while, however, there has been no successful AEAD which is secure at the same time lighter than ASCON. In this article, we have overcome the challenge of constructing a permutation that is lighter than the ASCON permutation while ensuring a similar performance, and based on which we achieve a more lightweight AEAD which we call Sycon. Extensive security analysis of Sycon confirms that it provides the same level of security as that of ASCON. Our hardware implementation result shows that the Sycon permutation has 5.35% reduced area, compared to the ASCON permutation. This leads to a remarkable area reduction for Sycon AEAD which is about 14.95% as compared to ASCON AEAD. We regard the Sycon as a new milestone as it is the lightest among all the AEADs belonging to the ASCON family.

EasyCrypt is a proof assistant used for verifying computational security proofs of cryptographic constructions. It has been applied to several prominent examples, including the SHA3 standard and a critical component of AWS Key Management Services. In this paper we enhance the EasyCrypt proof assistant to reason about computational complexity of adversaries. The key technical tool is a Hoare logic for reasoning about computational complexity (execution time and oracle calls) of adversarial computations. Our Hoare logic is built on top of the module system used by EasyCrypt for modeling adversaries. We prove that our logic is sound w.r.t. the semantics of EasyCrypt programs --- we also provide full semantics for the EasyCrypt module system, which was previously lacking. We showcase (for the first time in EasyCrypt and in other computer-aided cryptographic tools) how our approach can express precise relationships between the probability of adversarial success and their execution time. In particular, we can quantify existentially over adversaries in a complexity class, and express general composition statements in simulation-based frameworks. Moreover, such statements can be composed to derive standard concrete security bounds for cryptographic constructions whose security is proved in a modular way. As a main benefit of our approach, we revisit security proofs of some well-known cryptographic constructions and we present a new formalization of Universal Composability (UC).

FrodoKEM is a lattice-based key encapsulation mechanism, currently a semi-finalist in NIST’s post-quantum standardization effort. A condition for these candidates is to use NIST standards for sources of randomness (i.e., seed-expanding), and as such most candidates utilize SHAKE, an XOF defined in the SHA-3 standard. However, for many of the candidates, this module is a significant implementation bottleneck. Trivium is a lightweight, ISO standard stream cipher which performs well in hardware and has been used in previous hardware designs for lattice-based cryptography. This research proposes optimized designs for FrodoKEM, concentrating on high throughput by parallelising the matrix multiplication operations within the cryptographic scheme. This process is eased by the use of Trivium due to its higher throughput and lower area consumption. The parallelisations proposed also complement the addition of first-order masking to the decapsulation module. Overall, we significantly increase the throughput of FrodoKEM; for encapsulation we see a 16x speed-up, achieving 825 operations per second, and for decapsulation we see a 14x speed-up, achieving 763 operations per second, compared to the previous state-of-the-art, whilst also maintaining a similar FPGA area footprint of less than 2000 slices.

We present Vortex a new family of one way hash functions that can produce message digests of 224, 256, 384 and 512 bits. The main idea behind the design of these hash functions is that we use well known algorithms that can support very fast diffusion in a small number of steps. We also balance the cryptographic strength that comes from iterating block cipher rounds with SBox substitution and diffusion (like Whirlpool) against the need to have a lightweight implementation with as small number of rounds as possible. We use a variable number of Rijndael rounds with a stronger key schedule. Our goal is not to protect a secret symmetric key but to support perfect mixing of the bits of the input into the hash value. Rijndael rounds are followed by our variant of Galois Field multiplication. This achieves cross-mixing between 128-bit or 256-bit sets. Our hash function uses the Enveloped Merkle-Damgard construction to support properties such as collision resistance, first and second pre-image resistance, pseudorandom oracle preservation and pseudorandom function preservation. We provide analytical results that demonstrate that the number of queries required for finding a collision with probability greater or equal to 0.5 in an ideal block cipher approximation of Vortex 256 is at least 1.18x2^122.55 if the attacker uses randomly selected message words. We also provide experimental results that indicate that the compression function of Vortex is not inferior to that of the SHA family regarding its capability to preserve the pseudorandom oracle property. We list a number of well known attacks and discuss how the Vortex design addresses them. The main strength of the Vortex design is that this hash function can demonstrate an expected performance of 2.2-2.5 cycles per byte in future processors with instruction set support for Rijndael rounds and carry-less multiplication. We provide arguments why we believe this is a trend in the industry. We also discuss how optimized assembly code can be written that demonstrates such performance.

Vortex is a new family of one-way hash functions which has been submitted to the NIST SHA-3 competition. Its design is based on using the Rijndael block cipher round as a building block, and using a multiplication-based merging function to support fast mixing in a small number of steps. Vortex is designed to be a fast hash function, when running on a processor that has AES acceleration and has a proven collision resistance [2]. Several attacks on Vortex have been recently published [3, 4, 5, 6] exploiting some structural properties of its design, as presented in the version submitted to the SHA-3 competition. These are mainly ¯rst and second preimage attacks with time complexity below the ideal, as well as attempts to distinguish the Vortex output from random. In this paper we study the root-cause of the attacks and propose few amendments to the Vortex structure, which eliminate the attacks without a®ecting its collision resistance and performance.