International Association
for Cryptologic Research

Physically Unclonable Functions (PUFs) are emerging as hardware security primitives. They are typically employed to generate device-unique secret keys. As PUF output bits are noisy and possibly biased or correlated, on-chip digital post-processing is required. Fuzzy

extractors are used to generate reproducible and uniformly distributed keys. Traditionally, they employ an error-correcting code and a cryptographic hash function. Pattern matching key generators

have been proposed as an alternative. In this work, we demonstrate the latter construction to be vulnerable against manipulation of the public helper data. Full key recovery might be possible, although depending on some design choices and one system parameter. We demonstrate our attacks using a 4-XOR arbiter PUF, manufactured in 65nm CMOS technology. We also propose a simple but efficient countermeasure.

Simon and Speck are two families of ultra-lightweight block ciphers which were proposed by the U.S. National Security Agency in June 2013. Yet, the specification paper discusses only the design and the performance of both cipher families, the task of analyzing their security has been left to the research community.

In this paper we present conventional differential as well as rectangle attacks for almost all members of the \\speck cipher family, where we target up to 11/22, 12/23, 14/16, 15/29, and 18/34 rounds of the 32-, 48-, 64-, 96-, and 128-bit version, respectively. In addition, we discuss rotational attacks, where we show that these attacks can be easily mounted for the full or almost the full number of rounds for large groups of weak keys.

At Eurocrypt 2013, Joye and Libert proposed a method for constructing public key cryptosystems (PKCs) and lossy trapdoor functions (LTDFs) from $(2^\\alpha)^{th}$-power residue symbols. Their work can be viewed as non-trivial extensions of the well-known PKC scheme due to Goldwasser and Micali, and the LTDF scheme due to Freeman et al., respectively. In this paper, we will demonstrate that this kind of work can be extended \\emph{more generally}: all related constructions can work for any $k^{th}$ residues if $k$ only contains small prime factors, instead of $(2^\\alpha)^{th}$-power residues only. The resultant PKCs and LTDFs are more efficient than that from Joye-Libert method in terms of decryption speed with the same message length.

Identity Based Encryption (IBE) systems are often constructed using pairings or lattices. Three exceptions are due to Cocks in 2001, Boneh, Gentry and Hamburg in 2007, and Paterson and Srinivasan in 2009. In this paper, we propose an efficient identity-based encryption scheme of which the security is rooted in the intractability assumption of integer factorization. We believe that our construction has some essential differences from all existing IBEs.

Secure multi-party computation (MPC) allows a set P of n players to evaluate a function f in presence of an adversary who corrupts a subset of the players. In this paper we consider active, general adversaries, characterized by a so-called adversary structure Z which enumerates all possible subsets of corrupted players. In particular for small sets of players general adversaries better capture real-world requirements than classical threshold adversaries.

Protocols for general adversaries are ``efficient\'\' in the sense that they require |Z|^O(1) bits of communication. However, as |Z| is usually very large (even exponential in n), the exact exponent is very relevant. In the setting with perfect security, the most efficient protocol known to date communicates |Z|^3 bits; we present a protocol for this setting which communicates |Z|^2 bits. In the setting with statistical security, |Z|^3 bits of communication is needed in general (whereas for a very restricted subclass of adversary structures, a protocol with communication

|Z|^2 bits is known); we present a protocol for this setting (without limitations) which communicates |Z|^1 bits.

