International Association
for Cryptologic Research

This book offers an introduction to cryptology, the science that makes secure communications possible, and addresses its two complementary aspects: cryptography—--the art of making secure building blocks—--and cryptanalysis—--the art of breaking them. The text describes some of the most important systems in detail, including AES, RSA, group-based and lattice-based cryptography, signatures, hash functions, random generation, and more, providing detailed underpinnings for most of them. With regard to cryptanalysis, it presents a number of basic tools such as the differential and linear methods and lattice attacks.

Secure multi-party computation (MPC) allows several mutuallydistrustful parties to securely compute a joint function of theirinputs and exists in two main variants: In *synchronous* MPC partiesare connected by a synchronous network with a global clock, andprotocols proceed in *rounds* with strong delivery guarantees, whereas*asynchronous* MPC protocols can be deployed even in networks thatdeliver messages in an arbitrary order and impose arbitrary delays onthem.

The two models---synchronous and asynchronous---have to a large extentdeveloped in parallel with results on both feasibility and asymptoticefficiency improvements in either track. The most notable gap in thisparallel development is with respect to round complexity. Inparticular, although under standard assumptions on a synchronouscommunication network (availability of secure channels and broadcast),synchronous MPC protocols with (exact) constant rounds have beenconstructed, to the best of our knowledge, thus far no constant-roundasynchronous MPC protocols are known, with the best protocolsrequiring a number of rounds that is linear in the multiplicativedepth of the arithmetic circuit computing the desired function.

In this work we close this gap by providing the first constant-roundasynchronous MPC protocol. Our protocol is optimally resilient (i.e.,it tolerates up to $t<n/3$ corrupted parties), adaptively secure, andmakes black-box use of a pseudo-random function. It works under thestandard network assumptions for protocols in the asynchronous MPCsetting, namely, a complete network of point-to-point (secure)asynchronous channels with eventual delivery and asynchronousByzantine agreement (aka consensus). We provide formal definitions ofthese primitives and a proof of security in the UniversalComposability framework.

