International Association
for Cryptologic Research

Private set intersection (PSI) protocols allow a set of mutually distrustful parties, each holding a private set of items, to compute the intersection over all their sets, such that no other information is revealed. PSI has a wide variety of applications including online advertising (e.g., efficacy computation), security (e.g., botnet detection, intrusion detection), proximity testing (e.g., COVID-19 contact tracing), and more. PSI is a rapidly developing area and there exist many highly efficient protocols. However, almost all of these protocols are for the case of two parties or for semi-honest security. In particular, prior to our work, there has been no concretely efficient, maliciously secure multiparty PSI protocol.

We present PSImple, the first concretely efficient maliciously-secure multiparty PSI protocol. Our protocol is based on garbled Bloom filters, extending the 2-party PSI protocol of Rindal and Rosulek (Eurocrypt 2017) and the semi-honestly secure multiparty protocol of Inbar, Omri, and Pinkas (SCN 2018).

To demonstrate the practicality of the PSImple protocol, we implemented our protocol and ran experiments with on up to 32 parties and $2^{18}$ inputs. We incorporated several optimizations into our protocol, and compared our protocol with the 2-party protocol of Rindal and Rosulek and with the semi-honest protocol of Inbar et al.

Finally, we also revisit the parameters used in previous maliciously secure PSI works based on garbled Bloom filters. Using a more careful analysis, we show that the size of the garbled Bloom filters and the required number of oblivious transfers can be significantly reduced, often by more than 20%. These improved parameters can be used both in our protocol and in previous maliciously secure PSI protocols based on garbled Bloom filters.

We provide a modified version of the Ligero sublinear zero knowledge proof system for arithmetic circuits provided by Ames et. al. (CCS ‘17). Our modification "BooLigero" tailors Ligero for use in Boolean circuits to achieve a significant improvement in proof size. Although the original Ligero system could be used for Boolean circuits, Ligero generally requires allocating an entire field element to represent a single bit on a wire in a Boolean circuit. In contrast, our system performs operations over words of bits, allowing a proof size savings of between O(log(|F|)^1/4) and O(log(|F|)^1/2) compared to Ligero, where F is the field that leads to the optimal proof size in original Ligero. We achieve improvements in proof size of approximately 1.1-1.6x for SHA-2 and 1.7-2.8x for SHA-3. In addition to checking constraints of standard Boolean operations such as AND, XOR, and NOT over words, BooLigero also supports several other constraints such as multiplication in GF(2^w), bit masking, bit rearrangement within and across words, and bitwise outer product. Like Ligero, construction requires no trusted setup and no computational assumptions, which is ideal for blockchain applications. It is plausibly post-quantum secure in the standard model. Furthermore, it is public-coin, perfect honest-verifier zero knowledge, and can be made non-interactive in the random oracle model using the Fiat-Shamir transform.

We present a secure multiparty computation (MPC) protocol based on garbled circuits which is both actively secure and supports the free-XOR technique, and which has communication complexity $O(n)$ per party. This improves on a protocol of Ben-Efraim, Lindell and Omri which only achieved passive security, without support for free-XOR. Our construction is based on a new variant of LPN-based encryption, but has the drawback of requiring a rather expensive garbling phase. To address this issue we present a second protocol that assumes at least $n/c$ of the parties are honest (for an arbitrary fixed value $c$). This second protocol allows for a significantly lighter preprocessing, at the cost of a small sacrifice in online efficiency. We demonstrate the practicality of our evaluation phase with a implementation.

Secure comparison has been a fundamental challenge in privacy-preserving computation, since its inception as the Yao's millionaires' problem (FOCS 1982). In this work, we present a novel construction for general n-party private comparison, secure against an active adversary, in the dishonest majority setting. For the case of comparisons over fields, our protocol is more efficient than the best prior work (edaBits: Crypto 2020), with ~1.5x better throughput in most adversarial settings, over 2.3x better throughput in particular in the passive, honest majority setting, and lower communication. Our comparisons crucially eliminate the need for bounded inputs as well as the need for statistical security that prior works require. An important consequence of removing this "slack" (a gap between the bit-length of the input and the MPC representation) is that multi-party computation (MPC) protocols can be run in a field of smaller size, reducing the overhead incurred by privacy-preserving computations. We achieve this novel construction using the commutative nature of addition over rings and fields. This makes the protocol both simple to implement and highly efficient and we provide an implementation in MP-SPDZ (CCS 2020).

