International Association
for Cryptologic Research

We present the first homomorphic secret sharing (HSS) construction that simultaneously (1) has negligible correctness error, (2) supports integers from an exponentially large range, and (3) relies on an assumption not known to imply FHE --- specifically, the Decisional Composite Residuosity (DCR) assumption. This resolves an open question posed by Boyle, Gilboa, and Ishai (Crypto 2016). Homomorphic secret sharing is analogous to fully-homomorphic encryption, except the ciphertexts are shared across two non-colluding evaluators. Previous constructions of HSS either had non-negligible correctness error and polynomial-size plaintext space or were based on the stronger LWE assumption. We also present two applications of our technique: a multi-server ORAM with constant bandwidth overhead, and a rate-1 trapdoor hash function with negligible error rate.

Oblivious Pseudorandom Function (OPRF) is a protocol between a client holding input x and a server holding key k for a PRF F. At the end, the client learns F_k(x) and nothing else while the server learns nothing. OPRF's have found diverse applications as components of larger protocols, and the currently most efficient instantiation, with security proven in the UC model, is F_k(x)=H2(x,(H1(x))^k) computed using so-called exponential blinding, i.e., the client sends a=(H1(x))^r for random r, the server responds b=a^k, which the client ublinds as v=b^{1/r} to compute F_k(x)=H2(x,v).

However, this protocol requires two variable-base exponentiations on the client, while a more efficient multiplicative blinding scheme replaces one or both client exponentiations with fixed-base exponentiation, leading to the decrease of the client's computational cost by a factor between two to six, depending on pre-computation. We analyze the security of the above OPRF with multiplicative blinding, showing surprising weaknesses that offer attack avenues which are not present using exponential blinding. We characterize the security of this OPRF implementation as a "Revised OPRF" functionality, a relaxation of UC OPRF functionality used in prior work. On the positive side, we show that the Revised OPRF suffices for the security of OPAQUE, the asymmetric PAKE protocol, hence allowing OPAQUE the computational advantages of multiplicative blinding. Unfortunately, we also show examples of other OPRF applications which become insecure when using such blinding. The conclusion is that usage of multiplicative blinding for F_k(x) defined as above, in settings where correct value g^k (needed for multiplicative blinding) is not authenticated, and OPRF inputs are of low entropy, must be carefully analyzed, or avoided all together. We complete the picture by showing a simple and safe alternative definition of function F_k(x) which offers (full) UC OPRF security using either form of blinding.

SIDH/SIKE-style protocols benefit from key compression to minimize their bandwidth requirements, but proposed key compression mechanisms rely on computing bilinear pairings. Pairing computation is a notoriously expensive operation, and, unsurprisingly, it is typically one of the main efficiency bottlenecks in SIDH key compression, incurring processing time penalties that are only mitigated at the cost of trade-offs with precomputed tables. We address this issue by describing how to compress isogeny-based keys without pairings. As a bonus, we also substantially reduce the storage requirements of other operations involved in key compression.

In this work, we put forth the notion of compatibility of any key generation or setup algorithm. We focus on the specific case of encryption, and say that a key generation algorithm KeyGen is X-compatible (for X \in {CPA, CCA1, CCA2}) if there exist encryption and decryption algorithms that together with KeyGen, result in an X-secure public-key encryption scheme.

We study the following question: Is every CPA-compatible key generation algorithm also CCA-compatible? We obtain the following answers:

- Every sub-exponentially CPA-compatible KeyGen algorithm is CCA1-compatible, assuming the existence of hinting PRGs and sub-exponentially secure keyless collision resistant hash functions. - Every sub-exponentially CPA-compatible KeyGen algorithm is also CCA2-compatible, assuming the existence of non-interactive CCA2 secure commitments, in addition to sub-exponential security of the assumptions listed in the previous bullet.

