International Association
for Cryptologic Research

It has been 70 years since the publication of the seminal outstanding work of Claude Elwood Shannon, in which he first gave a mathematical definition of the cryptosystem and introduced the concept of perfect ciphers. He also examined the conditions in which such a ciphers exist. Shannon's results in one form or another are presented in almost all books on cryptography. One of his result deals with so-called endomorphic ciphers in which the cardinalities of the message space $\mathcal{M}$ and the ciphertexts $\mathcal{C}$ are the same. The Vernam cipher (one-time pad) is the most famous representative of such ciphers. Moreover, it's the only one known to be perfect.

Surprisingly, we have found a mistake in the Shannon's result. Namely, Shannon stated that an endomorphic cipher, in which the keyspace $\mathcal{K}$ has the same cardinality as message space, is perfect if and only if two conditions are satisfied. The first suggests that for any pair plaintext - ciphertext there exists only one key that translates this plaintext into this ciphertext. The second argues that the key distribution must be uniform. We show, that these two conditions are not really enough. We prove in three different ways that the plaintexts must also be equally probable. Moreover, we study the general endomorphic cipher and get the same result. It follows, that in practice perfect endomorphic ciphers do not exist.

The Feistel construction is one of the most studied ways of building block ciphers. Several generalizations were then proposed in the literature, leading to the Generalized Feistel Network, where the round function first applies a classical Feistel operation in parallel on an even number of blocks, and then a permutation is applied to this set of blocks. In 2010 at FSE, Suzaki and Minematsu studied the diffusion of such construction, raising the question of how many rounds are required so that each block of the ciphertext depends on all blocks of the plaintext. They thus gave some optimal permutations, with respect to this diffusion criteria, for a Generalized Feistel Network consisting of 2 to 16 blocks, as well as giving a good candidate for 32 blocks. Later at FSE'19, Cauchois et al. went further and were able to propose optimal even-odd permutations for up to 26 blocks.

In this paper, we complete the literature by building optimal even-odd permutations for 28, 30, 32, 36 blocks which to the best of our knowledge were unknown until now. The main idea behind our constructions and impossibility proof is a new characterization of the total diffusion of a permutation after a given number of rounds. In fact, we propose an efficient algorithm based on this new characterization which constructs all optimal even-odd permutations for the 28, 30, 32, 36 blocks cases and proves a better lower bound for the 34, 38, 40 and 42 blocks cases. In particular, we improve the 32 blocks case by exhibiting optimal even-odd permutations with diffusion round of 9. The existence of such a permutation was an open problem for almost 10 years and the best known permutation in the literature had a diffusion round of 10. Moreover, our characterization can be implemented very efficiently and allows us to easily re-find all optimal even-odd permutations for up to 26 blocks with a basic exhaustive search.

At ASIACRYPT 2018 it was shown that Statistical Ineffective Fault Attacks (SIFA) pose a threat for many practical implementations of symmetric cryptography. In particular, countermeasures against both power analysis and fault attacks typically do not prevent straightforward SIFA attacks that require very limited knowledge about the concrete attacked implementation. Consequently, the exploration of countermeasures against SIFA that do not rely on protocols or physical protection mechanisms is of particular interest. In this paper, we explore different countermeasure strategies against SIFA. First, we thoroughly analyze the conditions for an attack to be successful. We then show that by building the implementation from invertible building blocks rather than binary gates we can create circuits where a single fault in the computation does not cancel out. This property, when combined with a typical redundancy-based countermeasure, then results in a single-fault SIFA-secure implementation. This approach can be implemented efficiently and we show how it can be applied to 3-bit, 4-bit, and 5-bit S-boxes. Additionally, we also present an alternative countermeasure strategy based on fine-grained detection. Although this approach may lead to a higher implementation cost, it can be used to protect arbitrary circuits and can be generalized to cover multi-fault SIFA.

