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).

2013-06-10
20:42 [PhD][New]

Name: Christian Rechberger

18:55 [Job][New]

PhD and Post-doc Positions in Computer Security

The University of Luxembourg in collaboration with the Luxembourg Government (CTIE) will start a new research project “Supporting e-Democracy” for which we have two PhD candidates and one Research Associate (post-doc) positions available. The positions are within the APSIA (Applied Security and Information Assurance) (http://wwwen.uni.lu/snt/research/apsia) research group led by Prof. Dr. P.Y. Ryan.

The successful candidates will be working in an exciting, international and multicultural environment in the heart of Europe.

Project Description

The successful candidates will be working within the research project “Supporting e-Democracy”, collaboration between the University of Luxembourg and the Luxembourg Government (CTIE).

The research will focus on (a) design and security analysis of accurate and robust communication systems in specific electoral systems (b) design of reliable and secure computer assisted counting of paper ballots, (c) design and analysis of verifiable, computer assisted voting systems and a broader e-democracy platform.

Candidates Profile

The candidates are expected to have:

• A previous degree in computer science or related subject;

• A proven (theoretical and practical) interest in security;

• Knowledge of Network and System security;

• Fluent written and oral English skills;

Applications

The candidates must apply online at the following addresses:

PhD positions (open until July 31st, 2013): http://recruitment.uni.lu/en/details.html?id=QMUFK026203F3VBQB7V7VV4S8&nPostingID=2253&nPostingTargetID=2935&mask=karriereseiten&lg=UK

Research Associate position (open until June 20th, 2013): http://recruitment.uni.lu/en/details.html?id=QMUFK026203F3VBQB7V7VV4S8&nPostingID=2254&nPostingTargetID=2893&mask=karriereseiten&lg=UK

15:17 [Pub][ePrint]

Preneel et al.~(Crypto 1993) assessed 64 possible ways to construct a compression function out of a blockcipher. They conjectured that 12 out of these 64 so-called PGV constructions achieve optimal security bounds for collision resistance and preimage resistance. This was proven by Black et al.~(Journal of Cryptology, 2010), if one assumes that the blockcipher is ideal. This result, however, does not apply to non-ideal\'\' blockciphers such as AES. To alleviate this problem, we revisit the PGV constructions in light of the recently proposed idea of random-oracle reducibility (Baecher and Fischlin, Crypto 2011). We say that the blockcipher in one of the 12 secure PGV constructions reduces to the one in another construction, if \\emph{any} secure instantiation of the cipher, ideal or not, for one construction also makes the other secure. This notion allows us to relate the underlying assumptions on blockciphers in different constructions, and show that the requirements on the blockcipher for one case are not more demanding than those for the other. It turns out that this approach divides the 12 secure constructions into two groups of equal size, where within each group a blockcipher making one construction secure also makes all others secure. Across the groups this is provably not the case, showing that the sets of good\'\' blockciphers for each group are qualitatively distinct. We also relate the ideal ciphers in the PGV constructions with those in double-block-length hash functions such as Tandem-DM, Abreast-DM, and Hirose-DM. Here, our results show that, besides achieving better bounds, the double-block-length hash functions rely on weaker assumptions on the blockciphers to achieve collision and everywhere preimage resistance.

15:17 [Pub][ePrint]

Several research teams have recently been working toward the development of practical general-purpose protocols for verifiable computation. These protocols enable a computationally weak verifier to offload computations to a powerful but untrusted prover, while providing the verifier with a guarantee that the prover performed the requested computations correctly. Despite substantial progress, existing implementations require further improvements before they become practical for most settings. The main bottleneck is typically the extra effort required by the prover to return an answer with a guarantee of correctness, compared to returning an answer with no guarantee.

We describe a refinement of a powerful interactive proof protocol due to Goldwasser, Kalai, and Rothblum. Cormode, Mitzenmacher, and Thaler show how to implement the prover in this protocol in time $O(S \\log S)$, where $S$ is the size of an arithmetic circuit computing the function of interest. Our refinements apply to circuits with sufficiently regular\'\' wiring patterns; for these circuits, we bring the runtime of the prover down to $O(S)$. That is, our prover can evaluate the circuit with a guarantee of correctness, with only a constant-factor blowup in work compared to evaluating the circuit with no guarantee.

We argue that our refinements capture a large class of circuits, and we complement our theoretical results with experiments on problems such as matrix multiplication and determining the number of distinct elements in a data stream. Experimentally, our refinements yield a 200x speedup for the prover over the implementation of Cormode et al., and our prover is less than 10x slower than a C++ program that simply evaluates the circuit. Along the way, we describe a special-purpose protocol for matrix multiplication that is of interest in its own right.

Our final contribution is the design of an interactive proof protocol targeted at general data parallel computation. Compared to prior work, this protocol can more efficiently verify complicated computations as long as that computation is applied independently to many different pieces of data.

15:17 [Pub][ePrint]

We put forward a new notion of pseudorandom functions (PRFs) we call

constrained PRFs. In a standard PRF there is a master key k that enables one to evaluate the function at all points in the domain of the

function. In a constrained PRF it is possible to derive constrained keys kS from the master key k. A constrained key kS enables the

evaluation of the PRF at a certain subset S of the domain and

nowhere else. We present a formal framework for this concept and show

that constrained PRFs can be used to construct powerful primitives such as identity-based key exchange and an optimal private broadcast

encryption system. We then construct constrained PRFs for several natural set systems needed for these applications. We conclude with several open problems relating to this new concept.

15:17 [Pub][ePrint]

Linear regression-based methods have been proposed as efficient means of characterising device leakage in the training phases of profiled side-channel attacks. Empirical comparisons between these and the classical\' approach to template building have confirmed the reduction in profiling complexity to achieve the same attack-phase success, but have focused on a narrow range of leakage scenarios which are especially favourable to simple (i.e.\\ efficiently estimated) model specifications. In this contribution we evaluate---from a theoretic perspective as much as possible---the performance of linear regression-based templating in a variety of realistic leakage scenarios as the complexity of the model specification varies. We are particularly interested in complexity trade-offs between the number of training samples needed for profiling and the number of attack samples needed for successful DPA: over-simplified models will be cheaper to estimate but DPA using such a degraded model will require more data to recover the key. However, they can still offer substantial improvements over non-profiling strategies relying on the Hamming weight power model, and so represent a meaningful middle-ground between no\' prior information and full\' prior information.

15:17 [Pub][ePrint]

We adapt the concept of a programmable hash function (PHF, Crypto 2008) to a setting in which a multilinear map is available. This enables new PHFs with previously unachieved parameters.

To demonstrate their usefulness, we show how our (standard-model) PHFs can replace random oracles in several well-known cryptographic constructions. Namely, we obtain standard-model versions of the Boneh-Franklin identity-based encryption scheme, the Boneh-Lynn-Shacham signature scheme, and the Sakai-Ohgishi-Kasahara identity-based non-interactive key exchange (ID-NIKE) scheme. The ID-NIKE scheme is the first scheme of its kind in the standard model.

Our abstraction also allows to derive hierarchical versions of the above schemes in settings with multilinear maps. This in particular yields simple and efficient hierarchical generalizations of the BF, BLS, and SOK schemes. In the case of hierarchical ID-NIKE, ours is the first such scheme with full security, in either the random oracle model or the standard model.

While our constructions are formulated with respect to a generic multilinear map, we also outline the necessary adaptations required for the recent `noisy\'\' multilinear map candidate due to Garg, Gentry, and Halevi.

15:17 [Pub][ePrint]

In this paper we demonstrate a number of attacks against proposed protocols for privacy-preserving linear programming, based on publishing and solving a transformed version of the problem instance. Our attacks exploit the geometric structure of the problem, which has

mostly been overlooked in the previous analyses and is largely preserved by the proposed transformations. The attacks are efficient in practice and cast serious doubt to the viability of transformation-based approaches in general.

15:17 [Pub][ePrint]

When outsourcing computations to the cloud or other

third-parties, a key issue for clients is the ability to

verify the results. Recent work in proof-based verifiable

computation, building on deep results in complexity theory

and cryptography, has made significant progress on this

problem. However, all existing systems require computational

models that do not incorporate state. This limits these

systems to simplistic programming idioms and rules out

computations where the client cannot materialize all of the

input (e.g., very large MapReduce instances or database

queries).

This paper describes Pantry, the first built system that

incorporates state. Pantry composes the machinery of

proof-based verifiable computation with ideas from untrusted

storage: the client expresses its computation in terms of

digests that attests to state, and verifiably outsources

that computation. Besides the boon to expressiveness, the

client can gain from outsourcing even when the computation

is sublinear in the input size. We describe a verifiable

MapReduce application and a queriable database, among other

simple applications. Although the resulting applications

result in server overhead that is higher than we would like,

Pantry is the first system to provide verifiability for

realistic applications in a realistic programming model.

15:17 [Pub][ePrint]

We show how to produce a forged (ciphertext,tag) pair for the scheme ALE with data and time complexity of 2^102 ALE encryptions of short messages and the same number of authentication attempts.

We use a differential attack based on a local collision, which exploits the availability of extracted state bytes to the adversary. Our approach allows for a time-data complexity tradeoff, with an extreme case of a forgery produced after \$2^119 attempts and based on a single authenticated message. Our attack is further turned into a state recovery and a universal forgery attack with a time complexity of 2^120 verification attempts using only a single authenticated 48-byte message.

15:17 [Pub][ePrint]

We introduce \\emph{counter-cryptanalysis} as a new paradigm for strengthening weak cryptographic primitives against cryptanalytic attacks.

Redesigning a weak primitive to more strongly resist cryptanalytic techniques will unavoidably break backwards compatibility.

Instead, counter-cryptanalysis exploits unavoidable anomalies introduced by cryptanalytic attacks to detect and block

cryptanalytic attacks while maintaining full backwards compatibility.

Counter-cryptanalysis in principle enables the continued secure use of weak cryptographic primitives.

Furthermore, we present the first example of counter-cryptanalysis, namely the efficient detection whether any given single message has been constructed -- together with an \\emph{unknown} sibling message -- using a cryptanalytic collision attack on MD5 or SHA-1.

An immediate application is in digital signature verification software to ensure that an (older) MD5 or SHA-1 based digital signature is not a forgery using a collision attack.

This would certainly be desirable for two reasons.

Firstly, it might still be possible to generate malicious forgeries using collision attacks as too many parties still sign using MD5 (or SHA-1) based signature schemes.

Secondly, any such forgeries are currently accepted nearly everywhere due to the ubiquitous support of MD5 and SHA-1 based signature schemes.

Despite the academic push to use more secure hash functions over the last decade, these two real-world arguments (arguably) will remain valid for many more years.

Only due to counter-cryptanalysis were we able to discover that Flame,

a highly advanced malware for cyberwarfare uncovered in May 2012,

employed an as of yet unknown variant of our chosen-prefix collision attack on MD5 \\cite{DBLP:conf/eurocrypt/StevensLW07,DBLP:conf/crypto/StevensSALMOW09}.

In this paper we disect the revealed cryptanalytic details and work towards the reconstruction of the algorithms underlying Flame\'s new variant attack.

Finally, we make a preliminary comparision between Flame\'s attack and our chosen-prefix collision attack.