RC4 has remained the most popular software stream cipher since the last two decades. In parallel to cryptanalytic attempts, researchers have come up with many variants of RC4, some targeted to more security, some towards more throughput. We observe that the design of RC4 has been changed a lot in most of the variants. Since the RC4 structure is quite secure if the cipher is used with proper precautions, an arbitrary change in the design may lead to potential vulnerabilities, such as the distinguishing attack (Tsunoo et al., 2007) on the word-oriented variant GGHN (Gong et al., 2005). Some variants keep the RC4 structure (Maitra et al., 2008), but is byte-oriented and hence is an overkill for modern wide-word processors. In this paper, we try to combine the best of both the worlds. We keep the basic RC4 structure which guarantees reasonable security (if properly used) and we combine 4 RC4 states tacitly to design a high throughput stream cipher called {\\em Quad-RC4} that produces $32$-bit output at every round. The storage requirement for the internal state is only $1024$ bits. In terms of speed, this cipher performs much faster than normal RC4 and is comparable with HC-128, the fastest software stream cipher amongst the eSTREAM finalists. We also discuss the issue of generalizing the structure of Quad-RC4 to higher word-width variants.

Submission: 8 January 2014
Notification: 1 March 2014
From May 28 to May 30
Location: Marrakech, Morroco
More Information: http://

Crypto Engineer is to Design, Develop, Engineer the next generation Digital Currency across all platforms for the global world market to use. (e.g. Internet, Mobile Technology, ect)

Work from your home location

Self-pairings are a special subclass of pairings and

have interesting applications in cryptographic schemes and protocols. In this paper, we explore the computation of the self-pairings on supersingular elliptic curves with embedding degree $k = 3$. We construct a novel self-pairing which has the same Miller loop as the Eta/Ate pairing. However, the proposed self-pairing has a simple final exponentiation. Our results suggest that the proposed self-pairings are more efficient than the other ones on the corresponding curves. We compare the efficiency of self-pairing computations on different curves

over large characteristic and estimate that the proposed self-pairings on curves with $k=3$ require $44\\%$ less field multiplications than the fastest ones on curves with $k=2$ at AES 80-bit security level.

We present a new general-purpose obfuscator for all polynomial-size circuits. The obfuscator uses graded encoding schemes, a generalization of multilinear maps. We prove that the obfuscator exposes no more information than the program\'s black-box functionality, and achieves {\\em virtual black-box security}, in the generic graded encoded scheme model. This proof is under a plausible worst-case complexity-theoretic assumption related to the Exponential Time Hypothesis, in addition to standard cryptographic assumptions.

Very recently, Garg et al.~(FOCS 2013) used graded encoding schemes to present a candidate obfuscator for the weaker notion of \\emph{indistinguishability obfuscation}, without a proof of security. They posed the problem of constructing a provably secure indistinguishability obfuscator in the generic model. Our obfuscator, which achieves the stronger guarantee of virtual black-box security, resolves this problem (under the complexity assumptions).

Our construction is different from that of Garg et al., but it is inspired by their use of permutation branching programs. We obtain our obfuscator by developing techniques used to obfuscate $d$-CNF formulas (ePrint 2013), and applying them to permutation branching programs. This yields an obfuscator for the complexity class NC1. We then use homomorphic encryption to obtain an obfuscator for any polynomial-size circuit.

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ in a manner so that tampering the codeword causes the decoder to either output $s$ or a message that is independent of $s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family $F$ of tampering functions that is not too large (for instance, when $|F| \\le \\exp(2^{\\alpha n})$ for some $\\alpha \\in [0, 1)$ where $n$ is the number of bits in a codeword).

In this work, we study the \"capacity of non-malleable coding\", and establish optimal bounds on the achievable rate as a function of the family size, answering an open problem from Dziembowski et al. (ICS 2010). Specifically,

1. We prove that for every family $F$ with $|F| \\le \\exp(2^{\\alpha n})$, there exist non-malleable codes against $F$ with rate arbitrarily close to $1-\\alpha$ (this is achieved w.h.p. by a randomized construction).

2. We show the existence of families of size $\\exp(n^{O(1)} 2^{\\alpha n})$ against which there is no non-malleable code of rate $1-\\alpha$ (in fact this is the case w.h.p for a random family of this size).

3. We also show that $1-\\alpha$ is the best achievable rate for the family of functions which are only allowed to tamper the first $\\alpha n$ bits of the codeword, which is of special interest.