We present the first practical software implementation of Supersingular Isogeny Key Encapsulation (SIKE) round 2, targeting NIST’s 1, 2, and 5 security levels on 32-bit ARM Cortex-M4 microcontrollers. The proposed library introduces a new speed record of SIKE protocol on the target platform. We achieved this record by adopting several state-of-the-art engineering techniques as well as highly-optimized hand-crafted assembly implementation of finite field arithmetic. In particular, we carefully redesign the previous optimized implementations of filed arithmetic on 32-bit ARM Cortex-M4 platform and propose a set of novel techniques which are explicitly suitable for SIKE/SIDH primes. Moreover, the proposed arithmetic implementations are fully scalable to larger bit-length integers and can be adopted over different security levels. The benchmark result on STM32F4 Discovery board equipped with 32-bit ARM Cortex-M4 microcontrollers shows that the entire key encapsulation over p434 takes about 326 million clock cycles (i.e. 1.94 seconds @168MHz). In contrast to the previous optimized implementation of the isogeny-based key exchange on low-power 32-bit ARM Cortex-M4, our performance evaluation shows feasibility of using SIKE mechanism on the target platform. In comparison to the most of the post-quantum candidates, SIKE requires an excessive number of arithmetic operations, resulting in significantly slower timings. However, its small key size makes this scheme as a promising candidate on low-end microcontrollers in the quantum era by ensuring the lower energy consumption for key transmission than other schemes.

The era of PUFs has been characterized by the efforts put into research and the development of PUFs that are robust against attacks, in particular, machine learning (ML) attacks. In the lack of systematic and provable methods for this purpose, we have witnessed the ever-continuing competition between PUF designers/ manufacturers, cryptanalysts, and of course, adversaries that maliciously break the security of PUFs. This is despite a series of acknowledged principles developed in cryptography and complexity theory, under the umbrella term ``hardness amplification." The goal of studies on the hardness amplification is to build a strongly secure construction out of considerably weaker primitives. This paper aims at narrowing the gap between these studies and hardware security, specifically for applications in the domain of PUFs. To this end, we first review an example of practical efforts made to construct more secure PUFs, namely the concept of rolling PUFs. Based on what can be learned from this and central insights provided by the ML and complexity theory, we propose a new PUF-based scheme built around the idea of using a new function, namely, the Tribes function, which combines the outputs of a set of PUFs to generate the final response. Our theoretical findings are discussed in an exhaustive manner and supported by the results of experiments, conducted extensively on real-world PUFs.

We consider the normalized distribution of the overall running times of some cryptographic algorithms, and what information they reveal about the algorithms. Recent work of Deift, Menon, Olver, Pfrang, and Trogdon has shown that certain numerical algorithms applied to large random matrices exhibit a characteristic distribution of running times, which depends only on the algorithm but are independent of the choice of probability distributions for the matrices. Different algorithms often exhibit different running time distributions, and so the histograms for these running time distributions provide a "time-signature" for the algorithms, making it possible, in many cases, to distinguish one algorithm from another. In this paper we extend this analysis to cryptographic algorithms, and present examples of such algorithms with time-signatures that are indistinguishable, and others with time-signatures that are clearly distinct.

In this work we present a new interactive Zero-Knowledge Argument of knowledge for general arithmetic circuits. Our protocol is based on the ``MPC-in-the-head''-paradigm of Ishai et al. (STOC 2009) and uses MPC with preprocessing such as recently proposed by Katz, Kolesnikov and Wang (ACM CCS 2018). Our argument system uses only symmetric-key primitives and utilizes a version of the so-called SPDZ-protocol which has efficiency benefits for arithmetic circuits compared to other approaches.

Based on specific properties of our protocol we then show how it can be used to construct an efficient Zero-Knowledge Argument of Knowledge for instances of the Short Integer Solution (SIS) problem. We present different protocols that are tailored to specific uses of SIS and show how our solution compares in terms of argument size to existing work. We moreover implemented our Zero-Knowledge argument for SIS and show that using our protocols it is possible to run a complete interactive proof, even for general SIS instances which result in a circuit with $>10^6$ gates, in less than 0.5 seconds. To the best of our knowledge, our construction outperforms all known approaches for the SIS problem with post-quantum security either in terms of computation or communication complexity.

The Department of Computer Science at University of Erlangen-Nuremberg (FAU) invite applications for

10 PhD positions (salary level 13 TV-L) in Computer Science (full time)

within the Research Training Group 2475 \"Cybercrime and Forensic Computing\" funded by the German Research Foundation (DFG) commencing on October 1, 2019.

