International Association
for Cryptologic Research

This paper proposes an internal state recovery attack on special class of stream generators called non-linear combiners and filter generators over finite fields consisting of linear feedback shift registers (LFSRs) and nonlinear functions combining internal states to form output stream. This attack utilizes the concept of an observer, well known in the theory of Linear Dynamical Systems. An observer is a special linear dynamical system which when fed with the output sequence of the stream generator as an input with arbitrary initial state, reconstructs the internal state of the generator in finite time. This attack is termed as observability attack and it is shown that the computations are of complexity $O(D^4)$ in pre-computation and of $O(D)$ for online computation, where $D = \sum_{i=0}^{d} {n \choose i}$ for stream generators with $n$ states and $d$ the degree of the output function, when the stream generator is defined over $\mathbb{F}_2$. The attack is technically applicable over general finite fields and appropriate bounds on computation are estimated. This attack gives an important estimates of time and memory resources required for cryptanalysis of realistic stream ciphers.

Resource Public Key Infrastructure (RPKI) is vital to the security of inter-domain routing. However, RPKI enables Regional Internet Registries (RIRs) to unilaterally takedown IP prefixes - indeed, such attacks have been launched by nation-state adversaries. The threat of IP prefix takedowns is one of the factors hindering RPKI adoption.

In this work, we propose the first distributed RPKI system, based on threshold signatures, that requires the coordination of a number of RIRs to make changes to RPKI objects; hence, preventing unilateral prefix takedown. We perform extensive evaluations using our implementation demonstrating the practicality of our solution. Furthermore, we show that our system is scalable and remains efficient even when RPKI is widely deployed.

Lattice-based cryptography forms the mathematical basis for homomorphic encryption, which allows computation directly on encrypted data. Homomorphic encryption enables privacy-preserving applications such as secure cloud computing; yet, its practical applications suffer from the high computational complexity of homomorphic operations. Fast implementations of the homomorphic encryption schemes heavily depend on efficient polynomial arithmetic; multiplication of very large degree polynomials over polynomial rings, in particular. Number theoretic transform (NTT) accelerates polynomial multiplication significantly and therefore, it is the core arithmetic operation in the majority of homomorphic encryption scheme implementations. Therefore, practical homomorphic applications require efficient and fast implementations of NTT in different computing platforms. In this work, we present an efficient and fast implementation of NTT, inverse NTT (INTT) and NTT-based polynomial multiplication operations for GPU platforms. To demonstrate that our GPU implementation can be utilized as an actual accelerator, we experimented with the key generation, the encryption and the decryption operations of the Brakerski/Fan-Vercauteren (BFV) homomorphic encryption scheme implemented in Microsoft's SEAL homomorphic encryption library on GPU, all of which heavily depend on the NTT-based polynomial multiplication. Our GPU implementations improve the performance of these three BFV operations by up to 141.95x, 105.17x and 90.13x, respectively, on Tesla V100 GPU compared to the highly-optimized SEAL library running on an Intel i9-7900X CPU.

Most submitted lattice-based key encapsulation mechanisms (KEMs) on the second or third round list of the NIST standardization follow a similar structure: First a CPA secure scheme is constructed, which is then converted to a CCA secure one. The research of the key reuse attacks against the CPA secure ones is important in two folds: First, it is an important part of the cryptographic assessment of the ongoing NIST standardization. Secondly, it helps the design of CCA-secure authenticated key exchange directly from LWE, without FO transform.

There have been a number of key mismatch attacks on these CPA secure versions when the public key is reused. However, a unified method to evaluate their resilience under key mismatch attacks is still missing. Since the key index of the efficiency of these attacks is the number of queries (matches and mismatches) needed to successfully mount such an attack, in this paper, we propose and develop a systematic approach to find the lower bounds on the minimum average number of queries needed for such attacks. Our basic idea is to transform the problem of finding the lower bound of queries into finding an optimal binary recovery tree (BRT), where the computations of the lower bounds become essentially the computations of certain Shannon entropy. The approach means that one cannot find a better attack with fewer queries than this lower bound. The introduction of the optimal BRT approach enables us to understand why, for some schemes, there is a big gap between the theoretical bounds and practical attacks, in terms of the number of queries needed. This further leads us to improve the existing attacks. Especially, we can reduce the needed queries against Frodo640 by 71.99% , LAC256 by 82.81%, and Newhope1024 by 97.44%.

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.