Here, sub-exponentially CPA-compatible KeyGen refers to any key generation algorithm for which there exist encryption and decryption algorithms that result in a CPA-secure public-key encryption scheme {\em against sub-exponential adversaries}.

This gives a way to perform CCA secure encryption given any public key infrastructure that has been established with only (sub-exponential) CPA security in mind. The resulting CCA encryption makes black-box use of the CPA scheme and all other underlying primitives.

Post-quantum cryptography or PQC is a trend that has a deserved NIST status, and which aims to be resistant to quantum computer attacks like Shor and Grover algorithms. We choose to follow a non-standard way to achieve PQC: taking any standard asymmetric protocol and replacing numeric field arithmetic with GF-256 field operations. By doing so, it is easy to implement R-propped asymmetric systems as present and former papers show. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid resists known quantum algorithm and classical linearization attacks like Tsaban Algebraic Span or Romankov linearization attacks. Here we develop an original group-based digital signature protocol and R-propped it. The protocol security relies on the intractability of a generalized discrete log problem, combined with the power sets of algebraic ring extension tensors. The semantic security and classical and quantum security levels are discussed. Finally, we present a numerical example of the proposed protocol.

The CryptoLux group of the University of Luxembourg has a vacancy for a post-doctoral researcher in the area of symmetric cryptography. The successful candidate will contribute to a research project entitled Analysis and Protection of Lightweight Cryptographic Algorithms (APLICA), which is funded by the Luxembourgish Fonds National de la Recherche and the German Research Foundation. Starting in 2021, APLICA will run over a period of 3 years as a joint research project between the CryptoLux group and the Workgroup for Symmetric Cryptography of Ruhr-University Bochum. The mission of the APLICA project is to develop new cryptanalytic techniques for lightweight authenticated encryption algorithms and hash functions, and to design and implement new countermeasures against side-channel attacks that are suitable for constrained devices.

Candidates must have a Ph.D. degree in symmetric cryptography or a closely related field. Preference will be given to candidates with a strong publication record that includes at least one paper at an IACR conference/workshop or one of the top-4 security conferences. Experience in software development for embedded systems or mounting side-channel attacks is a plus. Candidates with an interest to conduct research in one of the following areas are particularly encouraged to apply:

• Cryptanalysis of authenticated encryption algorithms or hash functions
• Leakage resilience or leakage reduction by design (e.g. modes of operation)
• Security evaluation of leakage-resilient primitives or constructions

The position is available from Jan. 2021 on basis of a fixed-term contract for 3 years. The University of Luxembourg offers excellent working conditions and a highly competitive salary. Interested candidates are invited to send their application by email to Alex Biryukov before Apr. 1, 2021 (early submission is strongly encouraged, applications will be processed upon receipt). The application material should contain a cover letter explaining the candidate's research interests, a CV (incl. photo), a list of publications, scans of diploma certificates, and contact details of 3 references.

Closing date for applications:

Contact: Prof. Alex Biryukov (alex.biryukov@uni.lu)

More information: https://www.fnr.lu/projects/analysis-and-protection-of-lightweight-cryptographic-algorithms/

Cryptography and Blockchain research group at Fujitsu Laboratories of America is looking for research interns to work in cutting edge research problems of theoretical and practical interest in the areas of cryptography, security, and privacy. Potential research topics include (but not limited to) homomorphic encryption, lattice cryptography, zero knowledge proofs, memory hard functions, consensus algorithms, etc. A broad overview of our current research efforts is available in the link below.

This is a remote position; we are accepting applications from exceptional graduate students based in USA, UK or Japan. The selected candidate will closely work with researchers based in Sunnyvale, California. We offer attractive remuneration and typical length of internship is 12 weeks. Start date is flexible.

Closing date for applications:

Contact: Avradip Mandal (amandal at fujitsu dot com)

More information: https://www.fujitsu.com/us/about/businesspolicy/tech/rd/research/computer-security/cryptography-and-privacy/

