International Association
for Cryptologic Research

It is well established that the method of choice for implementing a side-channel secure modular inversion, is to use Fermat's little theorem. So $1/x = x^{p-2} \bmod p$. This can be calculated using any multiply-and-square method safe in the knowledge that no branching or indexing with potentially secret data (such as $x$) will be required. However in the case where the modulus $p$ is a pseudo-Mersenne, or Mersenne, prime of the form $p=2^n-c$, where $c$ is small, this process can be optimized to greatly reduce the number of multiplications required. Unfortunately an optimal solution must it appears be tailored specifically depending on $n$ and $c$. What appears to be missing from the literature is a near-optimal heuristic method that works reasonably well in all cases.

Signal is a famous secure messaging protocol used by billions of people, by virtue of many secure text messaging applications including Signal itself, WhatsApp, Facebook Messenger, Skype, and Google Allo. At its core it uses the concept of "double ratcheting," where every message is encrypted and authenticated using a fresh symmetric key; it has many attractive properties, such as forward security, post-compromise security, and "immediate (no-delay) decryption," which had never been achieved in combination by prior messaging protocols.

While the formal analysis of the Signal protocol, and ratcheting in general, has attracted a lot of recent attention, we argue that none of the existing analyses is fully satisfactory. To address this problem, we give a clean and general definition of secure messaging, which clearly indicates the types of security we expect, including forward security, post-compromise security, and immediate decryption. We are the first to explicitly formalize and model the immediate decryption property, which implies (among other things) that parties seamlessly recover if a given message is permanently lost---a property not achieved by any of the recent "provable alternatives to Signal." We build a modular "generalized Signal protocol" from the following components: (a) continuous key agreement (CKA), a clean primitive we introduce and which can be easily and generically built from public-key encryption (not just Diffie-Hellman as is done in the current Signal protocol) and roughly models "public-key ratchets;" (b) forward-secure authenticated encryption with associated data (FS-AEAD), which roughly captures "symmetric-key ratchets;" and (c) a two-input hash function that is a pseudorandom function (resp. generator with input) in its first (resp. second) input, which we term PRF-PRNG. As a result, in addition to instantiating our framework in a way resulting in the existing, widely-used Diffie-Hellman based Signal protocol, we can easily get post-quantum security and not rely on random oracles in the analysis.

We further show that our design can be elegantly extended to include other forms of "fine-grained state compromise" recently studied at CRYPTO'18, but without sacrificing the immediate decryption property. However, we argue that the additional security offered by these modifications is unlikely to justify the efficiency hit of using much heavier public-key cryptography in place of symmetric-key cryptography.

Whether there exist Almost Perfect Non-linear permutations (APN) operating on an even number of bit is the so-called Big APN Problem. It has been solved in the 6-bit case by Dillon et al. in 2009 but, since then, the general case has remained an open problem.

In 2016, Perrin et al. discovered the butterfly structure which contains Dillon et al.'s permutation over $\mathbb{F}_{2^6}$. Later, Canteaut et al. generalised this structure and proved that no other butterflies with exponent $3$ can be APN. Recently, Yongqiang et al. further generalized the structure with Gold exponent and obtained more differentially 4-uniform permutations with the optimal nonlinearity. However, the existence of more APN permutations in their generalization was left as an open problem.

In this paper, we adapt the proof technique of Canteaut et al. to handle all Gold exponents and prove that a generalised butterfly with Gold exponents over $\mathbb{F}_{2^{2n}}$ can never be APN when $n>3$. More precisely, we prove that such a generalised butterfly being APN implies that the branch size is strictly smaller than 5. Hence, the only APN butterflies operate on 3-bit branches, i.e. on 6 bits in total.

In this paper we focus on Polynomial Learning with Errors (PLWE). This problem is parametrized by a polynomial and we are interested in relating the hardness of the $\text{PLWE}^f$ and $\text{PLWE}^h$ problems for different polynomials $f$ and $h$. More precisely, our main result shows that for a fixed monic polynomial $f$, $\text{PLWE}^{f\circ g}$ is at least as hard as $\text{PLWE}^f$, in both search and decision variants, for any monic polynomial $g$. As a consequence, $\text{PLWE}^{\phi_n}$ is harder than $\text{PLWE}^{f},$ for a minimal polynomial $f$ of an algebraic integer from the cyclotomic field $\mathbb{Q}(\zeta_n)$ with specific properties. Moreover, we prove in decision variant that in the case of power-of-2 polynomials, $\text{PLWE}^{\phi_n}$ is at least as hard as $\text{PLWE}^f,$ for a minimal polynomial $f$ of algebraic integers from the $n$th cyclotomic field with weaker specifications than those from the previous result.

