International Association
for Cryptologic Research

Non-malleability is an important security property for public-key encryption (PKE). Its significance is due to the fundamental unachievability of integrity and authenticity guarantees in this setting, rendering it the strongest integrity-like property achievable using only PKE, without digital signatures. In this work, we generalize this notion to the setting of quantum public-key encryption. Overcoming the notorious "recording barrier" known from generalizing other integrity-like security notions to quantum encryption, we generalize one of the equivalent classical definitions, comparison-based non-malleability, and show how it can be fulfilled. In addition, we explore one-time non-malleability notions for symmetric-key encryption from the literature by defining plaintext and ciphertext variants and by characterizing their relation.

Due to its shorter key size, elliptic curve cryptography (ECC) is gaining more and more popularity. However, if not properly implemented, the resulting cryptosystems may be susceptible to fault attacks. Over the past few years, several techniques for secure implementations have been published. This paper revisits the ring extension method and its adaptation to the elliptic curve setting.

Event date: 22 June to 25 June 2020
Submission deadline: 9 September 2019
Notification: 20 January 2020

Key encapsulation mechanism (KEM) variants of the Fujisaki-Okamoto (FO) transformation (CRYPTO 1999 and Journal of Cryptology 2013) that turn a weakly-secure public-key encryption (PKE) into an IND-CCA-secure KEM, were proposed by Hofheinz, Hoevelmanns and Kiltz (TCC 2017) and widely used among the KEM submissions to the NIST Post-Quantum Cryptography Standardization Project. The security reductions for these variants in the quantum random oracle model (QROM) were given by Hofheinz, Hoevelmanns and Kiltz (TCC 2017) and Jiang et al. (Crypto 2018). However, under standard CPA security assumptions, i.e., OW-CPA and IND-CPA, all these security reductions are far from desirable due to the quadratic security loss.

In this paper, for KEM variants of the FO transformation, we show that a typical measurement-based reduction in the QROM from breaking standard OW-CPA (or IND-CPA) security of the underlying PKE to breaking the IND-CCA security of the resulting KEM, will inevitably incur a quadratic loss of the security, where ``measurement-based" means the reduction measures a hash query from the adversary and uses the measurement outcome to break the underlying security of PKE. In particular, all currently known security reductions in (TCC 2017 and Crypto 2018) are of this type, and our results suggest an explanation for the lack of progress in improving the reduction tightness in terms of the degree of security loss. We emphasize that our results do not expose any post-quantum security weakness of KEM variants of FO transformation.

The purpose of this paper is to provide a comprehensive analysis and side-by-side comparison of the noise growth behaviour in the BGV and FV somewhat homomorphic encryption schemes, both heuristically and in their implementations in the libraries HElib and SEAL, respectively. We run extensive experiments in HElib and SEAL to com- pare the heuristic noise growth to the noise growth in practice. From the experiments, we observe that for both schemes, the heuristic bounds are not tight. We attempt to improve the tightness of the bounds in a num- ber of ways, including the definition of new notions of noise, such as the invariant noise for BGV and the scaled inherent noise for FV. This does not significantly tighten the bounds, thus we conclude that the current heuristic bounds are the best possible in terms of a theoretical analysis. As an additional contribution, we update the comparison between the two schemes presented by Costache and Smart [22], and find that BGV has a slight advantage over FV. Thus, the conclusions of [22] still hold, although the differences between BGV and FV are less dramatic.

There is a well-known gap between second-preimage resistance and preimage resistance for length-preserving hash functions. This paper introduces a simple concept that fills this gap. One consequence of this concept is that tight reductions can remove interactivity for multi-target length-preserving preimage problems, such as the problems that appear in analyzing hash-based signature systems. Previous reduction techniques applied to only a negligible fraction of all length-preserving hash functions, presumably excluding all off-the-shelf hash functions.

Using information-theoretic tools, this paper establishes a mathematical link between the probability of success of a side-channel attack and the minimum number of queries to reach a given success rate, valid for any possible distinguishing rule and with the best possible knowledge on the attacker's side. This link is a lower bound on the number of queries highly depends on Shannon's mutual information between the traces and the secret key. This leads us to derive upper bounds on the mutual information that are as tight as possible and can be easily calculated. It turns out that, in the case of an additive white Gaussian noise, the bound on the probability of success of any attack is directly related to the signal to noise ratio. This leads to very easy computations and predictions of the success rate in any leakage model.

This work presents 2 sigma protocols with helper to prove knowledge of:

-A solution to a system of quadratic polynomials

-A solution to an instance of the Permuted Kernel Problem