Armknecht and Mikhalev proposed a new stream cipher `Sprout' based on the design specification of the stream cipher, Grain-128a. Sprout has shorter state size than Grain family with a round key function. The output of the round key function is XORed with the feedback bit of the NFSR of the cipher. In this paper, we propose a new fault attack on Sprout by injecting a single bit fault after the key initialization phase at any arbitrary position of the NFSR of the cipher. By injecting a single bit fault, we recover the bits of the secret key of the cipher by observing the normal and faulty keystream bits at certain clockings of the cipher. By implementing the attack, we verify our result for one particular case. We also show that the Sprout generates same keystream bits for two different key-IV pairs, which is a serious security flaw in Sprout.

This paper presents a new framework for constructing fully CCA-secure predicate encryption schemes from pair encoding schemes. Our construction is the first in the context of predicate encryption which uses the technique of well-formedness proofs known from public key encryption. The resulting constructions are simpler and more efficient compared to the schemes achieved using known generic transformations from CPA-secure to CCA-secure schemes. The reduction costs of our framework are comparable to the reduction costs of the underlying CPA-secure framework. We achieve this last result by applying the dual system encryption methodology in a novel way.

The Algebraic Eraser Diffie-Hellman (AEDH) protocol, first introduced in 2005 as a key agreement and authentication protocol, has been proposed as a standard in ISO JTC-1/SC-31 (29167-20) to protect various communication protocols like RFID, NFC, or Bluetooth for devices associated with ISO-18000 and the Internet of Things. A recent paper by M.J.B. Robshaw and Simon R Blackburn claims to recover sufficient data to impersonate a device or, with a bit more work, recover the private keys of a device if an attacker uses the draft 29167-20 protocol and gains direct access to the resulting shared secret computation. This paper shows that simply adding a Hash or a Message Authentication Code (MAC) to the proposed authentication protocol overcomes the purported attacks. These simple standard enhancements thwart all of these attacks; that is, attacks of this nature fail. As the 29167-20 draft is currently a work item under active development within the ISO process, all these attacks would normally have been addressed in the working group, and no AEDH protocol in the public domain currently transmits the computed shared secret. Therefore, contrary to the conclusion of Robshaw and Blackburn, a simple addition to the draft protocol, similar in nature to protections in other protocols like TLS, makes the AEDH protocol perfectly suitable for authentication of passive tags and other low-power, constrained devices.

Cryptographic protection of memory is an essential ingredient for any technology that allows a closed computing system to run software in a trustworthy manner and handle secrets, while its external memory is susceptible to eavesdropping and tampering. An example for such a technology is Intel's emerging Software Guard Extensions technology (Intel SGX) that appears in the latest processor generation, Architecture Codename Skylake. This technology operates under the assumption that the security perimeter includes only the internals of the CPU package, and in particular, leaves the DRAM untrusted. It is supported by an autonomous hardware unit called the Memory Encryption Engine (MEE), whose role is to protect the confidentiality, integrity, and freshness of the CPU-DRAM traffic over some memory range. To succeed in adding this unit to the micro architecture of a general purpose processor product, it must be designed under very strict engineering constraints. This requires a careful combination of cryptographic primitives operating over a customized integrity tree that mostly resides on the DRAM while relying only on a small internally stored root. The purpose of this paper is to explain how this hardware component of SGX works, and the rationale behind some of its design choices. To this end, we formalize the MEE threat model and security objectives, describe the MEE design, cryptographic properties, security margins, and report some concrete performance results.

Implementations of white-box cryptography aim to protect a secret key in a white-box environment in which an adversary has full control over the execution process and the entire environment. Its fundamental principle is the map of the cryptographic architecture, including the secret key, to a number of encoded tables that shall resist the inspection and decomposition of an attacker. In a gray-box scenario, however, the property of hiding required implementation details from the attacker could be used as a promising mitigation strategy against side-channel attacks (SCA). In this work, we present a first white-box implementation of AES on reconfigurable hardware for which we evaluate this approach assuming a gray-box attacker. We show that - unfortunately - such an implementation does not provide sufficient protection against an SCA attacker. We continue our evaluations by a thorough analysis of the source of the observed leakage, and present additional results which can be used to build stronger white-box designs.

Staircase-Generator codes (St-Gen codes) have recently been introduced in the design of code-based public key schemes and for the design of steganographic matrix embedding schemes. In this paper we propose a method for random splitting of St-Gen Codes and use it to design a new coding based public key encryption scheme. The scheme uses the known list decoding method for St-Gen codes, but introduces a novelty in the creation of the public and private key. We modify the classical approach for hiding the structure of the generator matrix by introducing a technique for splitting it into random parts. This approach counters the weaknesses found in the previous constructions of public key schemes using St-Gen codes. Our initial software implementation shows that encryption using Random Split of St-Gen Codes compared to original St-Gen Codes is slower by a linear factor in the number of random splits of the St-Gen code, while the decryption complexity remains the same.

Universally composable multi-party computation is impossible without setup assumptions. Motivated by the ubiquitous use of secure hardware in many real world security applications, Katz (EUROCRYPT 2007) proposed a model of tamper-proof hardware as a UC-setup assumption. An important aspect of this model is whether the hardware token is allowed to hold a state or not. Real world examples of tamper-proof hardware that can hold a state are expensive hardware security modules commonly used in mainframes. Stateless, or resettable hardware tokens model cheaper devices such as smartcards, where an adversarial user can cut off the power supply, thus resetting the card's internal state. A natural question is how the stateful and the resettable hardware model compare in their cryptographic power, given that either the receiver or the sender of the token (and thus the token itself) might be malicious. In this work we show that any UC-functionality that can be implemented by a protocol using a single untrusted stateful hardware token can likewise be implemented using a single untrusted resettable hardware token, assuming only the existence of one-way functions. We present two compilers that transform UC-secure protocols in the stateful hardware model into UC-secure protocols in the resettable hardware model. The first compiler can be proven secure assuming merely the existence of one-way functions. However, it (necessarily) makes use of computationally rather expensive non-black-box techniques. We provide an alternative second compiler that replaces the expensive non-black-box component of the first compiler by few additional seed OTs. While this second compiler introduces the seed OTs as additional setup assumptions, it is computationally very efficient.

In this paper, we initiate the study of ``homomorphic obfuscation", and show how to homomorphically obfuscate the kernel-test and affine subspace-test functionalities of high dimensional matrices. Namely, the evaluator is able to perform additions and multiplications over the obfuscated matrices, and test subspace memberships on the resulting code. The homomorphic operations are constrained by the prescribed data structure, e.g. a tree or a graph, where the matrices are stored. The security properties of all the constructions are based on the hardness of Learning with errors problem (LWE). The technical heart is to ``control" the ``chain reactions'' over a sequence of LWE instances.

Viewing the homomorphic obfuscation scheme from a different angle, it coincides with the graph-induced multilinear maps proposed by Gentry, Gorbunov and Halevi (GGH15). Our proof technique recognizes several ``safe modes" of GGH15 that are not known before, including a simple special case: if the graph is acyclic and the matrices are sampled independently from binary or error distributions, then the encodings of the matrices are pseudorandom. We further discuss the implication of our work for the landscape of cryptographic multilinear maps and program obfuscators.

Potential candidates are required to have interests in main research directions of the Department of Informatics where the position is offered. We especially encourage those with primary interests in Boolean functions and their applications, and, more generally, in discrete mathematics and mathematical cryptography. Further information in the following link:

https://www.jobbnorge.no/en/available-jobs/job/122667/research-fellows-phd-candidates-in-informatics-computer-science-2-positions

Closing date for applications: 1 April 2016

Contact: Dr. habil. Lilya Budaghyan, email: lilya.budaghyan (at) uib.no

More information: https://www.jobbnorge.no/en/available-jobs/job/122667/research-fellows-phd-candidates-in-informatics-computer-science-2-

Event date: 16 August 2016
Submission deadline: 19 April 2016
Notification: 26 May 2016

Event date: 2 May to 3 May 2016
Submission deadline: 31 March 2016
Notification: 12 April 2016

Event date: 17 September to 19 September 2016
Submission deadline: 15 June 2016
Notification: 1 August 2016

Event date: 26 September to 27 September 2016
Submission deadline: 3 May 2016
Notification: 4 July 2016

The surprising success of cryptocurrencies has led to a surge of interest in deploying large scale, highly robust, Byzantine fault tolerant (BFT) proto- cols for mission-critical applications, such as finan- cial transactions. Although the conventional wisdom is to build atop a (weakly) synchronous protocol such as PBFT (or a variation thereof), such protocols rely critically on network timing assumptions, and only guarantee liveness when the network behaves as ex- pected. We argue these protocols are ill-suited for this deployment scenario.

We present an alternative, HoneyBadgerBFT, the first practical asynchronous BFT protocol, which guarantees liveness without making any timing as- sumptions. We base our solution on a novel atomic broadcast protocol that achieves optimal asymptotic efficiency. We present an implementation and ex- perimental results to show our system can achieve throughput of tens of thousands of transactions per second, and scales to over a hundred nodes on a wide area network. We even conduct BFT experi- ments over Tor, without needing to tune any parame- ters. Unlike the alternatives, HoneyBadgerBFT sim- ply does not care about the underlying network.

We explore the feasibility of applying SAT solvers to optimizing implementations of small functions such as S-boxes for multiple optimization criteria, e.g., the number of nonlinear gates and the number of gates. We provide optimized implementations for the S-boxes used in Ascon, ICEPOLE, Joltik/Piccolo, Keccak/Ketje/Keyak, LAC, Minalpher, PRIMATEs, Pr\o st, and RECTANGLE, most of which are candidates in the secound round of the CAESAR competition. We then suggest a new method to optimize for circuit depth and we make tooling publicly available to find efficient implementations for several criteria. Furthermore, we illustrate with the 5-bit S-box of PRIMATEs how multiple optimization criteria can be combined.

We examine the IND-qCPA security of the wide-spread block cipher modes of operation CBC, CFB, OFB, CTR, and XTS (i.e., security against quantum adversaries doing queries in superposition).

We show that OFB and CTR are secure assuming that the underlying block cipher is a standard secure PRF (a pseudorandom function secure under classical queries). We give counterexamples that show that CBC, CFB, and XTS are not secure under the same assumption.

And we give proofs that CBC and CFB mode are secure if we assume a quantum secure PRF (secure under queries in superposition).

Traditional fully homomorphic encryption (FHE) schemes only allow computation on data encrypted under a single key. L{\'o}pez-Alt, Tromer, and Vaikuntanathan (STOC 2012) proposed the notion of \emph{multi-key} FHE, which allows homomorphic computation on ciphertexts encrypted under different keys, and also gave a construction based on a (somewhat nonstandard) assumption related to NTRU. More recently, Clear and McGoldrick (CRYPTO 2015), followed by Mukherjee and Wichs (EUROCRYPT 2016), proposed a multi-key FHE based on learning with errors (LWE). However, unlike the original construction of L{\'o}pez-Alt \etal, these later LWE-based schemes have the somewhat undesirable property of being ``single-hop'' with respect to keys, i.e., all relevant keys must be known at the start of the homomorphic computation, and the output cannot be usefully combined with ciphertexts encrypted under other keys (unless an expensive ``bootstrapping'' step is performed).

In this work we construct two multi-key FHE schemes, based on LWE assumptions, which are \emph{multi-hop with respect to keys}: the output of a homomorphic computation on ciphertexts encrypted under a set of keys can be used in further homomorphic computation involving \emph{additional} keys, and so on. Our systems also have smaller ciphertexts than the previous LWE-based ones; indeed, ciphertexts in our second construction are simply GSW ciphertexts with no auxiliary data.

Recently, the security of RSA variants with moduli N=p^rq, e.g., the Takagi RSA and the prime power RSA, have been actively studied in several papers. Due to the unusual composite moduli and rather complex key generations, the analyses are more involved than the standard RSA. Furthermore, the method used in some of these works are specialized to the form of composite integers N=p^rq.

In this paper, we generalize the techniques used in the current best attacks on the standard RSA to the RSA variants. We show that the lattices used to attack the standard RSA can be transformed into lattices to attack the variants where the dimensions are larger by a factor of (r+1) of the original lattices. We believe the steps we took present to be more natural than previous researches, and to illustrate this point we obtained the following results: \begin{itemize} \item Simpler proof for small secret exponent attacks on the Takagi RSA proposed by Itoh et al. (CT-RSA 2008). Our proof generalizes the work of Herrmann and May (PKC 2010). \item Partial key exposure attacks on the Takagi RSA; generalizations of the works of Ernst et al. (Eurocrypt 2005) and Takayasu and Kunihiro (SAC 2014). Our attacks improve the result of Huang et al. (ACNS 2014). \item Small secret exponent attacks on the prime power RSA; generalizations of the work of Boneh and Durfee (Eurocrypt 1999). Our attacks improve the results of Sarkar (DCC 2014, ePrint 2015) and Lu et al. (Asiacrypt 2015). \item Partial key exposure attacks on the prime power RSA; generalizations of the works of Ernst et al. and Takayasu and Kunihiro. Our attacks improve the results of Sarkar and Lu et al. \end{itemize} The construction techniques and the strategies we used are conceptually easier to understand than previous works, owing to the fact that we exploit the exact connections with those of the standard RSA.