The Research Training Group aims to systematically analyse research questions arising from the interaction between computer science and criminal law. The principal investigators of this project offer expertise in the following areas:

o Computer security, digital forensic science

o Theoretical computer science (logic, semantics, automata)

o Pattern recognition, image processing, image forensics

o Cryptography

o Hardware-software-co-design

Applicants should have an excellent academic record, hold an MSc or an equivalent university degree in computer science or related disciplines, and have the goal to finish a PhD degree within three years.

Founded in 1743 and situated at the heart of the Nuremberg Metropolitan Region, FAU is a strong research university with an international perspective and one of the largest universities in Germany. FAU’s outstanding research and teaching is reflected in top positions in both national and international rankings, as well as the high amount of DFG funding which its researchers are able to secure.

FAU aims to increase the number of women in scientific positions. Female candidates are therefore particularly encouraged to apply. In case of equal qualifications, candidates with disabilities will take precedence.

Please mention in your application at least two research areas from the above list which you are specifically interested in. Interviews will commence between 3.7.2019 and 12.7.2019 in Erlangen. Further inquiries can be directed to Felix Freiling (felix.freiling (at) fau.de) regarding positions in computer science and Hans Kudlich (hans.kudlich (at) fau.de) regarding positions in law.

Closing date for applications: 12 June 2019

Contact: Felix Freiling (felix.freiling (at) fau.de) regarding positions in computer science and Hans Kudlich (hans.kudlich (at) fau.de) regarding positions in law.

More information: https://cybercrime.fau.de

From 2019 on, the DFG (German Research Foundation) will establish the Cluster of Excellence 2092 \\\"CASA of Large-Scale Adversaries\\\" at Ruhr-Universität Bochum. With the support of approximately 30 million euros - 2025, Bochum will become one of the leading international locations for IT security. The cluster pursues the security against large-scale adversaries, in particular nation-state attackers. The research is characterized by a s approach which, in addition to technical questions, also investigates the interaction of human behavior and IT fields of computer science, cryptography, electrical engineering, mathematics and psychology work together in in Europe. This unparalleled holistic approach of CASA holds the potential for scientific breakthroughs. CASA Institute for IT Security, one of the top research institutions, which has Europe\\\'s largest IT security training pr networks with the scientific communication and industry, and has produced numerous successful cyber securit Society plans to establish the \\\"Max Planck Institute for Cyber Security and Protection of Privacy \\\" in the imm with a particularly stimulating effect on the CASA research. This environment offers excellent working condit and exciting field. In addition, CASA offers a friendly working atmosphere in a young and internationally high institution. We are looking for excellent M.Sc. graduates with outstanding grades and degrees in computer scie mathematics and psychology (preferably with a relationship to technology) or related disciplines. In addition, w outstanding postdoctoral candidates from these fields.

Closing date for applications: 2 June 2019

Contact: Contact: Dr. Patrick Schulte

RUHR-UNIVERSITÄT BOCHUM

Exzellenzcluster CASA / Horst Görtz Institute for IT Security

General Manager

ID 2 / 142

Universitätsstr. 150

44780 Bochum, Germany

Tel: +49-(0)234-32-27722

Email: patrick.schulte (at) rub.de

More information: https://twitter.com/HGI_Bochum/status/1087703387343331329 https://twitter.com/HGI_B /1087703387343331329

We are looking for a research fellow (PostDoc), a research/project associate and a research/project assistant, a to join our group to work on the following topics:

- lattice-based cryptography;

- privacy-preserving cryptographic primitives (including zero-knowledge proofs, anonymous credentials, ring signatures);

- blockchain & cryptocurrency.

Candidates for research fellow/associate should have completed (or close to completing) a PhD in computer science, mathematics, or a related discipline. Research assistant are expected to have an honours degree or an equivalent qualification. Post-secondary students will be considered for the position of research/project administrative assistant.

Applicants should have solid experience in any of the following areas:

- Public key cryptography and provable security;

- post-quantum cryptography;

- Software engineering.

Post-doc applicants should have a good track record (e.g. publications in IACR conferences / workshops)