We then remove the helper from the protocol with a "cut-and-choose" protocol and we apply the Fiat-Shamir transform to obtain signature schemes with security proof in the QROM. We show that the resulting signature schemes, which we call the "MUltivarite quaDratic FIat-SHamir" scheme (MUDFISH) and the "ShUffled Solution to Homogeneous linear SYstem FIat-SHamir" scheme (SUSHSYFISH), are more efficient than existing signatures based on the MQ problem and the Permuted Kernel Problem. We also leverage the ZK-proof for PKP to improve the efficiency of Stern-like Zero Knowledge proofs for lattice statements.

This paper presents an optimized software implementation of the module-lattice-based key-encapsulation mechanism Kyber for the ARM Cortex-M4 microcontroller. Kyber is one of the round-2 candidates in the NIST post-quantum project. In the center of our work are novel optimization techniques for the number-theoretic transform (NTT) inside Kyber, which make very efficient use of the computational power offered by the “vector” DSP instructions of the target architecture. We also present results for the recently updated parameter sets of Kyber which equally benefit from our optimizations. As a result of our efforts we present software that is 18% faster than an earlier implementation of Kyber optimized for the Cortex-M4 by the Kyber submitters. Our NTT is more than twice as fast as the NTT in that software. Our software runs at about the same speed as the latest speed-optimized implementation of the other module-lattice based round-2 NIST PQC candidate Saber. However, for our Kyber software, this performance is achieved with a much smaller RAM footprint. Kyber needs less than half of the RAM of what the considerably slower RAM-optimized version of Saber uses. Our software does not make use of any secret-dependent branches or memory access and thus offers state-of-the-art protection against timing attacks

Enigma 2000 (E2K) is a cipher that updates the World War II-era Enigma Machine for the twenty-first century. Like the original Enigma, E2K is intended to be computed by an offline device; this prevents side channel attacks and eavesdropping by malware. Unlike the original Enigma, E2K uses modern cryptographic algorithms; this provides secure encryption. E2K is intended for encrypted communication between humans only, and therefore it encrypts and decrypts plaintexts and ciphertexts consisting only of the English letters A through Z plus a few other characters. E2K uses a nonce in addition to the secret key, and requires that different messages use unique nonces. E2K performs authenticated encryption, and optional header data can be included in the authentication. This paper defines the E2K encryption and decryption algorithms, analyzes E2K’s security, and describes an encryption appliance based on the Raspberry Pi computer for doing E2K encryptions and decryptions offline.

We present a new generic construction of multi-client functional encryption (MCFE) for inner products from single-input functional inner-product encryption and standard pseudorandom functions. In spite of its simplicity, the new construction supports labels, achieves security in the standard model under adaptive corruptions, and can be instantiated from the plain DDH, LWE, and Paillier assumptions. Prior to our work, the only known constructions required discrete-log-based assumptions and the random-oracle model. Since our new scheme is not compatible with the compiler from Abdalla et al. (PKC 2019) that decentralizes the generation of the functional decryption keys, we also show how to modify the latter transformation to obtain a decentralized version of our scheme with similar features.

One of Bitcoin’s core security guarantees is that, for an attacker to be able to successfully interfere with the Bitcoin network and reverse transactions, they need to control 51% of total hash power. Eyal et al., however, significantly reduces Bitcoin’s security guarantee by introducing another type of attack, called "Selfish Mining". The key idea behind selfish mining is for a miner to keep its discovered blocks private, thereby intentionally forking the chain. As a result of a selfish mining attack, even a miner with 25% of the computation power can bias the agreed chain with its blocks. After Eyal's original paper, the concept of selfish mining has been actively studied within the Bitcoin community for several years. This paper studies a fundamental problem regarding the selfish mining strategy under the existence of mining pools. For this, we propose a new attack strategy, called "Detective Mining", and show that selfish mining pool is not profitable anymore when other miners use our strategy.

Event date: 11 November 2019
Submission deadline: 28 June 2019
Notification: 14 August 2019

We have a postdoctoral position in post-quantum cryptography broadly defined. In particular, anyone interested in algorithmic and/or complexity-theoretic aspects of problems relevant in lattice-based, code-based, and multivariate cryptography is welcome to apply.

The position comes with an internationally competitive salary and generous support for travel. Moreover, there are ample opportunities to collaborate with excellent scientists both based at CQT/NUS and research visitors.

Closing date for applications: 31 October 2019

Contact: Divesh Aggarwal

Assistant Professor, NUS, and Principal Investigator, CQT (joint appointment)

divesh.aggarwal (at) gmail.com