The IMDEA Software Institute offers a postdoc position in the area of security and privacy in blockchain. The work may involve a combination of (i) identification of security threats and privacy leakages in cryptocurrencies (e.g., hardware wallets, layer-2 scalability solutions, cross-chain protocols, cybercrime operations), (ii) design and evaluation of cryptographic protocols to enhance the security, privacy, scalability and interoperability of current cryptocurrencies. The postdoc will work under the supervision of Pedro Moreno-Sánchez and Juan Caballero.

Who should apply?

Applicants should have a PhD in computer science or a related discipline with an excellent track-record and an interest in privacy-enhancing technologies, applied cryptography, and data analysis. Good command of English both spoken and written is required.

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 is for 2 years. The preferred starting date is June 2021 with some flexibility.

How to apply?

Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2021-03-postdoc-spblockchain. Review of applications will begin immediately and close when the position is filled or on April 2nd, 2021.

Closing date for applications:

Contact: pedro.moreno(at)imdea.org and/or juan.caballero(at)imdea.org

More information: https://software.imdea.org/open_positions/2021-03-postdoc-spblockchain.html

Trusted execution enviroments (TEEs) enable secure execution of program on untrusted hosts and cryptographically attest the correctness of outputs. As these are complex systems, it is hard to capture the exact security achieved by protocols employing TEEs. Crucially TEEs are typically employed in multiple protocols at the same time, thus composable security (with global subroutines) is a natural goal for such systems.

We show that under an attested execution setup $\Gatt$ we can realise cryptographic functionalities that are unrealizable in the standard model. We propose a new primitive of Functional Encryption for Stateful and Randomised functionalities (FESR) and an associated protocol, Steel, that realizes it. We show that Steel UC-realises FESR in the universal composition with global subroutines model (TCC 2020). Our work is also a validation of the compositionality of earlier work (Iron}, CCS 2017) capturing (non-stateful) hardware-based functional encryption.

As the existing functionality for attested execution of Pass et al. (Eurocrypt 2017) is too strong for real world use, we propose a weaker functionality that allows the adversary to conduct rollback and forking attacks. We show that the stateful variant of $\Steel$, contrary to the stateless variant corresponding to Iron, is not secure in this setting and propose several mitigation techniques.

Updatable encryption (UE; CRYPTO 2013) is a symmetric encryption primitive that allows to periodically rotate encryption keys without the need to decrypt and re-encrypt already encrypted data. This is achieved by means of an update token that allows to perform the ciphertext update. In existing UE constructions, the update token thereby allows bi-directional updates of keys and ciphertexts, which leads to undesired information leakage and rather involved security models. A recent work by Jiang (ASIACRYPT 2020) shows that in the currently strongest UE model due to Boyd et al. (CRYPTO 2020), UE with bi-directional key and ciphertext updates implies schemes with uni-directional ones. While this might suggests that uni-directionality does not add security, we show that this rather stems from a defective security model and in an adequate model uni-directionality is indeed stronger. Irrespective of this fact, even uni-directional UE schemes still do not capture the intuitive security requirements expected from UE. To overcome this leakage problem and obtain natural security guarantees, UE schemes with so-called no-directional key updates are necessary, i.e., where tokens can solely update ciphertexts and only in one direction. However, it stayed unclear whether such UE schemes can be constructed and this tasks is presented as a challenging open problem in both aforementioned works.