All positions has a flexible starting date. The initial appointment will be for 12 months, with a strong possibility for further appointment.

Review of applications will start immediately until the positions are filled.

Closing date for applications: 30 September 2019

Contact: Man Ho Au

More information: http://www4.comp.polyu.edu.hk/~csallen

Suppose that there exist a user and $\ell$ servers $S_1, \ldots, S_{\ell}$. Each server $S_j$ holds a copy of a database $x=(x_1, \ldots, x_n) \in \{0,1\}^n$, and the user holds a secret index $i_0 \in \{1, \ldots, n\}$. A b error correcting $\ell$ server PIR (Private Information Retrieval) scheme allows a user to retrieve $x_{i_0}$ correctly even if and $b$ or less servers return false answers while each server learns no information on $i_0$ in the information theoretic sense. Although there exists such a scheme with the total communication cost $O(n^{1/(2k-1)} \times k\ell \log{\ell})$ where $k=\ell-2b$, the decoding algorithm is very inefficient.

In this paper, we show an efficient decoding algorithm for this $b$ error correcting $\ell$ server PIR scheme. It runs in time $O(\ell^3)$.

Many crypto-algorithms, Deep-Learning, DSP compute on words larger than 8-bit. SCA attacks can easily be done on Boolean operations like XOR, AND, OR, and substitution operations like s-box, p-box or q-box, as 8-bit hypothesis or less are enough to forge attacks. However, attacking larger hypothesis word increases exponentially required resources: memory and computation power. Considering multiplication, 32-bit operation implies $2^{32}$ hypothesis. Then a direct SCA attack cannot be efficiently performed. We propose to perform instead 4 small 8-bit SCA attacks. 32-bit attack complexity is reduced to 8-bit only complexity.

We propose a generic framework for perfectly hiding UC-Commitment schemes in the Global Random Oracle model of Canetti \textit{el at.} (CCS 14). The main building block of our construction is a novel primitive called Sampleable-Range Trapdoor Function, that is, a trapdoor function for which there is a non-negligible probability of finding preimages when given a uniformly chosen element of its codomain and the corresponding trapdoor. To show the versatility of the framework, we give concrete instantiations based on factoring, code-based, and lattice-based hardness assumptions. Our construction yields the first lattice-based UC-Commitment scheme (not constructed via generic transformations, such as via Oblivious Transfer), and achieves what we call \textit{phase-adaptive security}, a novel security notion we introduce which is stronger than static security.

Achieving adaptive security for UC-Commitment schemes is non-trivial and, usually, comes at the price of efficiency. Phase-adaptive security stands between adaptive and static security, and may be of independent interest. In this model, adversaries can corrupt at the beginning or between the commitment and opening phases of the protocol, but not during their execution. This new model is motivated by the fact that, in practice, it is more likely that parties are corrupted between phases of the protocol (where a relatively long period may elapse) than during their execution.

S-boxes are functions with an input so small that the simplest way to specify them is their lookup table (LUT). Unfortunately, some algorithm designers exploit this fact to avoid providing the algorithm used to generate said lookup table. In this paper, we provide tools for finding the hidden structure in an S-box or to identify it as the output of a complex generation process rather than a random sample.

We introduce various "anomalies". These real numbers are such that a property with an anomaly equal to $a$ should be found roughly once in a set of $2^{a}$ random S-boxes. First, we revisit the literature on S-box reverse-engineering to present statistical anomalies based on the distribution of the coefficients in the difference distribution table, linear approximation table, and for the first time, the boomerang connectivity table.

We then count the number of S-boxes that have block-cipher like structures to estimate the anomaly associated to those. In order to recover these structures, we show that the most general tool for decomposing S-boxes is an algorithm efficiently listing all the vector spaces of a given dimension contained in a given set, and we present such an algorithm.

Finally, we propose general methods to formally quantify the complexity of any S-box. It relies on the production of the smallest program evaluating it and on combinatorial arguments.

Combining these approaches, we show that all permutations that are actually picked uniformly at random always have essentially the same cryptographic properties, and can never be decomposed in a simpler way. These conclusions show that multiple claims made by the designers of the latest Russian standards are factually incorrect.

