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]

Human identification protocols are challenge-response protocols that rely on human computational ability to reply to random challenges from the server based on a public function of a shared secret and the challenge to authenticate the human user. One security criterion for a human identification protocol is the number of challenge-response pairs the adversary can observe before it can deduce the secret. In order to increase this number, protocol designers have tried to construct protocols that cannot be represented as a system of linear equations or congruences in the system parameter $n$. In this paper, we take a closer look at different ways from algebra, lattices and coding theory to obtain the secret from a system of linear congruences. We then show two examples of human identification protocols from literature that can be transformed into a system of linear congruences. The resulting attack limits the number of sessions these protocols can be used before secret renewal. Prior to this work, these protocols had no known upper bound on the number of allowable sessions per secret.

15:17 [Pub][ePrint]

In secure two-party computation protocols, the cut-and-choose paradigm is used to prevent the malicious party who constructs the garbled circuits from cheating. In previous realization of the cut-and-choose technique on the garbled circuits, the delivery of the random keys is divided into multiple stages. Thus, the round complexity is high and the consistency of cut-and-choose challenge should be proved.

In this paper, we introduce a new primitive called cut-and-choose bilateral oblivious transfer, which transfers all necessary keys of garbled circuits in one process. Specifically, in our oblivious transfer protocol, the sender inputs two pairs $(x_0,x_1)$, $(y_0,y_1)$ and a bit $\\tau$; the receiver inputs two bits $\\sigma$ and $j$. After the protocol execution, the receiver obtains $x_{\\tau},y_{\\sigma}$ for $j=1$, and $x_0,x_1,y_0,y_1$ for $j=0$.

By the introduction of this new primitive, the round complexity of secure two-party computation protocol can be decreased; the cut-and-choose challenge $j$ is no need to be opened anymore, therefore the consistency proof of $j$ is omitted. In addition, the primitive is of independent interest and could be useful in many cut-and-choose scenarios.

15:17 [Pub][ePrint]

A key source of inefficiency in existing obfuscation schemes is that they operate on programs represented as Boolean circuits

or (with stronger assumptions and costlier constructs) as Turing machines.

We bring the complexity of obfuscation down to the level of RAM programs. That is, assuming injective one way functions and

indistinguishability obfuscators for all circuits, we construct indistinguishability obfuscators for RAM programs with the

following parameters, up to polylogarithmic factors and a multiplicative factor in the security parameter:

(a) The space used by the obfuscated program, as well as the initial size of the program itself, are proportional to the maximum space s used by the plaintext program on any input of the given size.

(b) On each input, the runtime of the obfuscated program is proportional to s plus the runtime of the plaintext program on that input.

The security loss is proportional to the number of potential inputs for the RAM program.

Our construction can be plugged into practically any existing use of indistinguishability obfuscation, such as delegation of computation, functional encryption, non-interactive zero-knowledge, and multi-party computation protocols, resulting in significant efficiency gains. It also gives the first succinct and efficient one-time garbled RAM scheme. The size of the garbled RAM

is proportional to the maximum space $s$ used by the RAM machine, and its evaluation time is proportional to the running time

of the RAM machine on plaintext inputs.

At the heart of our construction is a mechanism for succinctly obfuscating \"iterated circuits\", namely circuits that run in iterations, and where the output of an iteration is used as input to the next. As contributions of independent interest, we also introduce (a) a new cryptographic tool called Asymmetrically Constrained Encapsulation (ACE), that allows us to succinctly and asymmetrically puncture both the encapsulation and decapsulation keys; and (b) a new program analysis tool called Inductive Properties (IP), that allows us to argue about computations that are locally different, but yet globally the same.

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]