In this work, we resolve these issues and present the first UE constructions with uni- and even no-directional key updates. We show that such UE schemes can be constructed in the standard model via the notion of dual system groups from the standard d-Lin assumption in prime-order bilinear groups. Our approach of constructing UE significantly departs from previous ones and in particular views UE from the perspective of puncturable encryption (Green and Miers, S&P 2015). Towards constructing UE, as an stepping stone, we introduce a variant of puncturable encryption that additionally support puncturing of ciphertexts. This turns out to be a useful abstraction on our way to construct UE and may be of independent interest.

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), the need for symmetric encryption schemes that minimize the number of field multiplications in their natural algorithmic description is apparent. This development has brought forward many dedicated symmetric encryption schemes that minimize the number of multiplications in GF(2^n) or GF(p), with p being prime. These novel schemes have lead to new cryptanalytic insights that have broken many of said schemes. Interestingly, to the best of our knowledge, all of the newly proposed schemes that minimize the number of multiplications use those multiplications exclusively in S-boxes based on a power mapping that is typically x^3 or x^{-1}. Furthermore, most of those schemes rely on complex and resource-intensive linear layers to achieve a low multiplication count.

In this paper, we present Ciminion, an encryption scheme minimizing the number of field multiplications in large binary or prime fields, while using a very lightweight linear layer. In contrast to other schemes that aim to minimize field multiplications in GF(2^n) or GF(p), Ciminion relies on the Toffoli gate to improve the non-linear diffusion of the overall design. In addition, we have tailored the primitive for the use in a Farfalle-like construction in order to minimize the number of rounds of the used primitive, and hence, the number of field multiplications as far as possible.

In this work we present a new construction for a batched Oblivious Pseudorandom Function (OPRF) based on Vector-OLE and the PaXoS data structure. We then use it in the standard transformation for achieving Private Set Intersection (PSI) from an OPRF. Our overall construction is highly efficient with $O(n)$ communication and computation. We demonstrate that our protocol can achieve malicious security at only a very small overhead compared to the semi-honest variant. For input sizes $n = 2^{20}$, our malicious protocol needs 6.2 seconds and less than 59 MB communication. This corresponds to under 450 bits per element, which is the lowest number for any published PSI protocol (semi-honest or malicious) to date. Moreover, in theory our semi-honest (resp. malicious) protocol can achieve as low as 219 (resp. 260) bits per element for $n=2^{20}$ at the added cost of interpolating a polynomial over $n$ elements. As a second contribution, we present an extension where the output of the PSI is secret-shared between the two parties. This functionality is generally referred to as Circuit-PSI. It allows the parties to perform a subsequent MPC protocol on the secret-shared outputs, e.g., train a machine learning model. Our circuit PSI protocol builds on our OPRF construction along with another application of the PaXoS data structure. It achieves semi-honest security and allows for a highly efficient implementation, up to 3x faster than previous work.

We prove that the Module Learning With Errors (M-LWE) problem with binary secrets and rank $d$ is at least as hard as the standard version of M-LWE with uniform secret and rank $k$, where the rank increases from $k$ to $d \geq (k+1)\log_2 q + \omega(\log_2 n)$, and the Gaussian noise from $\alpha$ to $\beta = \alpha \cdot \Theta(n^2\sqrt{d})$, where $n$ is the ring degree and $q$ the modulus. Our work improves on the recent work by Boudgoust et al. in 2020 by a factor of $\sqrt{md}$ in the Gaussian noise, where $m$ is the number of given M-LWE samples, when $q$ fulfills some number-theoretic requirements. We use a different approach than Boudgoust et al. to achieve this hardness result by adapting the previous work from Brakerski et al. in 2013 for the Learning With Errors problem to the module setting. The proof applies to cyclotomic fields, but most results hold for a larger class of number fields, and may be of independent interest.

