International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

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

2014-09-02
16:56 [Event][New]

From August 16 to August 20
Location: Santa Barbara, USA

09:17 [Pub][ePrint]

It is a long-standing open problem to prove the existence of (deterministic) hard-core predicates for the Diffie-Hellman problem over finite fields, without resorting to the generic approaches for any one-way functions (e.g., the Goldreich-Levin hard-core predicates). Fazio et al. (FGPS, Crypto \'13) make important progress on this problem by defining a weaker Computational Diffie-Hellman (CDH) problem over $\\mathbb{F}_{p^2}$, i.e., Partial-CDH problem, and proving the unpredictability of every single bit of one of the coordinates of the secret Diffie-Hellman value. However, the existence of specific hard-core predicates for the regular CDH problems defined over finite fields remains unproven. This paper closes this gap and resolves all the open problems left in FGPS:

1. We prove that the Partial-CDH problem over finite fields $\\mathbb{F}_{p^2}$ is as hard as the regular CDH problem over the same fields.

2. We show a much stronger and more generalized result over finite fields $\\mathbb{F}_{p^2}$---not only the regular CDH problem over $\\mathbb{F}_{p^2}$ admits hard-core predicates but every individual bit of the CDH value is unpredictable.

3. We extend the Partial-CDH problem to define the $d$-th CDH problem over finite fields $\\mathbb{F}_{p^t}$ for any polynomial $t>1$ and for any $0\\leq d \\leq t-1$. We show that computing any single coordinate of the CDH value over $\\mathbb{F}_{p^t}$ is equivalent to computing the entire CDH value.

4. We prove that over finite fields $\\mathbb{F}_{p^t}$ for any polynomial~$t>1$, each $d$-th CDH problem except $d \\neq 0$ admits a large class of hard-core predicates, including every individual bit of the $d$-th coordinate. Hence almost all individual bits of the CDH value of the regular CDH problem over finite fields $\\mathbb{F}_{p^t}$ for $t>1$ are hard-core.

09:17 [Pub][ePrint]

In this paper, we discuss the adjacency graph of feedback shift registers (FSRs) whose characteristic polynomial can be written as $g=(x_0+x_1)*f$ for some linear function $f$. For $f$ contains an odd number of terms, we present a method to calculate the adjacency graph of FSR$_{(x_0+x_1)*f}$ from the adjacency graph of FSR$_f$. The parity of the weight of cycles in FSR$_{(x_0+x_1)*f}$ can also be determined easily. For $f$ contains an even number of terms, the theory is not so much complete. We need more information than the adjacency graph of FSR$_f$ to determine the adjacency graph of FSR$_{(x_0+x_1)*f}$.

Besides, some properties about the cycle structure of linear feedback shift registers (LFSR) are presented.

07:12 [Event][New]

Submission: 30 November 2014
From December 19 to December 22
Location: Chennai, India

07:03 [Event][New]

From October 13 to October 16
Location: Porto, Portugal

2014-09-01
16:33 [Job][New]

The Chair for Information Security and Cryptography at University of Trier, Germany, offers a full-time PhD/Postdoc position.

The position involves both research and teaching in the area of cryptography/information security. The successful candidate is expected to contribute to research in cryptographic protocols and/or electronic voting.

The position is available immediately and is fully funded, with an internationally competitive salary.

Contracts are initially offered for two years. An extension to a total duration of up to six years is possible.

He or she is given the possibility to carry out a Ph.D. or, for Postdocs, a Habilitation.

The successful candidate should have a Master\'s degree or a Ph.D. (or should be very close to completion thereof) in Computer Science, Mathematics, Information Security, or a related field, with strong analytical and mathematical skills. Knowledge in cryptography is an asset. Since teaching is mostly done in German, sufficient knowledge of German is required.

The deadline for applications is October 5th, 2014. However, late applications will be considered until the position is filled.

See http://infsec.uni-trier.de/job-openings.html for the official job announcement (in German).

15:17 [Pub][ePrint]

The security of cryptographic algorithms can be consideredin two contexts. On the one hand, these algorithms can be proven secure mathematically. On the other hand, physical attacks can weaken the implementation of an algorithm yet proven secure. Under the common name of physical attacks, different attacks are regrouped: side channel

attacks and fault injection attacks. This paper presents a common formalism for these attacks and highlights their underlying principles. All physical attacks on symmetric algorithms can be described with a 3-step process. Moreover it is possible to compare different physical attacks, by separating the theoretical attack path and the experimental parts of the attacks.

15:17 [Pub][ePrint]

Algebraic side-channel attacks are a type of side-channel analysis which can recover the secret information with a small number of samples (e.g., power traces). However, this type of side-channel analysis is sensitive to measurement errors which may make the attacks fail.

In this paper, we propose a new method of algebraic side-channel attacks which considers noisy leakages as integers restricted to intervls and finds out the secret information with a constraint programming solver named BEE. To demonstrate the efficiency of this new method in algebraic side-channel attacks, we analyze some popular implementations of block ciphers---PRESENT, AES, and SIMON under the Hamming weight or Hamming distance leakage model. For AES, our method requires the least leakages compared with existing works under the same error model. For both PRESENT and SIMON, we provide the first analytical results of them under algebraic side-channel attacks in the presence of errors. To further demonstrate the wide applicability of this new method, we also extend it to cold boot attacks. In the cold boot attacks against AES, our method increases the success rate by over $25\\%$ than previous works.

15:17 [Pub][ePrint]

Attribute-based Credentials (ABCs) allow citizens to prove certain properties about themselves without necessarily revealing their full identity. Smart cards are an attractive container for such credentials, for security and privacy reasons. But their limited processing power and random access storage capacity pose a severe challenge. Recently, we, the IRMA team, managed to fully implement a limited subset of the Idemix ABC system on a smart card, with acceptable running times. In this paper we extend this functionality by overcoming the main hurdle: limited RAM. We implement an efficient

extended Pseudo-Random Number Generator (PRNG) for recomputing pseudorandomness and reconstructing variables. Using this we implement Idemix standard and domain pseudonyms, AND proofs based on prime-encoded attributes, and equality proofs of representation modulo a composite, together with terminal verification and secure messaging. In contrast to prior work that only addressed the verification of one credential with only one attribute (particularly, the master secret), we can now perform multi-credential proofs on credentials of 5 attributes and complex proofs in reasonable time. We provide a detailed performance analysis and compare our results to other approaches.

2014-08-31
15:17 [Pub][ePrint]

Most entropy notions $H(.)$ like Shannon or min-entropy satisfy a chain rule stating that for random variables $X,Z$ and $A$ we have $H(X|Z,A)\\ge H(X|Z)-|A|$. That is, by conditioning on $A$ the entropy of $X$ can decrease by at most the bitlength $|A|$ of $A$.

Such chain rules are known to hold for some computational entropy notions like

Yao\'s and unpredictability-entropy. For HILL entropy, the computational analogue of

min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption and memory delegation.

These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: We construct joint distributions $(X,Z,A)$, where $A$ is a

distribution over a \\emph{single} bit, such that the HILL entropy $H_\\infty(X|Z)$ is

large but $H_\\infty(X|Z,A)$ is basically zero.

Our counterexample just makes the minimal assumption that

${\\bf NP}\\nsubseteq{\\bf P/poly}$. Under the stronger assumption that

injective one-way function exist, we can make all the distributions efficiently samplable.

Finally, we show that some more sophisticated cryptographic objects

like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object.

15:17 [Pub][ePrint]

Attribute-based encryption (ABE) which allows users to encrypt and decrypt messages based on user attributes is a type of one-to-many encryption. Unlike the conventional one-to-one encryption which has no intention to exclude any partners of the intended receiver from obtaining the plaintext, an ABE system tries to exclude some unintended recipients from obtaining the plaintext whether they are partners of some intended recipients. We remark that this requirement for ABE is very hard to meet. An ABE system cannot truly exclude some unintended recipients from decryption because some users can exchange their decryption keys in order to maximize their own interests. The flaw discounts the importance of the cryptographic primitive.