International Association
for Cryptologic Research

Existing work on privacy-preserving machine learning with Secure Multiparty Computation (MPC) is almost exclusively focused on model training and on inference with trained models, thereby overlooking the important data pre-processing stage. In this work, we propose the first MPC based protocol for private feature selection based on the filter method, which is independent of model training, and can be used in combination with any MPC protocol to rank features. We propose an efficient feature scoring protocol based on Gini impurity to this end. To demonstrate the feasibility of our approach for practical data science, we perform experiments with the proposed MPC protocols for feature selection in a commonly used machine-learning-as-a-service configuration where computations are outsourced to multiple servers, with semi-honest and with malicious adversaries. Regarding effectiveness, we show that secure feature selection with the proposed protocols improves the accuracy of classifiers on a variety of real-world data sets, without leaking information about the feature values or even which features were selected. Regarding efficiency, we document runtimes ranging from several seconds to an hour for our protocols to finish, depending on the size of the data set and the security settings.

Many video classification applications require access to personal data, thereby posing an invasive security risk to the users' privacy. We propose a privacy-preserving implementation of single-frame method based video classification with convolutional neural networks that allows a party to infer a label from a video without necessitating the video owner to disclose their video to other entities in an unencrypted manner. Similarly, our approach removes the requirement of the classifier owner from revealing their model parameters to outside entities in plaintext. To this end, we combine existing Secure Multi-Party Computation (MPC) protocols for private image classification with our novel MPC protocols for oblivious single-frame selection and secure label aggregation across frames. The result is an end-to-end privacy-preserving video classification pipeline. We evaluate our proposed solution in an application for private human emotion recognition. Our results across a variety of security settings, spanning honest and dishonest majority configurations of the computing parties, and for both passive and active adversaries, demonstrate that videos can be classified with state-of-the-art accuracy, and without leaking sensitive user information.

Event date: 14 August 2021
Submission deadline: 1 May 2021
Notification: 15 June 2021

Event date: 20 March to 25 March 2022

The crucial step in elliptic curve scalar multiplication based on scalar decompositions using efficient endomorphisms—such as GLV, GLS or GLV+GLS—is to produce a short basis of a lattice involving the eigenvalues of the endomorphisms, which usually is obtained by lattice basis reduction algorithms or even more specialized algorithms. Recently, lattice basis reduction is found to be unnecessary. Benjamin Smith (AMS 2015) was able to immediately write down a short basis of the lattice for the GLV, GLS, GLV+GLS of quadratic twists using elementary facts about quadratic rings. Certainly it is always more convenient to use a ready-made short basis than to compute a new one by some algorithm.

In this paper, we extend Smith's method on GLV+GLS for quadratic twists to quartic and sextic twists, and give ready-made short bases for $4$-dimensional decompositions on these high degree twisted curves. In particular, our method gives a unified short basis compared with Hu et. al's method (DCC 2012) for $4$-dimensional decompositions on sextic twisted curves.

This paper proposes a new lattice-based weak curve fault attack on ECDSA, which assumes that a continuous bits block of curve parameter $a$ is disturbed randomly by fault injection. Firstly, the faulty $a'$ can be deduced by a distinguisher of quadratic residue, from which a weak curve with order $n'$ is derived. Secondly, under the assumption that there exists a solvable smooth small factor $d$ in $n'$, we obtain some reduced information of the nonce by solving the ECDLP constructed in a small subgroup with order $d$. Finally, based on the reduced information, a model of lattice attack can be constructed to recover the signature private key by solving special instances of closest vector problem(CVP) in lattice.

Compared with the previous weak curve fault attacks, our attack increases the success rate of fault injection sharply, since it is not required that the constructed instance of ECDLP with order $n'$ is practically solvable. In addition, the application of lattice-based attack is further extended in our attack by relaxing the restriction on the information leakage of nonces in comparison with the traditional partially known information attacks. Moreover, when there is a general random scalar masking in ECDSA, our attack still works without the additional masked bits leakage. Finally, the experiments demonstrate that the practical rate of effective faulty $a'$ is up to $94.9\%$ when the bit length of $d$ is greater than $8$, and the corresponding lattice attack is also feasible practically.

A tweakable enciphering scheme (TES) is a length preserving (tweakable) encryption scheme that provides (tweakable) strong pseudorandom permutation security on arbitrarily long messages. TES is traditionally built using block ciphers and the security of the mode depends on the strong pseudorandom permutation security of the underlying block cipher. In this paper, we construct TESs using public random permutations. Public random permutations are being considered as a replacement of block cipher in several cryptographic schemes including AEs, MACs, etc. However, to our knowledge, a systematic study of constructing TES using public random permutations is missing. In this paper, we give a generic construction of a TES which uses a public random permutation, a length expanding public permutation based PRF and a hash function which is both almost xor universal and almost regular. Further, we propose a concrete length expanding public permutation based PRF construction. We also propose a single keyed TES using a public random permutation and an AXU and almost regular hash function.

By combining inner-product and Lagrange's four-square theorem, we structure a range proof scheme which is called Cuproof. The scheme of Cuproof would make a range proof to prove that a secret number $v \in [a,b]$ without exposing redundant information of $v$. In Cuproof, the communication cost and the proof time is constant. Once the interval of range proof is large, the scheme of Cuproof would show better. Zero-knowledge proof is widely used in blockchain. For example, zk-SNARK is used by Zcash as its core technology in identifying transactions. Up to now, various range proofs have been proposed as well their efficiency and range-flexibility are enhanced. Bootle et al. firstly used inner product method and recursion to an efficient zero-knowledge proof. Then, Benediky B\"{u}nz et al. came up with an efficient zero-knowledge argument called Bulletproofs which convinces the verifier that a secret number lies in $[0,\, 2^{n}]$. The scheme of Cuproof is based on the scheme of Bulletproofs.

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/