As a corollary, this implies that the capacity of non-malleable coding in the split-state model (where the tampering function acts independently but arbitrarily on the two halves of the codeword) equals $1/2$.

We also give an efficient Monte Carlo construction of codes of rate close to 1 with polynomial time encoding and decoding that is non-malleable against any fixed $c > 0$ and family $F$ of size $\\exp(n^c)$, in particular tampering functions with, say, cubic size circuits.

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable coding is possible against any class of adversaries of bounded size. In particular, Dziembowski et al. show that such codes exist and may achieve positive rates for any class of tampering functions of size at most $2^{2^{\\alpha n}}$, for any constant $\\alpha \\in [0, 1)$. However, this result is existential and has thus attracted a great deal of subsequent research on explicit constructions of non-malleable codes against natural classes of adversaries.

In this work, we consider constructions of coding schemes against two well-studied classes of tampering functions; namely, bit-wise tampering functions (where the adversary tampers each bit of the encoding independently) and the much more general class of split-state adversaries (where two independent adversaries arbitrarily tamper each half of the encoded sequence). We obtain the following results for these models.

1. For bit-tampering adversaries, we obtain explicit and efficiently encodable and decodable non-malleable codes of length $n$ achieving rate $1-o(1)$ and error (also known as \"exact security\") $\\exp(-\\tilde{\\Omega}(n^{1/7}))$. Alternatively, it is possible to improve the error to $\\exp(-\\tilde{\\Omega}(n))$ at the cost of making the construction Monte Carlo with success probability $1-\\exp(-\\Omega(n))$ (while still allowing a compact description of the code). Previously, the best known construction of bit-tampering coding schemes was due to Dziembowski et al. (ICS 2010), which is a Monte Carlo construction achieving rate close to .1887.

2. We initiate the study of seedless non-malleable extractors as a natural variation of the notion of non-malleable extractors introduced by Dodis and Wichs (STOC 2009). We show that construction of non-malleable codes for the split-state model reduces to construction of non-malleable two-source extractors. We prove a general result on existence of seedless non-malleable extractors, which implies that codes obtained from our reduction can achieve rates arbitrarily close to 1/5 and exponentially small error. In a separate recent work, the authors show that the optimal rate in this model is 1/2. Currently, the best known explicit construction of split-state coding schemes is due to Aggarwal, Dodis and Lovett (ECCC TR13-081) which only achieves vanishing (polynomially small) rate.

As part of our participation in the just starting EU FP7 project PRIPARE on privacy engineering and privacy by design, we have an open PhD position in this area.

Evaluation of applications is continuing until the position is filled.

I am looking for a PhD student to join the DemTech research project (www.demtech.dk). DemTech\\\'s broad mission is about the role of technology in democratic processes. We work on topics ranging from software engineering and requirements engineering, information security, and program verification, cryptography, in particular ever lasting privacy, but also logic methods, concurrency, and computational social choice. The successful candidate will join an international group consisting of faculty, post-docs, and PhD students. DemTech is working with many governmental institutions around the world. The position runs for three or four years. The application deadline is

13th October 2013, at 23:59 CET

Please note that this is a strict deadline.

This paper presents early results of a (very) experimental implementation of the elliptic curve and stream cipher calculations of the Networking and Cryptography library (NaCl), on the TRS-80 Model I. Needless to say, the demonstration that such a library, which has been optimized for many modern platforms including leading edge desktops, servers and, recently, modern microcontrollers, is even feasible on such early home microcomputers is, at best, to be considered a recreation rather than as a practical application of technology. In the process, however, lessons were learned in implementing trade-offs for basic cryptographic primitives and, more importantly maybe, in experimenting with some transformative aspects of retrocomputing.

Counting the number of active S-boxes is a common way to evaluate the security of symmetric key cryptographic schemes against differential attack. Based on Mixed Integer Linear Programming (MILP), Mouha et al proposed a method to accomplish this task automatically for word-oriented symmetric-key ciphers with SPN structures. However, this method can not be applied directly to block ciphers of SPN structures with bitwise permutation diffusion layers (S-bP structures), due to its ignorance of the diffusion effect derived collaboratively by nonlinear substitution layers and bitwise permutation layers. Moreover, the MILP constrains presented in Mouha et al\'s method are not enough to describe the differential propagation behaviour of a linear diffusion layer constructed from a non-MDS code, even an almost MDS code. In this paper we extend Mouha et al\'s method for S-bP structures by introducing new representations for exclusive-or (XOR) differences to describe bit/word level differences simultaneously and by taking the collaborative diffusion effect of S-boxes and bitwise permutations into account. Our method is applied to the block cipher PRESENT-80, an international standard for lightweight symmetric key cryptography, to automatically evaluate its security against differential attacks. We obtain lower bounds on the numbers of active S-boxes in the single-key model for full 31-round PRESENT-80 and in related-key model for round-reduced PRESENT-80 up to 12 rounds, and therefore automatically prove that the full-round PRESENT-80 is secure against single-key differential attack, and the cost of related-key differential attack on the full-round PRESENT-80 is close to that of an exhaustive search: the best related-key differential characteristic for full PRESENT-80 is upper bounded by $2^{-72}$.

We give an algorithm for decomposing given element of Jacobian gruop

into the sum of the decomposed factor, which consists of certain subset of the points of curve.

Faug\\\'ere et al. shows that the decomposition problem of an element of elliptic curve over binary field $F_{2^n}$ reduces to solving low degree equations system over $bF_2$ coming from Weil descent. Using this method, the discrete logarithm problem of elliptic curve over $F_{2^n}$ reduces to linear constrains, i.e., solving equations system using linear algebra of monomial modulo field equations, and its complexity is expected to be subexponential of input size $n$. However, it is pity that at least using linear constrains, it is exponential.

Petit et al. shows that assuming first fall degree assumption and using Gr\\\"obner basis computation, its complexity is heuristically subexponential.

On the other hands, the author shows that the decomposition problem of Jacobian of plane curve over $F_{p^n}$ also essentially reduces to solving low degree equations system over $F_p$ coming from Weil descent.

In this paper, we generalize ($p>2$ cases, Jacobian cases) and revise (precise estimation of first fall degree) the results of Petit et al. and show that the discrete logarithm problem

of elliptic curve over small characteristic field $F_{p^n}$ is subexponential of input size $n$, and the discrete logarithm problem of Jacobian of small genus curve over small characteristic field $F_{p^n}$ is also subexponential of input size $n$,

under first fall degree assumption.

At Eurocrypt 2013, Joye and Libert proposed a method for constructing public key cryptosystems (PKCs) and lossy trapdoor functions (LTDFs) from $(2^\\alpha)^{th}$-power residue symbols. Their work can be viewed as non-trivial extensions of the well-known PKC scheme due to Goldwasser and Micali, and the LTDF scheme due to Freeman et al., respectively. In this paper, we will demonstrate that this kind of work can be extended \\emph{more generally}: all related constructions can work for any $k^{th}$ residues if $k$ only contains small prime factors, instead of $(2^\\alpha)^{th}$-power residues only. The resultant PKCs and LTDFs are more efficient than that from Joye-Libert method in terms of decryption speed with the same message length.

This document describes the symmetric encryption algorithm called Puzzle. It is free and open. The objective of this paper is to get an opinion about its security from the cryptology community. It is separated in two parts, a technical description of the algorithm and its cryptanalysis. The algorithm has some interesting properties :

The block size is variable and unknown from an attacker. The size of the key has no limit and is unknown from an attacker. The key size does not affect the algorithm speed (using a 256 bit key is the same as using a 1024 bit key). The algorithm is much faster than the average cryptographic function. Experimental test showed 600 Mo/s - 4 cycles/byte on an Intel Core 2 Duo P8600 2.40GHz and 1,2 Go/s - 2 cycles/byte on an Intel i5-3210M 2.50GHz. Both CPU had only 2 cores.