Privacy-aware Blockchain Public Key Infrastructure (PB- PKI) is a recent proposal by Louise Axon (2017) to create a privacy-preserving Public Key Infrastructure on the Blockchain. However, PB-PKI suffers from operational problems. We found that the most important change, i.e., the key update process proposed in PB-PKI for privacy is broken. Other issues include authenticating a user during key update and ensuring proper key revocation.

In this paper, we provide solutions to the problems of PB-PKI. We suggest generating fresh keys during key update. Furthermore, we use ring signatures for authenticating the user requesting key updates and use Asynchronous accumulators to handle the deletion of revoked keys. We show that the approach is feasible and implement a proof of concept.

Diffie-Hellman groups are a widely used component in cryptographic protocols in which a shared secret is needed. These protocols are typically proven to be secure under the assumption they are implemented with prime order Diffie Hellman groups. However, in practice, many implementations either choose to use non-prime order groups for reasons of efficiency, or can be manipulated into operating in non-prime order groups. This leaves a gap between the proofs of protocol security, which assume prime order groups, and the real world implementations. This is not merely a theoretical possibility: many attacks exploiting small subgroups or invalid curve points have been found in the real world.

While many advances have been made in automated protocol analysis, modern tools such as Tamarin and ProVerif represent DH groups using an abstraction of prime order groups. This means they, like many cryptographic proofs, may miss practical attacks on real world protocols.

In this work we develop a novel extension of the symbolic model of Diffie-Hellman groups. By more accurately modelling internal group structure, our approach captures many more differences between prime order groups and their actual implementations. The additional behaviours that our models capture are surprisingly diverse, and include not only attacks using small subgroups and invalid curve points, but also a range of proposed mitigation techniques, such as excluding low order elements, single coordinate ladders, and checking the elliptic curve equation. Our models thereby capture a large family of attacks that were previously outside the symbolic model.

We implement our improved models in the Tamarin prover. We find a new attack on the Secure Scuttlebutt Gossip protocol, independently discover a recent attack on Tendermint’s secure handshake, and evaluate the effectiveness of the proposed mitigations for recent Bluetooth attacks.

Many post-quantum cryptosystems which have been proposed in the National Institute of Standards and Technology (NIST) standardization process follow the same meta-algorithm, but in different algebras or different encoding methods. They usually propose two constructions, one being weaker and the other requiring a random oracle. We focus on the weak version of nine submissions to NIST. Submitters claim no security when the secret key is used several times. In this paper, we analyze how easy it is to run a key recovery under multiple key reuse. We mount a classical key recovery under plaintext checking attacks (i.e., with a plaintext checking oracle saying if a given ciphertext decrypts well to a given plaintext) and a quantum key recovery under chosen ciphertext attacks. In the latter case, we assume quantum access to the decryption oracle.