We show how to build distributed key generation and distributed decryption procedures for the LIMA Ring-LWE based post-quantum cryptosystem. Our protocols implement the CCA variants of distributed decryption and are actively secure (with abort) in the case of three parties and honest majority. Our protocols make use of a combination of problem specific MPC protocols, generic garbled circuit based MPC and generic Linear Secret Sharing based MPC. We also, as a by-product, report on the first run-times for the execution of the SHA-3 function in an MPC system.

We propose two one-round authenticated group-key exchange protocols from newly employed cryptographic invariant maps (CIMs): one is secure under the quantum random oracle model and the other resists against maximum exposure where a non-trivial combination of secret keys is revealed. The security of the former (resp. latter) is proved under the n-way decisional Diffie-Hellman (resp. n-way gap Diffie-Hellman) assumption on the CIMs in the quantum random (resp. random) oracle model. We instantiate the proposed protocols on the hard homogeneous spaces with limitation where the number of the user group is two. In particular, the protocols instantiated by using the CSIDH, commutative supersingular isogeny Diffie-Hellman, key exchange are currently more realistic than the general n-party CIM-based ones due to its implementability. Our two-party one-round protocols are secure against quantum adversaries.

Homomorphic encryption has the purpose to allow computations on encrypted data, without the need for decryption other than that of the final result. This could provide an elegant solution to the problem of privacy preservation in data-based applications, such as those provided and/or facilitated by machine learning techniques, but several limitations and open issues hamper the fulfillment of this plan. In this work we assess the possibility for homomorphic encryption to fully implement its program without the need to rely on other techniques, such as multiparty computation, which may be impossible in many actual use cases (for instance due to the high level of communication required). We proceed in two steps: i) on the basis of the well-known structured program theorem [Bohm and Jacopini] we identify the relevant minimal set of operations homomorphic encryption must be able to perform to implement any algorithm; and ii) we analyse the possibility to solve -and propose an implementation for- the most fundamentally relevant issue as it emerges from our analysis, that is, the implementation of conditionals (which in turn require comparison and selection/jump operations) in full homomorphic encryption. We show how this issue has a serious impact and clashes with the fundamental requirements of homomorphic encryption. This could represent a drawback for its use as a complete solution in data analysis applications, in particular machine learning. It will thus possibly require a deep re-thinking of the homomorphic encryption program for privacy preservation.

We note that our approach to comparisons is novel, and for the first time completely embedded in homomorphic encryption, differently from what proposed in previous studies (and beyond that, we supplement it with the necessary selection/jump operation). A number of studies have indeed dealt with comparisons, but have not managed to perform them in pure homomorphic encryption. Typically their comparison protocols do not utilise homomorphic encryption for the comparison itself, but rely on other cryptographic techniques, such as secure multiparty computation, which a) require a high level of communication between parties (each single comparison in a machine learning training and prediction process must be performed by exchanging several messages), which may not be possible in various use cases, and b) required the data owner to decrypt intermediate results, extract significant bits for the comparison, re-encrypt and send the result back to the other party for the accomplishment of the algorithm. Such ``decryption'' in the middle foils the purpose of homomorphic encryption. Beside requiring only homomorphic encryption, and not any intermediate decryption, our protocol is also provably safe (as it shares the same safety as the homomorphic encryption schemes), differently from other techniques such as OPE/ORE and variations, which have been proved not secure.

The efficient verification of the security of masked hardware implementations is an important issue that hinders the development and deployment of randomness-efficient masking techniques. At EUROCRYPT 2018, Bloem et al. [6] introduced the first practical formal tool to prove the side-channel resilience of masked circuits in the probing model with glitches. Most recently Barthe et al.[2] introduced a more efficient formal tool that builds upon the findings of Bloem et al. for modeling the effects of glitches. While Barthe et al.'s approach greatly improves the first-order verification performance, it shows that higher-order verification in the probing model with glitches is still enormously time-consuming for larger circuits like a second-order AES S-box, for instance. Furthermore, the results of Barthe et al. underline the discrepancy between state-of-the-art formal security notions that allow for faster verification of circuits. Namely the strong non-interference (SNI) notion, and existing masked hardware implementations that are secure in the probing model with glitches. In this work, we extend and improve the formal approaches of Bloem et al. and Barthe et al. on manifold levels. We first introduce a so-called sharing independence notion which helps to reason about the independence of shared variables. We then show how to use this notion to test for the independence of input and output sharings of a module which allows speeding up the formal verification of circuits that do not fulfill the SNI notion. With this extension, we are for the time able to verify the security of a second-order masked DOM AES S-box which takes about 3 seconds, and up to a fifth-order AES S-box which requires about 47 days for verification. Furthermore, we discuss in which case the independence of input and output sharings lead to composability.