CEA list is looking for a talented student to explore robustness and privacy of graph-neural network based approaches, by considering solutions combining randomization and homomorphic encryption. See https://gouypailler.github.io/files/phdCryptoRobust.pdf for details.

CEA background in these fields

==============================

CEA LIST has been a key leader in fully homomorphic encryption techniques https://github.com/CEA-LIST/Cingulata. In the context of FHE, machine learning applications appear as a killer application. Many key advances have yet to be considered to fully address machine learning applications using FHE technologies. Next technological barriers depend on the computational cost of the considered stage (training or inference) but the main approaches are: first to limit operators used in graph neural networks such that FHE associated computational cost is kept reasonable. Second FHE can be viewed as a building block, which could be activated in specific parts of the pipeline to ensure model or data privacy. CEA LIST is also very active in the field of randomization algorithms to ensure data privacy and robustness to adversarial attacks. Past works include PhD thesis of Anne Morvan and Rafael Pinot.

Closing date for applications: 15 June 2019

Contact: Cedric Gouy-Pailler (cedric.gouy-pailler (at) cea.fr) or Renaud Sirdey

More information: https://gouypailler.github.io/files/phdCryptoRobust.pdf

A recent NFS attack against pairings made it necessary to increase the key sizes of the most popular families of pairings : BN, BLS12, KSS16, KSS18 and BLS24. The attack applies to other families of pairings but not to all. In this paper we compute the key sizes required for more than 150 families of pairings to verify if there are any other families which are better than BN. The security estimation is not straightforward because it is not a mathematical formula, but rather one has to instantiate the Kim-Barbulescu attack by proposing polynomials and parameters.

After estimating the practical security of an extensive list of families, we compute the complexity of the optimal Ate pairing at 128 and 192 bits of security. For some of the families the optimal Ate has never been studied before. We show that a number of families of embedding degree 9, 14 and 15 are very competitive with $BN$, $BLS12$ and $KSS16$ at 128 bits of security. We identify a set of candidates for 192 bits and 256 bits of security.

This paper introduces new p^rq-based one-way functions and companion signature schemes. The new signature schemes are interesting because they do not belong to the two common design blueprints, which are the inversion of a trapdoor permutation and the Fiat-Shamir transform. In the basic signature scheme, the signer generates multiple RSA-like moduli n_i = p_i 2q_i and keeps their factors secret. The signature is a bounded-size prime whose Jacobi symbols with respect to the ni's match the message digest. The generalized signature schemes replace the Jacobi symbol with higher-power residue symbols. The case of 8th-power residue symbols is fully detailed along with an efficient implementation thereof. Given of their very unique design the proposed signature schemes seem to be overlooked missing species in the corpus of known signature algorithms

Motivated by the application of delegating computation, we revisit the design of filter permutators as a general approach to build stream ciphers that can be efficiently evaluated in a fully homomorphic manner. We first introduce improved filter permutators that allow better security analyses, instances and implementations than the previously proposed FLIP family of stream ciphers. We also put forward the similarities between these improved constructions and a popular PRG design by Goldreich. Then, we exhibit the relevant cryptographic parameters of two families of Boolean functions, direct sums of monomials and XOR-MAJ functions, which give candidates to instantiate the improved filter permutator paradigm. We develop new Boolean functions techniques to study them, and refine Goldreich's PRG locality bound for this purpose. We give an asymptotic analysis of the noise level of improved filter permutators instances using both kind of functions, and recommend them as good candidates for evaluation with a third-generation FHE scheme. Finally, we propose a methodology to evaluate the performance of such symmetric cipher designs in a FHE setting, which primarily focuses on the noise level of the symmetric ciphertexts (hence on the amount of operations on these ciphertextsthat can be homomorphically evaluated). Evaluations performed with HElib show that instances of improved filter permutators using direct sums of monomials as filter outperform all existing ciphers in the literature based on this criteria. We also discuss the (limited) overheads of these instances in terms of latency and throughput.

We show that a future adversary with access to a quantum computer, historic network traffic protected by WireGuard, and knowledge of a WireGuard user's long-term static public key can likely decrypt many of the WireGuard user's historic messages. We propose a simple, efficient alteration to the WireGuard protocol that mitigates this vulnerability, with negligible additional computational and memory costs. Our changes add zero additional bytes of data to the wire format of the WireGuard protocol. Our alteration provides transitional post-quantum security for any WireGuard user who does not publish their long-term static public key -- it should be exchanged out-of-band.

In this paper we give an efficient and compact reformulation of NIST collision estimate test given in SP-800 90B. We correct an error in the formulation of the test and show that the test statistic can be computed in a much easier way. We also propose a revised algorithm for the test based on our findings.