International Association
for Cryptologic Research

The Horst Görtz Institute for IT-Security (HGI) at Ruhr- University Bochum is one of Europe’s leading research centers in IT security. The DFG, or German Research Foundation, awarded more than €4 million to the HGI for the establishment of the interdisciplinary research training group “New Challenges for Cryptography in Ubiquitous Computing”. We are looking for candidates with an outstanding Ph.D. in the fields of computer science, electrical engineering, mathematics or related areas.

The research training group will study problems which are fundamental for securing the Internet of Things. The research is structured in three levels: cryptographic primitives, device and system level. The research topics range from cryptographic foundations such as fully homomorphic encryption for privacy in cloud computing, over security for medical implants to internet security solutions involving new national ID cards.

Beside the own research, the main task of the Postdoc is to work withthe UbiCrypt Ph.D. students, and to encourage collaboration between them.

Thus,an interest in working with doctoral students and a broad interest in current research are required.

- Start: earliest possile

- Competitive salary (TV-L 14)

- Application: Send your documents by August 31, 2015, to grako (at) hgi.rub.de

- Required documents: CV, certificates (Bachelor, Master/Diplom, Ph.D.), transcripts , motivation for applying (1 page), names of at least two people who can provide reference letters (email addresses are sufficient)

A group of internationally renowned researchers together with excellent funding provides an extremely interesting scientific environment. The HGI is known for its good working atmosphere.

The Horst Görtz Institute for IT-Security (HGI) at Ruhr-University Bochum is one of Europe’s leading research centers in IT security. The DFG, or German Research Foundation, awarded more than €4 million to the HGI for the establishment of the interdisciplinary research training group “New Challenges for Cryptography in Ubiquitous Computing”. We are looking for candidates with outstanding Master/Diplom in the fields of computer science, electrical engineering, mathematics or related areas.

The research training group will study problems which are fundamental for securing the Internet of Things. The research is structured in three levels: cryptographic primitives, device and system level.

The research topics range from cryptographic foundations such as fully homomorphic encryption for privacy in cloud computing, over security for medical implants to internet security solutions involving new national ID cards. A central goal of the doctoral training is an interdisciplinary and structured education at the highest scientific level. Establishing networks to top internationally research groups is part of the training.

A group of internationally renowned researchers together with excellent funding provides an extremely interesting scientific environment. The HGI is known for its good working atmosphere.

- Start: earliest possible

- Competitive salary (TV-L 13)

- Application: Send your documents by August 31, 2015, to grako (at) hgi.rub.de

- Required Documents: CV, certificates, transcript (Master or Diplom), motivation for applying (1 page), names of at least two people who can provide reference letters (email addresses are sufficient)

Further information:

http://www.ubicrypt.hgi.rub.de/index.html.de

Modular multiplication and modular reduction are the atomic constituents of most public-key cryptosystems. Amongst the numerous algorithms for performing these operations, a particularly elegant method was proposed by Barrett. This method builds the operation $a \\bmod b$ from bit shifts, multiplications and additions in $\\mathbb{Z}$. This allows building modular reduction at very marginal code or silicon costs by leveraging existing hardware or software multipliers.

This paper presents a method allowing doubling the speed of Barrett\'s algorithm by using specific composite moduli. This is particularly useful for lightweight devices where such an optimization can make a difference in terms of power consumption, cost and processing time. The generation of composite moduli with a predetermined portion is a well-known technique and the use of such moduli is considered, in statu scientae, as safe as using randomly generated composite moduli.

Fault and power attacks are two common ways of extracting secrets from tamper-resistant chips. Although several protections have been proposed to thwart these attacks, resistant designs usually claim significant area or speed overheads. Furthermore, circuit-level countermeasures are usually not reconfigurable at runtime. This paper exploits the AES\' algorithmic features to propose low-cost and low-latency protections.

We provide Verilog and FPGA implementation details. Using our design, real-life applications can be configured during runtime to meet the user\'s needs and the system\'s constraints.

This paper describes a new multiplication algorithm, particularly

suited to lightweight microprocessors when one of the operands is

known in advance. The method uses backtracking to find a multiplicationfriendly encoding of the operand known in advance.

A 68HC05 microprocessor implementation shows that the new algorithm

indeed yields a twofold speed improvement over classical multiplication for 128-byte numbers.

Password vaults are increasingly popular applications that store multiple passwords encrypted under a single master password that the user memorizes. A password vault can greatly reduce the burden on a user of remembering passwords, but introduces a single point of failure. An attacker that obtains a user\'s encrypted vault can mount offline brute-force attacks and, if successful, compromise all of the passwords in the vault. In this paper, we investigate the construction of encrypted vaults that resist such offline cracking attacks and force attackers instead to mount online attacks.