In Sweden, a phd studentship is a paid full-time job, with a salary, annual leave and all other social and medical benefits.

We are hiring one phd student to work on (acoustic) side channels, automotive security, or cybercrime at Linköping University.

Candidates with a solid MSc in security or applied crypto are welcome to apply.

PI profile: https://scholar.google.com/citations?hl=en&user=rYhiAEUAAAAJ&view_op=list_works&sortby=pubdate

Closing date for applications: 30 November 2018

Contact: Prof Jeff Yan (jeff.yan (at) liu.se)

The Strategic Centre for Research in Privacy-Preserving Technologies & Systems (SCRIPTS) of Nanyang Technological University in Singapore is the one-stop centre for knowledge, technologies, and solutions for privacy-preserving problems. We seek highly motivated researchers to fill several R&D positions ranging from fresh postdoc research fellows to senior research scientists in the areas including but not limited to Fully Homomorphic Encryption (FHE), Multi-Party Computation (MPC), Searchable Encryptions (SE), and Differential Privacy (DP). The successful applicants are expected to have either proven record of top publications (IACR conferences, S&P, CCS, Usenix, NDSS) or strong systems research experiences and software development skills in these areas.

We offer a globally competitive salary package and low income tax, plus an excellent research environment in Singapore. The initial contract will be for 2 years, and renewable for up to 5 years subject to the performance. Interested candidates are to send their CV, and 2 reference letters to Jian Guo. Review of application will start immediately until the positions are filled.

Closing date for applications: 31 March 2019

Contact: Asst Prof. Jian Guo, guojian (at) ntu.edu.sg

