International Association
for Cryptologic Research

About the Department

Cloudflare’s Technology team is working on building the future of Cloudflare by tackling strategic projects that have a large impact on the way Cloudflare systems, and the Internet at large, work. Engineers in the Technology team are expected to research new ideas and technologies, dive into existing codebases to make meaningful changes, work independently on greenfield projects, and collaborate closely with the engineering organization to achieve common goals.

The Cryptography team is a sub-team of the Technology team focused on solving difficult problems in security, performance, and privacy at scale using cryptographic tools. This involves systems engineering, open source software development, protocol design, the implementation of cryptographic primitives, contributions to cutting-edge research in collaboration with academia, participation in Internet standards organizations like the IETF, and more.

Closing date for applications: 1 July 2019

Contact: Nick Sullivan

More information: https://www.cloudflare.com/careers/departments/technology-research/

DTU Compute\'s Section for Cyber Security, invites applications for an appointment as Associate Professor/Assistant Professor within cryptology. The position is available from May 1, 2019 or according to mutual agreement.

The department, DTU Compute, is an internationally unique academic environment spanning the science disciplines mathematics, statistics and computer science. At the same time, we are an engineering department covering informatics and communication technologies (ICT) in their broadest sense. Finally, we play a major role in addressing the societal challenges of the digital society where ICT is a part of every industry, service, and human endeavor.

Responsibilities and tasks

Through the position, the University seeks to strengthen the research within cyber security. The cyber security section at DTU has experts in cryptology, in particular the design and analysis of ciphers and hash functions, but wishes to further strengthen its research within cryptology.

Topics of particular interest include but are not limited to:

• symmetric cryptology

• lightweight and resource-efficient cryptography

• post-quantum cryptology

• provable security of cryptographic primitives

• side-channel attacks and physical cryptanalysis

• analysis and protection of cryptographic implementations

• algorithmic aspects of cryptology

• efficient implementation of cryptographic primitives

Candidates with strong expertise in any other area of cryptology are also encouraged to apply.

Application procedure

To apply, please read the full job advertisement at www.career.dtu.dk

Please submit your online application no later than 1 December 2018.

Closing date for applications: 31 December 2018

We are looking for research fellows with expertise on blockchain and PKC, and offer a competitive salary. If you are interested, please send your CV to Prof. Jianying Zhou . Only short-listed candidates will be contacted for interview.

Closing date for applications: 8 January 2019

Contact: Prof. Jianying Zhou

Email: jianying_zhou (at) sutd.edu.sg

More information: http://jianying.space/

At the Graz University of Technology / Faculty of Computer Science and Biomedical Engineering the position of

University Professor of Information Security

is to be filled at the institute of Applied Information Processing and Communications (IAIK) as a full time permanent position according to section 98 of the Austrian Universities Act (§98 UG). IAIK is an internationally visible research center at TU Graz where more than 60 researchers work on a multitude of topics in information security.

We are seeking a candidate with proven scientific expertise who will represent the field of Information Security in research and teaching. The successful candidate will complement existing strengths at the institute and be an engaged teacher in the Computer Science programs at the bachelor, master, and PhD level.

Closing date for applications: 3 December 2018

Contact: Stefan Mangard, Email: Stefan.Mangard (at) iaik.tugraz.at

More information: https://www.tugraz.at/fakultaeten/infbio/news/vacancies/professor-of-information-security/

A conjunction is a function $f(x_1,\dots,x_n) = \bigwedge_{i \in S} l_i$ where $S \subseteq [n]$ and each $l_i$ is $x_i$ or $\neg x_i$. Bishop et al. (CRYPTO 2018) recently proposed obfuscating conjunctions by embedding them in the error positions of a noisy Reed-Solomon codeword and encoding the codeword in a group exponent. They prove distributional virtual black box (VBB) security in the generic group model for random conjunctions where $|S| \geq 0.226n$. While conjunction obfuscation was known from LWE due to Wichs and Zirdelis (FOCS 2017) and Goyal et al. (FOCS 2017), these constructions rely on substantial technical machinery.

In this work, we conduct an extensive study of simple conjunction obfuscation techniques.

- We abstract the Bishop et al. scheme to obtain an equivalent yet more efficient "dual'' scheme that can handle conjunctions over exponential size alphabets. This scheme admits a straightforward proof of generic group security, which we combine with a novel combinatorial argument to obtain distributional VBB security for $|S|$ of any size.