Auctioning an asset with sealed bids has been shown to be economically optimal but requires trusting a auctioneer who analyzes the bids and determines the winner. Many privacy preserving computation protocols for auctions have been proposed, aiming at eliminating the need for a trusted third party. However, they lack fairness, meaning that the adversary learns the outcome of the auction before honest parties and may choose to make the protocol fail without suffering any consequences. In this work, we propose efficient protocols for both first and second price sealed bid auctions with fairness against rational adversaries, leveraging secret cryptocurrency transactions and public smart contracts. In our approach, the bidders jointly compute the winner of the auction while preserving the privacy of losing bids and ensuring that cheaters are financially punished by losing a secret collateral deposit. We guarantee that it is never profitable for rational adversaries to cheat by making the deposit equal to the bid plus the cost of running the protocol, i.e. once a party commits to a bid it is guaranteed that it has the funds and it cannot walk away from the protocol without forfeiting the bid. Moreover, our protocols guarantee that the winner is determines and the auction payments are completed even if the adversary misbehaves, so that it cannot force the protocol to fail and then rejoin the auction with an adjusted bid. Our constructions are more efficient than the state-of-the-art even though they achieve stronger security guarantees, i.e. fairness. Interestingly, we show how the Second Price can be computed with a minimal increase of the complexity of the simpler First Price case. Moreover, in case there is no cheating, only collateral deposit and refund transactions must be sent to the smart contract, significantly saving on-chain storage.

The Fiat-Shamir with Aborts paradigm of Lyubashevsky (Asiacrypt'09) has given rise to efficient lattice-based signature schemes. One popular implementation is Dilithium which is a finalist in an ongoing standardization process run by the NIST. An interesting research question is whether it is possible to combine several unrelated signatures, issued from different signing parties on different messages, into one single aggregated signature. Of course, its size should be much smaller than the trivial concatenation of all signatures. Ideally, the aggregation can be done offline by a third party, called public aggregation. Doröz et al. (IACR eprint 2020/520) proposed a first lattice-based aggregate signature scheme allowing public aggregation. However, its security is based on the hardness of the Partial Fourier Recovery problem, a structured lattice problem which neither benefits from worst-to-average reductions nor wasn't studied extensively from a cryptanalytic point of view. In this work we give a first instantiation of an aggregate signature allowing public aggregation whose hardness is proven in the aggregate chosen-key model assuming the intractability of two well-studied problems on module lattices: The Module Learning With Errors problem (M-LWE) and the Module Short Integer Solution problem~(M-SIS). Both benefit from worst-case to average-case hardness reductions. Our protocol can be seen as an aggregated variant of Dilithium. Alternatively, it can be seen as a transformation of the protocol from Doröz et al. to the M-LWE/M-SIS framework.

We describe a simple method for solving the distributed discrete logarithm problem in Paillier groups, allowing two parties to locally convert multiplicative shares of a secret (in the exponent) into additive shares. Our algorithm is perfectly correct, unlike previous methods with an inverse polynomial error probability. We obtain the following applications and further results.

- Homomorphic secret sharing. We construct homomorphic secret sharing for branching programs with *negligible* correctness error and supporting *exponentially large* plaintexts, with security based on the decisional composite residuosity (DCR) assumption.

- Correlated pseudorandomness. Pseudorandom correlation functions (PCFs), recently introduced by Boyle et al. (FOCS 2020), allow two parties to obtain a practically unbounded quantity of correlated randomness, given a pair of short, correlated keys. We construct PCFs for the oblivious transfer (OT) and vector oblivious linear evaluation (VOLE) correlations, based on the quadratic residuosity (QR) or DCR assumptions, respectively. We also construct a pseudorandom correlation generator (for producing a bounded number of samples, all at once) for general degree-2 correlations including OLE, based on a combination of (DCR or QR) and the learning parity with noise assumptions.

- Public-key silent OT/VOLE. We upgrade our PCF constructions to have a *public-key setup*, where after independently posting a public key, each party can locally derive its PCF key. This allows completely *silent generation* of an arbitrary amount of OTs or VOLEs, without any interaction beyond a PKI, based on QR, DCR, a CRS and a random oracle. The public-key setup is based on a novel non-interactive vector OLE protocol, which can be seen as a variant of the Bellare-Micali oblivious transfer protocol.

In this paper, we describe an extensible experimental infrastructure and methodology for evaluating the micro-architectural leakage, based on power consumption, which stems from a physical device. Building on existing literature, we use it to systematically study 14 different devices, which span 4 different instruction set architectures and 4 different vendors. The study allows a characterisation of each device with respect to any leakage effects stemming from sources within the micro-architectural implementation; we use it, for example, to identify and document several novel leakage effects (e.g., due to speculative instruction execution), and scenarios where an assumption about leakage is non-portable between different yet compatible devices. Ours is the widest study of its kind we are aware of, and highlights a range of challenges with respect to 1) the design, implementation, and evaluation of masking schemes, 2) construction of accurate fine-grained leakage models, and 3) selection of suitable devices for experimental research. For example, in relation to 1), we cast further doubt on whether a given device can or does uphold the assumptions required by a given masking scheme; in relation to 2), we ultimately conclude that real-world leakage models (either statistical or formal) must include information about the micro-architecture of the device being modelled; in relation to 3), we claim the near mono-culture of devices that dominates existing literature is insufficient to support general claims regarding security. This is particularly important