The notion of Registration-Based Encryption (RBE) was recently introduced by Garg, Hajiabadi, Mahmoody, and Rahimi [TCC'18] with the goal of removing the private-key generator (PKG) from IBE. Specifically, RBE allows encrypting to identities using a (compact) master public key, like how IBE is used, with the benefit that the PKG is substituted with a weaker entity called "key curator" who has no knowledge of any secret keys. Here individuals generate their secret keys on their own and then publicly register their identities and their corresponding public keys to the key curator. Finally, individuals obtain "rare" decryption-key updates from the key curator as the population grows. In their work, they gave a construction of RBE schemes based on the combination of indistinguishability obfuscation and somewhere statistically binding hash functions. However, they left open the problem of constructing RBE schemes based on standard assumptions.

In this work, we resolve the above problem and construct RBE schemes based on standard assumptions (e.g., CDH or LWE). Furthermore, we show a new application of RBE in a novel context. In particular, we show that anonymous variants of RBE (which we also construct under standard assumptions) can be used for realizing abstracts forms of anonymous messaging tasks in simple scenarios in which the parties communicate by writing messages on a shared board in a synchronized way.

In this paper, we propose a new general construction to reduce the public key size of McEliece-based schemes based on Goppa codes. In particular, we generalize the ideas of automorphism-induced Goppa codes by considering nontrivial subsets of automorphism groups to construct Goppa codes with a nice block structure. By considering additive and multiplicative automorphism subgroups, we provide explicit constructions to demonstrate our technique. In addition, we show that our technique can be applied to automorphism-induced Goppa codes to further reduce their key sizes.

We present new protocols for Byzantine agreement in the synchronous and authenticated setting, tolerating the optimal number of $f$ faults among $n=2f+1$ parties. Our protocols achieve an expected $O(1)$ round complexity and an expected $O(n^2)$ communication complexity. The exact round complexity in expectation is 10 for a static adversary and 16 for a strongly rushing adaptive adversary. For comparison, previous protocols in the same setting require expected 29 rounds and expected $\Omega(n^4)$ communication. We also give a lower bound showing that expected $\Omega(n^2)$ communication is necessary against a strongly rushing adaptive adversary.

Inspired by Maurer's universal zero knowledge (UZK) abstract perspective and building on legally fair contract signing protocols without keystones, we propose and analyze the security of the first UZK class of co-signing protocols. We construct our main idea considering the stringent issue of scheme compatibility which characterizes communication systems. Typical examples are the cases of certificates in a public key infrastructure and the general issue of upgrading the version of a system. Thus, working in a general framework may reduce implementation errors and save application development and maintenance time.

This paper presents ecient formulas to compute Miller doubling and Miller addition utilizing degree-3 twists on curves with j-invariant 0 written in Hessian form. We give the formulas for both odd and even embedding degrees and for pairings on both $\mathbb{G}_1\times\mathbb{G}_2$ and $\mathbb{G}_2\times\mathbb{G}_1$. We propose the use of embedding degrees 15 and 21 for 128-bit and 192-bit security respectively in light of the NFS attacks and their variants. We give a comprehensive comparison with other curve models; our formulas give the fastest known pairing computation for embedding degrees 15, 21, and 24.

We construct an integer matrices encryption scheme based on binary matrices encryption scheme proposed in [9], and support homomorphic addition and multiplication operations, we prove the correctness and analyze the security. Besides, we implement four encryption schemes in- cluding public-key and symmetric-key binary matrices encryption schemes from [9], and public-key and symmetric-key integer matrices encryption schemes from this work. The experimental results show that the running time of homomorphic multiplycation just costs 0.32sec for 40 times 40 integer matrices, it provides a promising prospect for application. Finally,we apply integer matrices encryption into graph theory to homomorphiclly solve a problem that the number of length-k walks between any two vertices, the algorithm shows the effectiveness.

Cryptocurrencies record transactions between parties in a blockchain maintained by a peer-to-peer network. In most cryptocurrencies, transactions explicitly identify the previous transaction providing the funds they are spending, revealing the amount and sender/recipient pseudonyms. This is a considerable privacy issue. Zerocash resolves this by using zero-knowledge proofs to hide both the source, destination and amount of the transacted funds. To receive payments in Zerocash, how- ever, the recipient must scan the blockchain, testing if each transaction is destined for them. This is not practical for mobile and other bandwidth constrained devices. In this paper, we build ZLiTE, a system that can support the so called "light clients", which can receive transactions aided by a server equipped with a Trusted Execution Environment. Even with the use of a TEE, this is not a trivial problem. First, we must ensure that server processing the blockchain does not leak sensitive information via side channels. Second, we need to design a bandwidth efficient mechanism for the client to keep an up-to-date version of the witness needed in order to spend the funds they previously received.

Profiled side-channel attacks based on deep learning, and more precisely Convolutional Neural Networks, is a paradigm showing significant potential. The results, although scarce for now, suggest that such techniques are even able to break cryptographic implementations protected with countermeasures. In this paper, we start by proposing a new Convolutional Neural Network instance that is able to reach high performance for a number of considered datasets. Additionally, for a dataset protected with the random delay countermeasure, our neural network is able to break the implementation by using only 2 traces in the attack phase. We compare our neural network with the one designed for a particular dataset with masking countermeasure and we show how both are good designs but also how neither can be considered as a superior to the other one. Next, we address how the addition of artificial noise to the input signal can be actually beneficial to the performance of the neural network. Such noise addition is equivalent to the regularization term in the objective function. By using this technique, we are able to improve the number of measurement needed to reveal the secret key by orders of magnitude in certain scenarios for both neural networks. To strengthen our experimental results, we experiment with a number of datasets which differ in the levels of noise (and type of countermeasure) where we show the viability of our approaches.

We explore how to build a blind certificate authority (CA). Unlike conventional CAs, which learn the exact identity of those registering a public key, a blind CA can simultaneously validate an identity and provide a certificate binding a public key to it, without ever learning the identity. Blind CAs would therefore allow bootstrapping truly anonymous systems in which no party ever learns who participates. In this work we focus on constructing blind CAs that can bind an email address to a public key.

To do so, we first introduce secure channel injection (SCI) protocols. These allow one party (in our setting, the blind CA) to insert a private message into another party's encrypted communications. We construct an efficient SCI protocol for communications delivered over TLS, and use it to realize anonymous proofs of account ownership for SMTP servers. Combined with a zero-knowledge certificate signing protocol, we build the first blind CA that allows Alice to obtain a X.509 certificate binding her email address alice@domain.com to a public key of her choosing without ever revealing ``alice'' to the CA. We show experimentally that our system works with standard email server implementations as well as Gmail.

Videos from CHES 2018 are now online at the IACR Youtube channel. See https://www.youtube.com/user/TheIACR