Our contributions are as follows. We present an attack and supporting analysis showing that a previous design for cracking-resistant vaults--the only one of which we are aware--actually degrades security relative to conventional password-based approaches. We then introduce a new type of secure encoding scheme that we call a natural language encoder (NLE). An NLE permits the construction of vaults which, when

decrypted with the wrong master password, produce plausible-looking decoy passwords. We show how to build NLEs using existing tools from natural language processing, such as n-gram models and probabilistic context-free grammars, and evaluate their ability to generate plausible decoys. Finally, we present, implement, and evaluate a full, NLE-based cracking-resistant vault system called NoCrack.

We examine a FlipIt game in which there are multiple resources which a monolithic attacker is trying to compromise. This extension to FlipIt was considered in a paper in GameSec 2014, and was there called FlipThem. Our analysis of such a situation is focused on the situation where the attacker\'s goal is to compromise a threshold of the resources. We use our game theoretic model to enable a defender to choose the correct configuration of resources (number of resources and the threshold) so as to ensure that it makes no sense for a rational adversary to try to attack the system. This selection is made on the basis of the relative costs of the attacker and the defender.

This paper presents new speed records for arithmetic on a large family of elliptic curves with cofactor 3: specifically, 8.77M per bit for 256-bit variable-base single-scalar multiplication when curve parameters are chosen properly. This is faster than the best results known for cofactor 1, showing for the first time that points of order 3 are useful for performance and narrowing the gap to the speeds of curves with cofactor 4.

Secure two-party computation allows two mutually distrusting parties to compute a function together, without revealing their secret inputs to each other. Traditionally, the security properties desired in this context, and the corresponding security proofs, are based on a notion of simulation, which can be symbolic or computational. Either way, the proofs of security are intricate, requiring first to find a simulator, and then to prove a notion of indistinguishability.

Furthermore, even for classic protocols such as Yao\'s (based on garbled circuits and oblivious transfer), we do not have adequate symbolic models for cryptographic primitives and protocol roles, that can form the basis for automated security proofs. We therefore propose new models in applied pi-calculus in order to address these gaps. Our contributions, formulated in the context of Yao\'s protocol, include:

- an equational theory for specifying the primitives of garbled computation and oblivious transfer;

- process specifications for the roles of the two parties in Yao\'s protocol;

- definitions of security that are more clear and direct: result integrity, input agreement (both based on correspondence assertions) and input privacy (based on observational equivalence).

We put these models together and illustrate their use with ProVerif, providing a first automated verification of security for Yao\'s two-party computation protocol.

COFFE is a hash-based authenticated encryption scheme. In the original paper, it was claimed to have IND-CPA security and also ciphertext integrity even in nonce-misuse scenario. In this paper, we analyse the security of COFFE. Our attack shows that even under the assumption that the primitive hash function is ideal, a valid ciphertext can be forged with 2 enquiries with success probability close to 1. The motivation of the attack is to find a collision on the input of each of the hash calls in the COFFE instantiation. It can be done in two ways.

The first way is by modifying nonce and last message block size. Chosen appropriately, we can ensure two COFFE instantiations with different nonce and different last message block size can have exactly the same intermediate state value. This hence leads to a valid ciphertext to be generated. Another way is by considering two different COFFE instantiations with different message block size despite same key. In this case, we will use the existence of consecutive zero in the binary representation the initial value to achieve identical intermediate state value on two different COFFE instantiations. Having the state collisions, the forgery attack is then conducted by choosing two different plaintexts with appropriate nonce and tag size to query. Having this fact, without knowing the secret key, we can then validly encrypt another plaintext with probability equal to 1.

Two announcements:

(1) CRYPTO 2015 is less than two weeks away, and the proceedings are now available. Through our arrangement with Springer, IACR members can access the proceedings for free online (http://www.iacr.org/services/springer.php). You will need to login with your IACR membership credentials.

In addition to traditional PDFs, this year Springer is also offering HTML and ePub versions of the proceedings. We hope this improves your experience on a wider variety of devices.

(2) Tal Rabin is stepping down as co-editor of the ePrint Archive after 7.5 years of service. We thank her for her diligent service over a period of time that saw ePrint roughly double in publication volume.

We are also pleased to announce that Alexandra (Sasha) Boldyreva has agreed to take over as the new co-editor of ePrint. Nigel Smart remains as the other co-editor.

We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction.

We provide two distinct, but closely related constructions and show that multilinear analogues of the DDH assumption hold for them. Our first construction is \\emph{symmetric} and comes with a k-linear map e : G^k --> G_T for prime-order groups G and G_T. To establish the hardness of the k-linear DDH problem, we rely on the existence of a base group for which the (k - 1)-strong DDH assumption holds. Our second construction is for the \\emph{asymmetric} setting, where e : G_1 x ... x G_k --> G_T for a collection of k + 1 prime-order groups G_i and G_T, and relies only on the standard DDH assumption in its base group. In both constructions the linearity k can be set to any arbitrary but a priori fixed polynomial value in the security parameter.

We rely on a number of powerful tools in our constructions: (probabilistic) indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness indistinguishability and zero knowledge), and additively homomorphic encryption for the group Z_N^{+}. At a high level, we enable \"bootstrapping\" multilinear assumptions from their simpler counterparts in standard cryptographic groups, and show the equivalence of IO and multilinear maps under the existence of the aforementioned primitives.

