International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

04:17 [Pub][ePrint] A Practical Chosen Message Power Analysis Method on the Feistel-SP ciphers with Applications to CLEFIA and Camellia, by Chenyang Tu and Neng Gao and Zeyi Liu and Lei Wang and Zongbin Liu and Bingke Ma

  The Feistel-SP structure is a commonly adopted structure in symmetric cryptography with many practical instances. Differential power analysis (DPA) has proven to be effective against these ciphers with compact implementations within these years. However, the applications of DPA on Feistel-SP ciphers with loop hardware implementations are more complicated and less evaluated in literature, mainly due to the relatively large size (32-bit or more) of the whole round key which often results in complex relations with the targeted intermediate variable. \\\\

In this paper, we propose a practical chosen message power analysis method on Feistel-SP ciphers with loop hardware implementations. The essence of the new method lies in the delicate selection of the plaintext set in a chosen message manner. Thus, the input space of the plaintext in our method is decreased from $2^{32}$ or more to $2^8$ or less, which is suitable for practical power analysis. Moreover, we show that the whitening key at the first or last round can be easily revealed with our method, thus leading to the full exposure of the master key thanks to the relations between whitening keys and the master key in many practical ciphers. In order to further manifest the validity of the new method, we carry extensive experiments on two ISO standardized and widely deployed ciphers CLEFIA and Camellia with loop implementations on FPGA, and the master keys are recovered as expected.

01:17 [Pub][ePrint] Differential-Linear Cryptanalysis of ICEPOLE, by Tao Huang; Ivan Tjuawinata; Hongjun Wu

  ICEPOLE is a CAESAR candidate with the intermediate level of robustness under nonce misuse circumstances in the original document. In particular, it was claimed that key recovery attack against ICEPOLE is impossible in the case of nonce misuse. ICEPOLE is strong against the differential cryptanalysis and linear cryptanalysis. In this paper, we developed the differential-linear attacks against ICEPOLE when nonce is misused. Our attacks show that the state of ICEPOLE-128 and ICEPOLE-128a can be recovered with data complexity $2^{46}$ and time complexity $2^{46}$; the state of ICEPOLE-256a can be recovered with data complexity $2^{60}$ and time complexity $2^{60}$. For ICEPOLE-128a and ICEPOLE-256a, the secret key is recovered once the state is recovered. We experimentally verified the attacks against ICEPOLE-128 and ICEPOLE-128a.

01:17 [Pub][ePrint] Exploring the Resilience of Some Lightweight Ciphers Against Proled Single Trace Attacks, by Valentina Banciu and Elisabeth Oswald and Carolyn Whitnall

  This paper compares attack outcomes w.r.t. profiled single trace attacks of four different lightweight ciphers in order to investigate which of their properties, if any, contribute to attack success. We show that mainly the diffusion properties of both the round function and the key schedule play a role. In particular, the more (reasonably statistically independent) intermediate values are produced in a target implementation, the better attacks succeed. A crucial aspect for lightweight ciphers is hence the key schedule which is often designed to be particularly light. This design choice implies that information from all round keys can be easily combined which results in attacks that succeed with ease.

01:17 [Pub][ePrint] New Multilinear Maps over the Integers, by Jean-Sebastien Coron and Tancrede Lepoint and Mehdi Tibouchi

  In the last few years, cryptographic multilinear maps have proved their tremendous potential as building blocks for new constructions, in particular the first viable approach to general program obfuscation. After the first candidate construction by Garg, Gentry and Halevi (GGH) based on ideal lattices, a second construction over the integers was described by Coron, Lepoint and Tibouchi (CLT). However the CLT scheme was recently broken by Cheon et al.; the attack works by computing the eigenvalues of a diagonalizable matrix over Q derived from the multilinear map.