An (n,m,t)-homomorphic secret sharing (HSS) scheme allows n clients to share their inputs across m servers, such that the inputs are hidden from any t colluding servers, and moreover the servers can evaluate functions over the inputs locally by mapping their input shares to compact output shares. Such compactness makes HSS a useful building block for communication-efficient secure multi-party computation (MPC).

In this work, we propose a simple compiler for HSS evaluating multivariate polynomials based on two building blocks: (1) homomorphic encryption for linear functions or low-degree polynomials, and (2) information-theoretic HSS for low-degree polynomials. Our compiler leverages the power of the first building block towards improving the parameters of the second.

We use our compiler to generalize and improve on the HSS scheme of Lai, Malavolta, and Schröder [ASIACRYPT'18], which is only efficient when the number of servers is at most logarithmic in the security parameter. In contrast, we obtain efficient schemes for polynomials of higher degrees and an arbitrary number of servers. This application of our general compiler extends techniques that were developed in the context of information-theoretic private information retrieval (Woodruff and Yekhanin [CCC'05]), which use partial derivatives and Hermite interpolation to support the computation of polynomials of higher degrees.

In addition to the above, we propose a new application of HSS to MPC with preprocessing. By pushing the computation of some HSS servers to a preprocessing phase, we obtain communication-efficient MPC protocols for low-degree polynomials that use fewer parties than previous protocols based on the same assumptions. The online communication of these protocols is linear in the input size, independently of the description size of the polynomial.

CSURF (CSIDH on the surface) was recently proposed by Castryck, and Decru in PQCrypto-2020, and then improved by the radical isogeny formulae in Asiacrypt-2020. The main advantage of using CSURF and radical isogenies is the possibility of using isogenies of degree two and radical isogeny chains of odd degree requiring only a single random sampling of points. This work addresses the practical implications of a constant-time implementation of CSURF and the radical isogeny procedures. In particular, this paper introduces the first constant-time formulation and implementation of the radical isogenies using projective representation, which are twice as efficient as the original radical isogeny formulae. Nevertheless, the overhead introduced by going to constant-time is significant: in terms of finite field operations, our experiments illustrate that the speed-up of using a constant-time CSURF-512 is reduced to 1.64% in comparison to the fastest state-of-the-art constant-time CSIDH-512 implementation. Furthermore, these savings disappear when using constant-time radical isogenies and when moving to higher parameter sets. This negatively answers the open question from Castryck and Decru: constant-time CSIDH implementations outperform both CSURF and radical isogenies.

In this paper we describe the first improvement of the shuffling countermeasure against side-channel attacks described by Ishai, Sahai and Wagner at Crypto 2003. More precisely, we show how to get worst case statistical security against $t$ probes with running time ${\mathcal O}(t)$ instead of ${\mathcal O}(t \log t)$; our construction is also much simpler. Recall that the classical masking countermeasure achieves perfect security but with running time ${\mathcal O}(t^2)$.