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-30
15:17 [Pub][ePrint]

This paper investigates pairs of AES-128 cipher keys and plaintexts which result in being quiet\'\' in the final round, i.e., whose 128-bit State holds the same bit pattern before and after Round 10. We show that the number of such quiet plaintexts (resulting in Hamming distance 0) for any cipher key is at most 5,914,624, and that there exist exactly 729 cipher keys having such a maximum number. The same holds if quiet\'\' is replaced by noisy\'\' (which means to have Hamming distance 128). Because such quiet and noisy plaintexts make extreme actions in the final round of the AES encryption, these AES-128 cipher keys are quite useful for AES hardware designers to efficiently evaluate the vulnerabilities of their products, for instance, the performance of their side-channel attack countermeasures.

15:17 [Pub][ePrint]

A {\\em randomized encoding} allows to represent a complex\'\' function $f(x)$ by a simpler\'\' randomized function $\\hat{f}(x;r)$ whose output distribution encodes $f(x)$, while revealing nothing else regarding $x$. Existing randomized encodings, geared mostly to allow encoding with low parallel complexity, have proven instrumental in various strong applications such as multiparty computation and parallel cryptography.

This work focuses on another natural complexity measure: {\\em the time required to encode}. We construct {\\em succinct randomized encodings} where a computation given by a (Turing or random-access) machine $M$, and input $x$, requiring time $t$ and space $s$, can be encoded roughly in time $\\poly(|x|,\\log t,s)$, thus inducing significant savings in time when $s \\ll t$. The scheme guarantees computational input-privacy and is based on indistinguishability obfuscation for a relatively simple circuit class, which can in turn be based on a polynomial version of the subgroup elimination assumption on multilinear graded encodings.

We then invoke succinct randomized encodings to obtain several strong applications, including:

\\begin{itemize}

\\item

Indistinguishability obfuscation for uniform (Turing or random-access) machines, where the obfuscated machine $\\iO(M)$ computes the same function as $M$ for inputs $x$ of apriori-fixed maximal size $n$, and is computed in time $\\poly(n,\\log t,s)$.

\\item

Functional encryption for uniform machines, where a functional decryption key corresponding to $M$ allows decrypting $M(x)$ from encryptions of $x$. As in the previous case, inputs $x$ are of apriori-fixed maximal size $n$, and key derivation time is roughly $\\poly(n,\\log t,s)$.

\\item

Publicly-verifiable 2-message delegation where verification time is roughly $\\poly(n,\\log t,s)$. We also show how to transform any 2-message delegation scheme to an essentially non-interactive system where the verifier message is reusable.

\\end{itemize}

For the first application, we also require subexponentially-secure indistinguishability obfuscation for circuits, and for the second polynomial indistinguishability obfuscation, which can be replaced by more concrete polynomial hardness assumptions on multilinear graded-encodings. Previously, both applications were only known based on various non-standard knowledge assumptions.

14:42 [Job][New]

What we offer:

We offer three predoctoral grants motivated by the start of two large research projects related to security, privacy, cryptography and the economics of privacy.

The candidates\' primary job will be to do research within the project. Additionally, they are expected to submit a PhD thesis based on the research carried out.

What we require:

Candidates should have a Master\'s degree in Computer Science. Also acceptable is a Master\'s degree in Economics or Social Sciences, as long as the candidate\'s skills in mathematics and computer science are demonstrably good. Knowledge of cryptographic protocols, game theory and/or behavioural economics will be regarded as an additional merit.

Where we are:

Universitat Rovira i Virgili (URV) is based in Tarragona (Catalonia), which is a coastal city 90 km south of Barcelona. URV has been ranked by Times Higher Education 2014 as the world´s 66th best university under 50 years of age. Also, according to the CWTS Leiden 2014 ranking, URV has the second highest research impact on Math., Comp. Sci. and Engineering´´ among European universities. According to the Shanghai ARWU ranking, URV is one of the world\'s top 200 universities in computer science.

What candidates should send:

Send your CV and publication record, plus two recommendation letters to

Prof. Josep Domingo-Ferrer ( josep.domingo (at) urv.cat ).

2014-09-29
17:14 [PhD][New]

Name: Florian Legendre
Topic: Exploitation de la logique propositionnelle pour la résolution de problèmes cryptograhiques
Category: secret-key cryptography

Description: Democratization of increasingly high-performance digital technologies and especially the Internet has considerably changed the world of communication. Consequently, needs in cryptography are more and more numerous and the necessity of verifying the security of cipher algorithms is essential. This thesis deals with a new cryptanalysis, called logical cryptanalysis, which is based on the use of logical formalism to express and solve cryptographic problems. More precisely, works presented here focuses on a particular category of ciphers, called cryptographic hash functions, used in authentication and data integrity protocols. The first contribution is the modeling of a cryptographic problem as a SAT problem. For this, we present some rules that lead to describe easily basic operations involved in cipher algorithms. Then, a section is dedicated to logical reasoning in order to simplify the produced SAT formulas and show how satisfiability can help to enrich a knowledge on a studied problem. Furthermore, we also present many points of view to use our smooth modeling to apply a probabilistic reasoning on all the data associated with the generated SAT formulas. This has then allowed to improve both the modeling and the solving of the problem and underlined a weakness about the use of round constants. Second, a section is devoted to practical attacks. Within this framework, we tackled preimages and the collision problem of the most popular cryptographic hash functions[...]