In this paper we present a very simple scheme for strengthening the conventional product-sum type PKC which has been long considered insecure against the various attacks such as the secret key attack, LLL attack, etc.

We show that with the proposed strengthening scheme, the securities of the conventional product-sum type PKC\'s can be much improved.

Diffusion layers are critical components of symmetric ciphers. MDS matrices are diffusion layers of maximal branch number which have been used in various symmetric ciphers. In this article, we examine decomposition of cyclic matrices from mathematical viewpoint and based on that, we present new cyclic MDS matrices. From the aspect of implementation, the proposed matrices have lower implementation costs both in software and hardware, compared to what is presented in cryptographic literature, up to our knowledge.

In this work, we construct an adaptively secure functional encryption for Turing machines scheme, based on indistinguishability obfuscation for circuits. Our work places no restrictions on the types of Turing machines that can be associated with each secret key, in the sense that the Turing machines can accept inputs of unbounded length, and there is no limit to the description size or the space complexity of the Turing machines.

Prior to our work, only special cases of this result were known, or stronger assumptions were required. More specifically, previous work (implicitly) achieved selectively secure FE for Turing machines with a-priori bounded input based on indistinguishability obfuscation (STOC 2015), or achieved FE for general Turing machines only based on knowledge-type assumptions such as public-coin differing-inputs obfuscation (TCC 2015).

A consequence of our result is the first constructions of succinct adaptively secure garbling schemes (even for circuits) in the standard model. Prior succinct garbling schemes (even for circuits) were only known to be adaptively secure in the random oracle model.

Arithmetic Walsh transform(AWT) of Boolean function caught our attention due to their arithmetic analogs of Walsh-Hadamard transform(WHT) recently. We present new results on AWT in this paper. Firstly we characterize the existence of linear structure of Boolean functions in terms of AWT. Secondly we show that the relation between AWT and WHT of a balanced Boolean function with a linear structure 1^n is sectionally linear. Carlet and Klapper\'s recent work showed that the AWT of a diagonal Boolean function can be expressed in terms of the AWT of a diagonal Boolean function of algebraic degree at most 3 in a larger number of variables.However their proof is right only when c has even weight.We complement their proof by considering the case of c with odd weight.

The Modular Inversion Hidden Number Problem (MIHNP) was introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001 (BHH\'01). They provided two heuristics - in Method I, two-third of the output bits are required to solve the problem, whereas the more efficient heuristic (Method II) requires only one-third of the bits of the output. After more than a decade, here we identify that the claim in Method II is actually not correct and a detailed

calculation justifies that this method too requires two-third of the bits of the output, contrary to the claim in BHH\'01. Further, we show that using the same relations as in Boneh et al., one can reconstruct the lattice so that the problem can be heuristically solved by the knowledge of five-eighth of the bits. Finally, we could accumulate additional relations to solve the problem heuristically with only half of the output bits in asymptotic sense. Experimental results support the claim corresponding to our heuristics.

An oracle chooses a function f from the set of n bits strings to itself, which is either a randomly chosen permutation or a randomly chosen function. When queried by an n-bit string w, the oracle computes f(w), truncates the m last bits, and returns only the first n-m bits of f(w). How many queries does a querying adversary need to submit in order to distinguish the truncated permutation from a random function?

In 1998, Hall et al. showed an algorithm for determining (with high probability) whether or not f is a permutation, using O ( 2^((m+n)/2) ) queries. They also showed that if m < n/7, a smaller number of queries will not suffice. For m > n/7, their method gives a weaker bound.

In this manuscript, we show how a modification of the method used by Hall et al. can solve the porblem completely. It extends the result to essentially every m, showing that

Omega ( 2^((m+n)/2) ) queries are needed to get a non-negligible distinguishing advantage.

We recently became aware that a better bound for the distinguishing advantage, for every m

Recently Sarkar (DCC 2014) has proposed a new attack on small decryption exponent when RSA Modulus is of the form N=p^rq for r>=2.

This variant is known as Prime Power RSA. The work of Sarkar improves the result of May (PKC 2004) when r

Diffusion layers are critical components of symmetric ciphers. MDS matrices are diffusion layers of maximal branch number which have been used in various symmetric ciphers. In this article, we examine decomposition of cyclic matrices from mathematical viewpoint and based on that, we present new cyclic MDS matrices. From the aspect of implementation, the proposed matrices have lower implementation costs both in software and hardware, compared to what is presented in cryptographic literature, up to our knowledge.