Homomorphic Encryption (HE) is a cryptosystem which supports computation on encrypted data. L{\'o}pez-Alt et al. (STOC 2012) proposed a generalized notion of HE, called Multi-Key Homomorphic Encryption (MKHE), which is capable of performing arithmetic operations on ciphertexts encrypted under different keys.

In this paper, we present multi-key variants of two HE schemes with packed ciphertexts. We present new relinearization algorithms which are simpler and faster than previous method by Chen et al. (TCC 2017). We then generalize the bootstrapping techniques for HE to obtain multi-key fully homomorphic encryption schemes. We provide a proof-of-concept implementation of both MKHE schemes using Microsoft SEAL. For example, when the dimension of base ring is 8192, homomorphic multiplication between multi-key BFV (resp. CKKS) ciphertexts associated with four parties followed by a relinearization takes about 116 (resp. 67) milliseconds.

Our MKHE schemes have a wide range of applications in secure computation between multiple data providers. As a benchmark, we homomorphically classify an image using a pre-trained neural network model, where input data and model are encrypted under different keys. Our implementation takes about 1.8 seconds to evaluate one convolutional layer followed by two fully connected layers on an encrypted image from the MNIST dataset.

Cryptocurrency applications have spurred a resurgence of interest in the computation of ECDSA signatures using threshold protocols---that is, protocols in which the signing key is secret-shared among $n$ parties, of which any subset of size $t$ must interact in order to compute a signature. Among the resulting works to date, that of Doerner et al. requires the most natural assumptions while also achieving the best practical signing speed. It is, however, limited to the setting in which the threshold is two. We propose an extension of their scheme to arbitrary thresholds, and prove it secure against a malicious adversary corrupting up to one party less than the threshold under only the Computational Diffie-Hellman Assumption in the Global Random Oracle model, an assumption strictly weaker than those under which ECDSA is proven.

Whereas the best current schemes for threshold-two ECDSA signing use a Diffie-Hellman Key Exchange to calculate each signature's nonce, a direct adaptation of this technique to a larger threshold $t$ would incur a round count linear in $t$; thus we abandon it in favor of a new mechanism that yields a protocol requiring $\lceil\log(t)\rceil+6$ rounds in total. We design a new consistency check, similar in spirit to that of Doerner et al., but suitable for an arbitrary number of participants, and we optimize the underlying two-party multiplication protocol on which our scheme is based, reducing its concrete communication and computation costs.

We implement our scheme and evaluate it among groups of up to 256 of co-located and geographically-distributed parties, and among small groups of embedded devices. We find that in the LAN setting, our scheme outperforms all prior works by orders of magnitude, and that it is efficient enough for use even on smartphones or hardware tokens. In the WAN setting we find that, despite its logarithmic round count, our protocol outperforms the best constant-round protocols in realistic scenarios.

A secret-sharing scheme is a method by which a dealer, holding a secret string, distributes shares to parties such that only authorized subsets of parties can reconstruct the secret. The collection of authorized subsets is called an access structure. Secret-sharing schemes are an important tool in cryptography and they are used as a building box in many secure protocols. In the original constructions of secret-sharing schemes by Ito et al. [Globecom 1987], the share size of each party is $\tilde{O}(2^{n})$ (where $n$ is the number of parties in the access structure). New constructions of secret-sharing schemes followed; however, the share size in these schemes remains basically the same. Although much efforts have been devoted to this problem, no progress was made for more than 30 years. Recently, in a breakthrough paper, Liu and Vaikuntanathan [STOC 2018] constructed a secret-sharing scheme for a general access structure with share size $\tilde{O}(2^{0.994n})$. The construction is based on new protocols for conditional disclosure of secrets (CDS). This was improved by Applebaum et al. [EUROCRYPT 2019] to $\tilde{O}(2^{0.892n})$.

In this work, we construct improved secret-sharing schemes for a general access structure with share size $\tilde{O}(2^{0.762n})$. Our schemes are linear, that is, the shares are a linear function of the secret and some random elements from a finite field. Previously, the best linear secret-sharing scheme had shares of size $\tilde{O}(2^{0.942n})$. Most applications of secret-sharing require linearity. Our scheme is conceptually simpler than previous schemes, using a new reduction to two-party CDS protocols (previous schemes used a reduction to multi-party CDS protocols).

In a CDS protocol for a function $f$, there are $k$ parties and a referee; each party holds a private input and a common secret, and sends one message to the referee (without seeing the other messages). On one hand, if the function $f$ applied to the inputs returns $1$, then it is required that the referee, which knows the inputs, can reconstruct the secret from the messages. On the other hand, if the function $f$ applied to the inputs returns $0$, then the referee should get no information on the secret from the messages. However, if the referee gets two messages from a party, corresponding to two different inputs (as happens in our reduction from secret-sharing to CDS), then the referee might be able to reconstruct the secret although it should not.

To overcome this problem, we define and construct $t$-robust CDS protocols, where the referee cannot get any information on the secret when it gets $t$ messages for a set of zero-inputs of $f$. We show that if a function $f$ has a two-party CDS protocol with message size $c_f$, then it has a two-party $t$-robust CDS protocol with normalized message size $\tilde{O}(t c_f)$. Furthermore, we show that every function $f:[N] \times [N]\rightarrow \{0,1\}$ has a multi-linear $t$-robust CDS protocol with normalized message size $\tilde{O}(t+\sqrt{N})$. We use a variant of this protocol (with $t$ slightly larger than $\sqrt{N}$) to construct our improved linear secret-sharing schemes. Finally, we construct robust $k$-party CDS protocols for $k>2$.