In this paper we describe a new candidate multilinear map over the integers. Our construction is based on CLT but with a new arithmetic technique that makes the zero-testing element non-linear in the encoding, which prevents the Cheon et al. attack. Our new construction is relatively practical as its efficiency is comparable to the original CLT scheme. Moreover the subgroup membership and decisional linear assumptions appear to hold in the new setting.

01:17 [Pub][ePrint] Indistinguishability Obfuscation from Functional Encryption, by Nir Bitansky and Vinod Vaikuntanathan

  Indistinguishability obfuscation is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. We construct indistinguishability obfuscation from any public-key functional encryption scheme with succinct ciphertexts and sub-exponential security.

01:17 [Pub][ePrint] Constant Size Ring Signature Without Random Oracle, by Priyanka Bose and Dipanjan Das and C. Pandu Rangan

  Ring signature enables an user to anonymously sign a message on behalf of a group of users termed as \'ring\' formed in an \'ad-hoc\' manner. A naive scheme produces a signature linear in the size of the ring, but this is extremely inefficient when ring size is large. Dodis et al. proposed a constant size scheme in EUROCRYPT\'13, but provably secure in random oracle model. Best known result without random oracle is a sub-linear size construction by Chandran et al. in ICALP\'07 and a follow-up work by Essam Ghadafi in IMACC\'13. Therefore, construction of a constant size ring signature scheme without random oracle meeting stringent security requirement still remains as an

interesting open problem.

Our first contribution is a generic technique to convert a compatible signature scheme to a constantsized ring signature scheme. The technique employs a constant size set membership check that may be of independent interest. Our construction is instantiated over asymmetric pairing of composite order and optimally efficient. The scheme meets strongest security requirements, viz. anonymity under full key exposure and unforgeability against insider-corruption without using random oracle under simple hardness assumptions. We also provide a concrete instantiation of the scheme based on Full Boneh-Boyen signatures.

01:17 [Pub][ePrint] The Cryptographic Hardness of Random Local Functions -- Survey, by Benny Applebaum

  Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions

that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \\emph{random local functions} in which each output bit is computed by applying some fixed $d$-ary predicate $P$ to a randomly chosen $d$-size subset of the input bits.

In this work, we will study the cryptographic hardness of random local functions. In particular, we will survey known attacks and hardness results, discuss different flavors of hardness (one-wayness, pseudorandomness, collision resistance, public-key encryption), and mention applications to other problems in cryptography and computational complexity. We also present some open questions with the hope to develop a systematic study of the cryptographic hardness of local functions.

01:17 [Pub][ePrint] Naturally Rehearsing Passwords, by Jeremiah Blocki and Manuel Blum and Anupam Datta

  We introduce quantitative usability and security models to guide the design of \\emph{password

management schemes} --- systematic strategies to help users create and remember multiple

passwords. In the same way that security proofs in cryptography are based on

complexity-theoretic assumptions (e.g., hardness of factoring and discrete logarithm), we quantify

usability by introducing \\emph{usability assumptions}. In particular, password management relies

on assumptions about human memory, e.g., that a user who follows a particular rehearsal

schedule will successfully maintain the corresponding memory. These assumptions are informed by research in cognitive science and can be tested empirically. Given rehearsal requirements and a user\'s

visitation schedule for each account, we use the total number of extra rehearsals that

the user would have to do to remember all of his passwords as a measure of the usability of

the password scheme. Our usability model leads us to a key observation: password reuse benefits users not only by reducing the number of passwords that the user has to memorize, but more importantly by increasing the natural rehearsal rate for each password. We also present a security model which accounts for the complexity of password

management with multiple accounts and associated threats,

including online, offline, and plaintext password leak attacks. Observing that current

password management schemes are either insecure or unusable, we present Shared Cues--- a new scheme in which the underlying secret is strategically

shared across accounts to ensure that most rehearsal requirements are satisfied naturally while

simultaneously providing strong security. The construction uses the Chinese Remainder Theorem to achieve these competing goals.