- If we replace the Reed-Solomon code with a random binary linear code, we can prove security from standard LPN and avoid encoding in a group. This addresses an open problem posed by Bishop et al. to prove security of this simple approach in the standard model.

- We give a new construction that achieves information theoretic distributional VBB security and weak functionality preservation for $|S| \geq n - n^\delta$ and $\delta < 1$. Assuming discrete log and $\delta < 1/2$, we satisfy a stronger notion of functionality preservation for computationally bounded adversaries while still achieving information theoretic security.

Linear cryptanalysis considers correlations between linear input and output combiners for block ciphers and stream ciphers. Daeman and Rijmen (2007) had obtained the distributions of the correlations between linear input and output combiners of uniform random functions and uniform random permutations. Our first contribution is to generalise these results to obtain the distributions of the correlations between arbitrary input and output combiners of uniform random functions and uniform random permutations. Recently, Todo et al. (2018) have proposed nonlinear invariant attacks which consider correlations between nonlinear input and output combiners for a key-alternating block cipher. In its basic form, a nonlinear invariant attack is a distinguishing attack. The second and the main contribution of this paper is to obtain precise expressions for the errors of nonlinear invariant attacks in distinguishing a key-alternating cipher from either a uniform random function or a uniform random permutation.

Physical attacks, especially side-channel attacks, are threats to IoT devices which are located everywhere in the field. For these devices, the authentic functionality is important so that the IoT system becomes correct, and securing this functionality against side-channel attacks is one of our emerging issues. Toward that, Coron et al. gave an efficient arithmetic-to-Boolean mask conversion algorithm which enables us to protect cryptographic algorithms including arithmetic operations, such as hash functions, from the attacks. Recently, Biryukov et al. improved it by locally optimizing subroutines of the conversion algorithm. In this paper, we revisit the algorithm. Unlike Biryukov et al., we improve the Coron et al.'s algorithm with integrative optimizations over the subroutines. The gains against these algorithms are about $22.6\%$ and $7.0\%$ in the general setting. We also apply our algorithm to HMAC-SHA-1 and have an experiment to show that the implementation on a test vehicle smartcard leaks no sensitive information with the ISO/IEC17825 test.

Multilevel and compartmented access structures are two important classes of access structures where participants are grouped into levels/compartments with different degrees of trust and privileges. The construction of secret sharing schemes for such access structures has been in the attention of researchers for a long time. Two main approaches have been taken so far: one of them is based on polynomial interpolation and the other one is based on the Chinese Remainder Theorem (CRT).

In this paper we propose the first asymptotically ideal CRT-based secret sharing schemes for (disjunctive, conjunctive) multilevel and compartmented access structures. Our approach is compositional and it is based on a variant of the Asmuth-Bloom secret sharing scheme where some participants may have public shares. Based on this, we show that the proposed secret sharing schemes for multilevel and compartmented access structures are asymptotically ideal if and only if they are based on 1-compact sequences of co-primes.

The quantum secure supersingular isogeny Diffie-Hellman (SIDH) key exchange is a promising candidate in NIST's on-going post-quantum standardization process. The evaluation of various implementation characteristics is part of this standardization process, and includes the assessment of the applicability on constrained devices. When compared to other post-quantum algorithms, SIDH appears to be well-suited for the implementation on those constrained devices due to its small key sizes. On the other hand, SIDH is computationally complex, which presumably results in long computation times. Since there are no published results to test this assumption, we present speed-optimized implementations for two small microcontrollers and set a first benchmark that can be of relevance for the standardization process. We use state-of-the art field arithmetic algorithms and optimize them in assembly. However, an ephemeral key exchange still requires more than 18 seconds on a 32-bit Cortex-M4 and more than 11 minutes on a 16-bit MSP430. Those results show that even with an improvement by a factor of 4, SIDH is in-fact impractical for small embedded devices, regardless of further possible improvements in the implementation. On a positive note, we also analyzed the implementation security of SIDH and found that appropriate DPA countermeasures can be implemented with little overhead.