12:08 [Event][New]

From September 28 to September 30
Location: Bordeaux, France

09:17 [Pub][ePrint]

Detecting hardware trojans is a difficult task in general.

In this article we study hardware trojan horses insertion and detection in cryptographic intellectual property (IP) blocks.

The context is that of a fabless design house that sells IP blocks as GDSII hard macros, and wants to check that final products have not been infected by trojans during the foundry stage.

First, we show the efficiency of a medium cost hardware trojans detection method if the placement or the routing have been redone by the foundry.

It consists in the comparison between optical microscopic pictures of the silicon product and the original view from a GDSII layout database reader.

Second, we analyze the ability of an attacker to introduce a hardware trojan horse without changing neither the placement nor the routing of the cryptographic IP logic.

On the example of an AES engine, we show that if the placement density is beyond $80$\\%, the insertion is basically impossible.

Therefore, this settles a simple design guidance to avoid trojan horses insertion in cryptographic IP blocks:

have the design be compact enough, so that any functionally discreet trojan necessarily requires a complete re-place and re-route, which is detected by mere optical imaging (and not complete chip reverse-engineering).

09:17 [Pub][ePrint]

Higher-order differential power analysis attacks are a serious threat for cryptographic hardware implementations. In particular, glitches in the circuit make it hard to protect the implementation with masking. The existing higher-order masking countermeasures that guarantee security in the presence of glitches use multi-party computation techniques and require a lot of resources in terms of circuit area and randomness. The Threshold Implementation method is also based on multi-party computation but it is more area and randomness efficient. Moreover, it typically requires less clock-cycles since all parties can operate simultaneously. However, so far it is only provable secure against 1st-order DPA. We address this gap and extend the Threshold Implementation technique to higher orders. We define generic constructions and prove their security. To illustrate the approach, we provide 1st, 2nd and 3rd-order DPA-resistant implementations of the block cipher KATAN- 32. Our analysis of 300 million power traces measured from an FPGA implementation supports the security proofs.

09:17 [Pub][ePrint]

09:17 [Pub][ePrint]

In the problem of anonymous authentication (Boneh et al. CCS 1999), a sender wishes to authenticate a message to a given recipient in a way that preserves anonymity: the recipient does not know the identity of the sender and only is assured that the sender belongs to some authorized set. Although solutions for the problem exist (for example, by using ring signatures, e.g. Naor, Crypto 2002), they provide no security when the anonymity set is a singleton. This work is motivated by the question of whether there is any type of anonymity possible in this scenario. It turns out that we can still protect the identity of all senders (authorized or not) if we shift our concern from preventing the identity information be revealed to the recipient to preventing it could be revealed to an external entity, other than the recipient. We define a natural functionality which provides such guarantees and we denote it by F_{eaa} for externally anonymous authenticated channel.

We argue that any realization of F_{eaa} must be deniable in the sense of Dodis et al. TCC 2009. To prove the deniability of similar primitives, previous work defined ad hoc notions of deniability for each task, and then each notion was showed equivalent to realizing the primitive in the Generalized Universal Composability framework (GUC, Canetti et al. TCC 2007). Instead, we put forward the question of whether deniability can be defined independently from any particular task. We answer this question in the affirmative providing a natural extension of the definition of Dodis et al. for arbitrary multiparty protocols. Furthermore, we show that a protocol satisfies this definition if an only if it realizes the ideal functionality F_{eaa} in the GUC framework. This result enables us to prove that most GUC functionalities we are aware of (and their realizations) are deniable.

We conclude by applying our results to the construction of a deniable protocol that realizes F_{eaa}.

09:17 [Pub][ePrint]

We develop a technique inspired by pseudorandom functions that allows us to increase the entropy available for proving the security of dual system encryption schemes under the Decisional Linear Assumption. We show an application of the tool to Attribute-Based Encryption by presenting a Key-Policy ABE scheme that exhibits a significant improvement over the state of the art schemes in public parameter size in terms of the number of reuses of attributes allowed in the policy while remaining fully secure under the Decisional Linear Assumption.

09:17 [Pub][ePrint]

Encryption algorithms are designed to be difficult to break without knowledge of the secrets or keys. To achieve this, the algorithms require the keys to be large, with some algorithms having a recommend size of 2048-bits or more. However most modern processors only support computation on 64-bits at a time. Therefore standard operations with large numbers are more complicated to implement. One operation that is particularly challenging to implement efficiently is modular reduction. In this paper we propose a highly-efficient algorithm for solving large modulo operations; it has several advantages over current approaches as it supports the use of a variable sized lookup table, has good spatial and temporal locality allowing data to be streamed, and only requires basic processor instructions. Our proposed algorithm is theoretically compared to widely used modular algorithms, before practically compared against the state-of-the-art GNU Multiple Precision (GMP) large number library.