01:17 [Pub][ePrint] Post-Zeroizing Obfuscation: The case of Evasive Circuits, by Saikrishna Badrinarayanan and Eric Miles and Amit Sahai and Mark Zhandry

  Recent devastating attacks by Cheon et al. [Eurocrypt\'15] and others have highlighted significant gaps in our intuition about security in candidate multilinear map schemes, and in candidate

obfuscators that use them. The new attacks, and some that were previously known, are typically called \"zeroizing\" attacks because they all crucially rely on the ability of the adversary to create

encodings of 0.

In this work, we initiate the study of post-zeroizing obfuscation, and we present a construction for the special case of evasive functions. We show that our obfuscator survives all known attacks

on the underlying multilinear maps, by proving that no encodings of 0 can be created by a generic-model adversary. Previous obfuscators (for both evasive and general functions) were either analyzed in a less-conservative \"pre-zeroizing\" model that does not capture recent attacks, or were proved secure relative to assumptions that are now known to be false.

To prove security, we introduce a new technique for analyzing polynomials over multilinear map encodings. This technique shows that the types of encodings an adversary can create are much more restricted than was previously known, and is a crucial step toward achieving postzeroizing security. We also believe the technique is of independent interest, as it yields efficiency improvements for existing schemes.

01:17 [Pub][ePrint] More PS and H-like bent functions, by C. Carlet

  Two constructions/classes of bent functions are derived from the notion of spread. The first class, ${\\cal PS}$, gives a useful framework for designing bent functions which are constant (except maybe at 0) on the elements of a (partial) spread. Dillon has deduced the explicit class ${\\cal PS}_{ap}$ of bent functions obtained from the spread of all multiplicative cosets of ${\\Bbb F}_{2^m}^*$ (added with 0) in ${\\Bbb F}_{2^{2m}}^*$ (that we shall call the Dillon spread). The second class, $H$, later slightly modified into a class called ${\\cal H}$ so as to relate it to the so-called Niho bent functions, is up to addition of affine functions the set of bent functions whose restrictions to the spaces of the Dillon spread are linear. It has been observed that the functions in ${\\cal H}$ are related to o-polynomials, and this has led to several explicit classes of bent functions. In this paper we first apply the ${\\cal PS}$ construction to a larger class of spreads, well-known in the finite geometry domain and that we shall call Andr\\\'e\'s spreads, and we describe explicitly the ${\\cal PS}$ corresponding bent functions and their duals. We also characterize those bent functions whose restrictions to the spaces of an Andr\\\'e spread are linear. This leads to a notion extending that of o-polynomial. Finally, we obtain similar characterizations for the ${\\cal H}$-like functions derived from the spreads used by Wu to deduce ${\\cal PS}$ bent functions from the Demp\\-wolff-M\\\"uller pre-quasifield, the Knuth pre-semifield and the Kantor pre-semifield. In each case, this also leads to a new notion on polynomials.

01:17 [Pub][ePrint] Short Schnorr signatures require a hash function with more than just random-prefix resistance, by Daniel R. L. Brown

  Neven, Smart and Warinschi (NSW) proved, in the generic group model, that full-length Schnorr signatures require only random-prefix resistant hash functions to resist passive existential forgery.

Short Schnorr signatures halve the length of the hash function, and

have been conjectured to provide a similar level of security. The

NSW result is too loose to provide a meaningful security for short

Schnorr signatures, but Neven, Smart and Warinschi conjecture that

this is mere artefact of the proof technique, and not an essential

deficiency of the short Schnorr signatures. In particular, this

amounts to a conjecture that short Schnorr signature are secure

under the same set of assumptions, namely random-prefix resistance

of the hash function.

This report provides a counterexample to the latter conjecture, in

other words, a separation result. It finds a hash function that

seems to suggest random-prefix resistance does not suffice for short

Schnorr signatures. In other words, the loose reduction implicit

in the NSW theorem is as tight as possible.

Obviously, this result does not preclude the possibility of another

proof for short Schnorr signatures, based on different hash function

security properties such as preimage resistance.