The technology of homomorphic encryption has improved rapidly in a few years. The cutting edge implementations are efficient enough to use in practical applications. Recently, Cheon et al. (ASIACRYPT'17) proposed a homomorphic encryption scheme which supports an arithmetic of approximate numbers over encryption. This scheme shows the current best performance in computation over the real numbers, but its implementation could not employ core optimization techniques based on the Residue Number System (RNS) decomposition and the Number Theoretic Transformation (NTT).

In this paper, we present a variant of approximate homomorphic encryption which is optimal for implementation on standard computer system. We first introduce a new structure of ciphertext modulus which allows us to use both the RNS decomposition of cyclotomic polynomials and the NTT conversion on each of the RNS components. We also suggest new approximate modulus switching procedures without any RNS composition. Compared to previous exact algorithms requiring multi-precision arithmetic, our algorithms can be performed by using only word size (64-bit) operations.

Our scheme achieves a significant performance gain from its full RNS implementation. For example, compared to the earlier implementation, our implementation showed speed-ups 17.3, 6.4, and 8.3 times for decryption, constant multiplication, and homomorphic multiplication, respectively, when the dimension of a cyclotomic ring is 32768. We also give experimental result for evaluations of some advanced circuits used in machine learning or statistical analysis. Finally, we demonstrate the practicability of our library by applying to machine learning algorithm. For example, our single core implementation takes 1.8 minutes to build a logistic regression model from encrypted data when the dataset consists of 575 samples, compared to the previous best result 3.5 minutes using four cores.

ElGamal cryptosystem is typically developed in the multiplicative group $\mathbb{Z}_p^*$ ($p$ is a prime number), but it can be applied to the other groups in which discrete logarithm problem should be computationally infeasible. Practically, instead of ElGamal in $\mathbb Z_p^*$, various variants such as ECElGamal (ElGamal in elliptic curve group), CRTElGamal (ElGamal in subgroup of $\mathbb Z_n^*$ where $n=pq$ and $p,q,(p-1)/2,(q-1)/2$ are primes) have already been used for the semantic security. In this paper, for the fast decryption, we reduced the private CRT exponent $x_p$ ($= x mod (p - 1)$) and $x_q$ ($= x mod (q-1)$)maintaining full sized private exponent $x$ ($0<x<n$) in CRTElGamal as reducing $d_p$ ($= d mod (p - 1)$) and $d_q$ ($= d mod (q-1)$) in RSA for the fast decryption. (i.e. as in rebalanced RSA). In this case, unlike rebalanced RSA, decryption of CRTElGamal can be done faster without losing of encryption speed. As a result, it is possible to propose the fast public key cryptosystem that has fast encryption and fast decryption.

Any $d$-regular graph on $n$ vertices with spectral expansion $\lambda$ satisfying $n = \Omega(d^3\log(d)/\lambda)$ yields a $O\left(\frac{\lambda^{3/2}}{d}\right)$-non-malleable code in the split-state model.

We propose FO-AKE , a generic construction of two-message authenticated key exchange (AKE) from any passively secure public key encryption (PKE) in the quantum random oracle model (QROM). Whereas previous AKE constructions relied on a Diffie-Hellman key exchange or required the underlying PKE scheme to be perfectly correct, our transformation allows arbitrary PKE schemes with non-perfect correctness. Furthermore, we avoid the use of (quantum-secure) digital signature schemes which are considerably less efficient than their PKE counterparts. As a consequence, we can instantiate our AKE transformation with any of the submissions to the recent NIST post-quantum competition, e.g., ones based on codes and lattices. FOAKE can be seen as a generalization of the well known Fujisaki-Okamoto transformation (for building actively secure PKE from passively secure PKE) to the AKE setting. Therefore, as a helper result, we also provide an alternative security proof for the Fujisaki-Okamoto transformation in the QROM that deals with possible correctness errors.

In distributed pseudorandom functions (DPRFs), a PRF secret key $SK$ is secret shared among $N$ servers so that each server can locally compute a partial evaluation of the PRF on some input $X$. A combiner that collects $t$ partial evaluations can then reconstruct the evaluation $F(SK,X)$ of the PRF under the initial secret key. So far, all non-interactive constructions in the standard model are based on lattice assumptions. One caveat is that they are only known to be secure in the static corruption setting, where the adversary chooses the servers to corrupt at the very beginning of the game, before any evaluation query. In this work, we construct the first fully non-interactive adaptively secure DPRF in the standard model. Our construction is proved secure under the LWE assumption against adversaries that may adaptively decide which servers they want to corrupt. We also extend our construction in order to achieve robustness against malicious adversaries.

Motivated by the potential cryptographic application of building a directed transitive signature scheme, the search for a group with infeasible inversion was initiated in the theses of Hohenberger and Molnar in 2003. Later it was also shown to provide a broadcast encryption scheme by Irrer et al. (2004). However, to date the only case of a group with infeasible inversion is implied by the much stronger primitive of self-bilinear map constructed by Yamakawa et al. (2014) based on the hardness of factoring and indistinguishability obfuscation (iO).

We propose a candidate trapdoor group with infeasible inversion without using the heavy machinery of iO. The underlying group is isomorphic to the ideal class group of an imaginary quadratic order, and is represented by the elliptic curve isogeny graph. The hardness of group inversion relies on the conjectured hardness of several problems on the isogeny graphs defined over composite moduli with unknown factorization.

Today’s blockchains do not scale in a meaningful sense. As more nodes join the system, the efficiency of the system (computation, communication, and storage) degrades, or at best stays constant. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. We observe that sharding is similar to replication coding, which is known to be inefficient and fragile in the coding theory community. In this paper, we demonstrate a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: “polynomially coded sharding” scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

We introduce the forward secure signature scheme XMSS$^{+}$ and present an implementation for smart cards. It is based on the hash-based signature scheme XMSS. In contrast to the only previous implementation of a hash-based signature scheme on smart cards by Rohde et al., we solve the problem of on-card key generation. Compared to XMSS, we reduce the key generation time from $\mathcal{O}(n)$ to $\mathcal{O}(\sqrt{n})$, where $n$ is the number of signatures that can be created with one key pair. To the best of our knowledge this is the first implementation of a forward secure signature scheme and the first full implementation of a hash-based signature scheme on smart cards. The resulting runtimes are comparable to those of RSA and ECDSA on the same device. This shows the practicality of forward secure signature schemes, even on constrained devices.

In a delegatable anonymous credential system, participants may use their credentials anonymously as well as anonymously delegate them to other participants. Such systems are more usable than traditional anonymous credential systems because a popular credential issuer can delegate some of its responsibilities without compromising users' privacy. They also provide stronger privacy guarantees than traditional anonymous credential systems because the identities of credential issuers are hidden. The identity of a credential issuer may convey information about a user's identity even when all other information about the user is concealed.

The only previously known constructions of delegatable anonymous credentials were prohibitively inefficient. They were based on non-interactive zero-knowledge (NIZK) proofs. In this paper, we provide a simple construction of delegatable anonymous credentials and prove its security in the generic group model. Our construction is direct, not based on NIZK proofs, and is therefore considerably more efficient. In fact, in our construction, only five group elements are needed per link to represent an anonymous credential chain.

Our main building block is a new type of signature scheme, a mercurial signature, which allows a signature $\sigma$ on a message $M$ under public key $\mathsf{pk}$ to be transformed into a signature $\sigma'$ on an equivalent but unlinkable message $M'$ under an equivalent but unlinkable public key $\mathsf{pk}'$.

Threshold implementations have emerged as one of the most popular masking countermeasures for hardware implementations of cryptographic primitives. In the original version of TI, the number of input shares was dependent on both security order $d$ and algebraic degree of a function $t$, namely $td + 1$. At CRYPTO 2015, a new method was presented yielding to a $d$-th order secure implementation using $d+1$ input shares. In this work, we first provide a construction for $d+1$ TI sharing which achieves the minimal number of output shares for any $n$-input Boolean function of degree $t=n-1$. Furthermore, we present a heuristic for minimizing the number of output shares for higher order $td + 1$ TI. Finally, we demonstrate the applicability of our results on $d+1$ and $td+1$ TI versions, for first- and second-order secure, low-latency and low-energy implementations of the PRINCE block cipher.

Motivatedbytheoreticalandpracticalconsiderations,anim- portant line of research is to design secure computation protocols that only make black-box use of cryptography. An important component in nearly all the black-box secure computation constructions is a black- box commit-and-prove protocol. A commit-and-prove protocol allows a prover to commit to a value and prove a statement about this value while guaranteeing that the committed value remains hidden. A black- box commit-and-prove protocol implements this functionality while only making black-box use of cryptography. In this paper, we build several tools that enable constructions of round- optimal, black-box commit and prove protocols. In particular, assuming injective one-way functions, we design the first round-optimal, black- box commit-and-prove arguments of knowledge satisfying strong privacy against malicious verifiers, namely: – Zero-knowledge in four rounds and, – Witness indistinguishability in three rounds. Prior to our work, the best known black-box protocols achieving commit- and-prove required more rounds. We additionally ensure that our protocols can be used, if needed, in the delayed-input setting, where the statement to be proven is decided only towards the end of the interaction. We also observe simple applications of our protocols towards achieving black-box four-round constructions of extractable and equivocal commitments. We believe that our protocols will provide a useful tool enabling several new constructions and easy round-efficient conversions from non-black- box to black-box protocols in the future.