Asynchronous verifiable secret sharing (AVSS) protocols protect a secret that is distributed among N parties. Dual-threshold AVSS protocols guarantee consensus in the presence of T Byzantine failures and privacy if fewer than P parties attempt to reconstruct the secret. In this work, we construct a dual-threshold AVSS protocol that is optimal along several dimensions. First, it is a high-threshold AVSS scheme, meaning that it is a dual-threshold AVSS with optimal parameters T < N/3 and P < 2N/3. Second, it has O(N^2) message complexity, and for large secrets it achieves the optimal O(N) communication overhead, without the need for a public key infrastructure or trusted setup. While these properties have been achieved individually before, to our knowledge this is the first protocol that is achieves all of the above simultaneously. The core component of our construction is a high-threshold AVSS scheme for small secrets based on polynomial commitments that achieves O(N^2 log(N)) communication overhead, as compared to prior schemes that require O(N^3) overhead with T<N/4 Byzantine failures or O(N^4) overhead for the recent high-threshold protocol of Kokoris-Kogias et al (CCS 2020). Using standard amortization techniques based on erasure coding, we can reduce the communication complexity to O(N*|F|) for a large secret F.

In this paper, we introduce FPPW, a new payment channel with watchtower scheme for Bitcoin. This new scheme provides fairness w.r.t. all channel participants including both channel parties and the watchtower. It means that the funds of any honest channel participant are safe even assuming that other two channel participants are corrupted and/or collude with each other. Furthermore, the watchtower in FPPW learns no information about the off-chain transactions and hence the channel balance privacy is preserved. As a byproduct, we also define the coverage of a watchtower scheme, that is the total capacity of channels that a watchtower can cover on a scale of 0 to 1, and show that FPPW's coverage is higher than those of PISA and Cerberus. The scheme can be implemented without any update in Bitcoin script.

We offer a public key exchange protocol based on a semidirect product of two cyclic (semi)groups of matrices over Z_p. One of the (semi)groups is additive, the other one multiplicative. This allows us to take advantage of both operations on matrices to diffuse information. We note that in our protocol, no power of any matrix or of any element of Z_p is ever exposed, so all standard attacks on Diffie-Hellman-like protocols (including Shor's quantum algorithm attack) are not applicable.

The IMDEA Software Institute offers a postdoc position in the area of cryptography. Topics of particular interest include (but are not limited to): secure computation (multiparty computation, homomorphic/functional encryption), zero knowledge proofs, and verifiable computation. The postdoc will work under the supervision of Dario Fiore and Ignacio Cascudo.

Who should apply?
Applicants should have (or be about to complete) a PhD in cryptography or a related topic.

Working at IMDEA Software
The position is based in Madrid, Spain where the IMDEA Software Institute is situated. Salaries are internationally competitive and include attractive conditions such as access to an excellent public healthcare system. The working language at the institute is English. Knowledge of Spanish is not required.

Dates
The position has guaranteed funding for at least 2 years. The starting date is flexible with a preference in mid 2021.

How to apply?
Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2021-02-postdoc-cryptoprimitives.
Deadline for applications is February 28th, 2021.
We encourage early applications and review of applications will begin immediately.

Closing date for applications:

Contact: Dario Fiore (dario.fiore (at) imdea.org) and Ignacio Cascudo (ignacio.cascudo (at) imdea.org)

More information: https://careers.software.imdea.org/postdoc/2021-02-postdoc-cryptoprimitives/

Event date: 13 December to 15 December 2021
Submission deadline: 1 June 2021
Notification: 1 October 2021

Event date: 5 December to 9 December 2021

Abstract The Supersingular Isogeny Key Encapsulation mechanism (SIKE) is the only post-quantum key encapsulation mechanism based on supersingular elliptic curves and isogenies between them. Despite the security of the protocol, unlike the rest of the NIST post-quantum algorithms, SIKE requires more number of clock cycles and hence does not provide competitive timing, energy and power consumption results. However, it is more attractive offering smallest public key sizes as well as ciphertext sizes, which taking into account the impact of the communication costs and storage of the keys could become as good fit for resource-constrained devices. In this work, we present the fastest practical implementation of SIKE, targeting the platform Cortex-M4 based on the ARMv7-M architecture. We performed our measurements on NIST recommended device based on STM32F407 microcontroller, for benchmarking the clock cycles, and on the target board Nucleo-F411RE, attached to X-NUCLEO-LPM01A (Power Shield), for measuring the power and energy consumption. The lower level finite field arithmetic and extension field operations play main role determining the efficiency of SIKE. Therefore, we mainly focus on those improvements and apply them to all NIST required security levels. Our SIKEp434 implementations for NIST security level 1 take about 850ms which is about 22.3% faster than the counterparts appeared in previous work. Moreover, our implementations are 21.9%, 19.7% and 19.5% faster for SIKEp503, SIKEp610 and SIKEp751 in comparison to the previously reported work for other NIST recommended security levels. Finally, we benchmark power and energy consumption and report the results for comparison.

In response to standardization requests regarding password-authenticated key exchange (PAKE) protocols, the IRTF working group CFRG has setup a PAKE selection process in 2019, which led to the selection of the CPace protocol in the balanced setting, in which parties share a common password.

In this paper, we provide a security analysis of CPace in the universal composability framework for implementations on elliptic-curve groups. When doing so, we restrict the use of random oracles to hash functions only and refrain from modeling CPace's MapToPoint function that maps field elements to curve points as an idealized function. As a result, CPace can be proven secure under standard complexity assumptions in the random-oracle model.

Finally, in order to extend our proofs to different CPace variants optimized for specific environments, we employ a new approach, which represents the assumptions required by the proof as libraries which a simulator can access. By allowing for the modular replacement of assumptions used in the proof, this new approach avoids a repeated analysis of unchanged protocol parts and lets us efficiently analyze the security guarantees of all the different CPace variants.

Secure multi-party computation (MPC) allows a set of n servers to jointly compute an arbitrary function of their inputs, without revealing these inputs to each other. A (k,n) threshold secret sharing is a protocol in which a single secret is divided into n shares and the secret can be recovered from a threshold k shares. Typically, multiplication of (k,n) secret sharing will result in increase of polynomial degree from k-1 to 2k-2, thus increasing the number of shares required from k to 2k-1. Since each server typically hold only one share, the number of servers required in MPC will also increase from k to 2k-1. Therefore, a set of n servers can compute multiplication securely if the adversary corrupts at most k-1<n/2 of the servers. In this paper, we differentiate the number of servers N required and parameter n of (k,n) secret sharing scheme, and propose a method of computing (k-1) sharing of multiplication ab by using only N=k servers. By allowing each server to hold two shares, we realize MPC of multiplication with the setting of N=k,n&#8805;2k-1. We also show that our proposed method is information theoretic secure against a semi-honest adversary.

Multi-Party Non-Interactive Key Exchange (MP-NIKE) is a fundamental cryptographic primitive in which users register into a key generation centre and receive a public/private key pair each. After that, any subset of these users can compute a shared key without any interaction. Nowadays, IoT devices suffer from a high number and large size of messages exchanged in the Key Management Protocol (KMP). To overcome this, an MP-NIKE scheme can eliminate the airtime and latency of messages transferred between IoT devices. MP-NIKE schemes can be realized by using multilinear maps. There are several attempts for constructing multilinear maps based on indistinguishable obfuscation, lattices and the Chinese Remainder Theorem (CRT). Nevertheless, these schemes are inefficient in terms of computation cost and memory overhead. Besides, several attacks have been recently reported against CRT-based and lattice-based multilinear maps. There is only one modular exponentiation-based MP-NIKE scheme in the literature which has been claimed to be both secure and efficient. In this article, we present an attack on this scheme based on the Euclidean algorithm, in which two colluding users can obtain the shared key of any arbitrary subgroup of users. We also propose an efficient and secure MP-NIKE scheme. We show how our proposal is secure in the random oracle model assuming the hardness of the root extraction modulo a composite number.

Even though the currently used encryption and signature schemes are well tested and secure in a classical computational setting, they are not quantum-resistant as Shor's work proves. Taking this into account, alternatives based on hard mathematical problems that cannot be solved using quantum methods are needed, and lattice-based cryptography offers such solutions. The well-known GGH and NTRUEncrypt encryption schemes are proven secure, but their corresponding signature schemes are flawed in their design approach. Once introducing the computationally hard problems like Ring-LWE, elegant and efficient cryptographic primitives could be built.

Security of cryptographic primitives is usually proved by assuming ``ideal'' probability distributions. We need to replace them with approximated ``real'' distributions in the real-world systems without losing the security level. We demonstrate that the Hellinger distance is useful for this problem, while the statistical distance is mainly used in the cryptographic literature. First, we show that for preserving $\lambda$-bit security of a given security game, the closeness of $2^{-\lambda/2}$ to the ideal distribution is sufficient for the Hellinger distance, whereas $2^{-\lambda}$ is generally required for the statistical distance. The result can be applied to both search and decision primitives through the bit security framework of Micciancio and Walter (Eurocrypt 2018). We also show that the Hellinger distance gives a tighter evaluation of closeness than the max-log distance when the distance is small. Finally, we show that the leftover hash lemma can be strengthened to the Hellinger distance. Namely, a universal family of hash functions gives a strong randomness extractor with optimal entropy loss for the Hellinger distance. Based on the results, a $\lambda$-bit entropy loss in randomness extractors is sufficient for preserving $\lambda$-bit security. The current understanding based on the statistical distance is that a $2\lambda$-bit entropy loss is necessary.

Due to high IC design costs and emergence of countless untrusted foundries, logic encryption has been taken into consideration more than ever. In state-of-the-art logic encryption works, a lot of performance is sold to guarantee security against both the SAT-based and the removal attacks. However, the SAT-based attack cannot decrypt the sequential circuits if the scan chain is protected or if the unreachable states encryption is adopted. Instead, these security schemes can be defeated by the model checking attack that searches iteratively for different input sequences to put the activated IC to the desired reachable state. In this paper, we propose a practical logic encryption approach to defend against the model checking attack on sequential circuits. The robustness of the proposed approach is demonstrated by experiments on around fifty benchmarks.

In July 2020, the lattice-based CRYSTALS-Dilithium digital signature scheme has been chosen as one of the three third-round finalists in the post-quantum cryptography standardization process by the National Institute of Standards and Technology (NIST). In this work, we present the first Very High Speed Integrated Circuit Hardware Description Language (VHDL) implementation of the CRYSTALS-Dilithium signature scheme for Field-Programmable Gate Arrays (FPGAs). Due to our parallelization-based design requiring only low numbers of cycles, running at high frequency and using reasonable amount of hardware resources on FPGA, our implementation is able to sign 15832 messages per second and verify 10524 signatures per second. In particular, the signing algorithm requires 68461 Look-Up Tables (LUTs), 86295 Flip-Flops (FFs), and the verification algorithm takes 61738 LUTs and 34963 FFs on Virtex 7 UltraScale+ FPGAs. In this article, experimental results for each Dilithium security level are provided and our VHDL-based implementation is compared with related High-Level Synthesis (HLS)-based implementations. Our solution is ca 114 times faster (in the signing algorithm) and requires less hardware resources.

Gun violence results in a significant number of deaths in the United States. Starting in the 1960’s, the US Congress passed a series of gun control laws to regulate the sale and use of firearms. One of the most important but politically fraught gun control measures is a national gun registry. A US Senate office is currently drafting legislation that proposes the creation of a voluntary national gun registration system. At a high level, the bill envisions a decentralized system where local county officials would control and manage the registration data of their constituents. These local databases could then be queried by other officials and law enforcement to trace guns. Due to the sensitive nature of this data, however, these databases should guarantee the confidentiality of the data.

In this work, we translate the high-level vision of the proposed legislation into technical requirements and design a cryptographic protocol that meets them. Roughly speaking, the protocol can be viewed as a decentralized system of locally-managed end-to-end encrypted databases. Our design relies on various cryptographic building blocks including structured encryption, secure multi-party computation and secret sharing. We propose a formal security definition and prove that our design meets it. We implemented our protocol and evaluated its performance empirically at the scale it would have to run if it were deployed in the United States. Our results show that a decentralized and end-to-end encrypted national gun registry is not only possible in theory but feasible in practice.

Event date: 28 June to 1 July 2021
Submission deadline: 18 March 2021
Notification: 29 April 2021