International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service 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).

2012-12-14
19:17 [Pub][ePrint] Automated Analysis and Synthesis of Padding-Based Encryption Schemes, by Gilles Barthe and Juan Manuel Crespo and Benjamin Grégoire and César Kunz and Yassine Lakhnech and Santiago Zanella-Béguelin

  Verifiable security is an emerging approach in cryptography that

advocates the use of principled tools for building machine-checked

security proofs of cryptographic constructions. Existing tools

following this approach, such as EasyCrypt or CryptoVerif, fall short

of finding proofs automatically for many interesting constructions. In

fact, devising automated methods for analyzing the security of large

classes of cryptographic constructions is a long-standing problem

which precludes a systematic exploration of the space of possible

designs. This paper addresses this issue for padding-based encryption

schemes, a class of public-key encryption schemes built from hash

functions and trapdoor permutations, which includes widely used

constructions such as RSA-OAEP.

Firstly, we provide algorithms to search for proofs of security

against chosen-plaintext and chosen-ciphertext attacks in the random

oracle model. These algorithms are based on domain-specific logics

with a computational interpretation and yield quantitative security

guarantees; for proofs of chosen-plaintext security, we output

machine-checked proofs in EasyCrypt. Secondly, we provide a crawler

for exhaustively exploring the space of padding-based encryption

schemes under user-specified restrictions (e.g. on the size of their

description), using filters to prune the search space. Lastly, we

provide a calculator that computes the security level and efficiency

of provably secure schemes that use RSA as trapdoor permutation.

Using these three tools, we explore over 1.3 million encryption

schemes, including more than 100 variants of OAEP studied in the

literature, and prove chosen-plaintext and chosen-ciphertext security

for more than 250,000 and 17,000 schemes, respectively.





2012-12-11
08:57 [Job][New] faculty position, EPFL, Lausanne, Switzerland, EEA

  The School of Computer and Communication Sciences at EPFL invites applications for faculty positions in computer and communication sciences. We are primarily seeking candidates for tenure-track assistant professor positions; suitably qualified candidates for senior positions will also be considered.

Successful candidates will develop an independent and creative research program, participate in both undergraduate and graduate teaching, and supervise PhD students.

Candidates from all areas of computer science will be considered, but preference will be given to candidates in the fields of machine learning or system security, as well as of computer science theory or human-computer-interaction (HCI). An explicit interest in the fields of medicine or energy is a plus.

EPFL offers internationally competitive salaries, significant start-up resources, and outstanding research infrastructure.

To apply, please follow the application procedure at https://academicjobsonline.org/ajo/jobs/2294

The following documents are requested in PDF format: curriculum vitae, including publication list, brief statements of research and teaching interests, names and addresses (including e-mail) of 3 references for junior positions, and 6 for senior positions. Screening will start on January 15, 2013. Further questions can be addressed to :

Prof. Ruediger URBANKE

Chairman of the recruiting committee

School of Computer and Communication Sciences

EPFL

CH-1015 Lausanne

recruiting.ic (at) epfl.ch

For additional information on EPFL, please consult:

http://www.epfl.ch or http://ic.epfl.ch

EPFL is an equal opportunity employer.



06:38 [Job][New] Research Science, University of Houston, Houston Texas USA

  The post-doctoral researcher will have the opportunity to work in a dynamic and interdisciplinary team, to pursue research in the area of information security. The post-doctoral researcher will be expected to oversee projects, procedures and students, prepare data and write reports/articles for technical publications as well as participate in future grant proposal development.



2012-12-10
13:17 [Pub][ePrint] Hiding the Input-Size in Secure Two-Party Computation, by Yehuda Lindell and Kobbi Nissim and Claudio Orlandi

  In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their inputs, while preserving properties like privacy, correctness, and independence of inputs. One security property that has typically not been considered in the past relates to the length or size of the parties inputs. This is despite the fact that in many cases the size of a party\'s input can be confidential. The reason for this omission seems to have been the folklore belief that, as with encryption, it is impossible to carry out non-trivial secure computation while hiding the size of parties\' inputs. However some recent results (e.g., Ishai and Paskin at TCC 2007, Ateniese, De Cristofaro and Tsudik at PKC 2011) showed that it is possible to hide the input size of one of the parties for some limited class of functions, including secure two-party set intersection. This suggests that the folklore belief may not be fully accurate.

In this work, we initiate a theoretical study of input-size hiding secure computation, and focus on the two-party case. We present definitions for this task, and deal with the subtleties that arise in the setting where there is no a priori polynomial bound on the parties\' input sizes. Our definitional study yields a multitude of classes of input-size hiding computation, depending on whether a single party\'s input size remains hidden or both parties\' input sizes remain hidden, and depending on who receives output and if the output size is hidden from a party in the case that it does not receive output. We prove feasibility and impossibility results for input-size hiding secure two-party computation. Some of the highlights are as follows:

Under the assumption that fully homomorphic encryption (FHE) exists, there exist non-trivial functions (e.g., the millionaire\'s problem) that can be securely computed while hiding the input size of both parties.

Under the assumption that FHE exists, every function can be securely computed while hiding the input size of one party, when both parties receive output (or when the party not receiving output does learn the size of the output). In the case of functions with fixed output length, this implies that every function can be securely computed while hiding one party\'s input size.

There exist functions that cannot be securely computed while hiding both parties\' input sizes. This is the first formal proof that, in general, some information about the size of the parties\' inputs must be revealed.

Our results are in the semi-honest model. The problem of input-size hiding is already challenging in this scenario. We discuss the additional difficulties that arise in the malicious setting and leave this extension for future work.



13:17 [Pub][ePrint] Natural Generalizations of Threshold Secret Sharing, by Oriol Farras,Carles Padro,Chaoping Xing, and An Yang

  We present new families of access structures that, similarly to the multilevel and compartmented access structures introduced in previous works, are natural generalizations of threshold secret sharing. Namely, they admit an ideal linear secret sharing schemes over

every large enough finite field, they can be described by a small number of parameters, and they have useful properties for the applications of secret sharing. The use of integer polymatroids makes it possible to find many new such families and it simplifies in great measure

the proofs for the existence of ideal secret sharing schemes for them.



13:17 [Pub][ePrint] Resilience to Distinguishing Attacks on WG-7 Cipher and Their Generalizations, by Guang Gong and Mark Aagaard and Xinxin Fan

  The stream cipher WG-7 is a lightweight variant of the well-known Welch-Gong (WG) stream cipher family, targeting for resource-constrained devices like RFID tags, smart cards, and wireless sensor nodes. Recently, a distinguishing attack was discovered against the stream cipher WG-7 by Orumiehchiha, Pieprzyk and Steinfeld. In this paper, we

extend their work to a general distinguishing attack and suggest criteria to protect the WG stream cipher family from this attack. Our analysis shows that by properly choosing the minimal polynomial of the linear feedback shift register for a WG stream cipher, the general distinguishing attack can be easily thwarted.



13:17 [Pub][ePrint] Proofs of Retrievability with Public Verifiability and Constant Communication Cost in Cloud, by Jiawei Yuan and Shucheng Yu

  For data storage outsourcing services, it is important to allow data owners to efficiently and securely verify that the storage sever stores their data correctly. To address this issue, several proof-of-retrievability(POR) schemes have been proposed wherein a storage sever must prove to a verifier that all of a client\'s data is stored correctly. While existing POR schemes offer decent solutions addressing various practical issues, they either have a non-trivial (linear or quadratic) communication complexity, or only support private verication - only the data owner can verify the remotely stored data. It remains open to design a POR scheme that achieves both public verifiability and constant communication cost simultaneously.

In this paper, we solve this open problem and propose the first POR scheme with public verifiability and constant communication cost. In our proposed scheme, the message exchanged between the prover and verifier is composed of a const number of the underlying group elements. Different from existing private POR construction, our scheme allows public verification and releases the data owners from burden of being staying online. Thorough analysis and experiments on Amazon S3 show that our proposed scheme is efficient and practical. We prove the security of our scheme based on Computational Diffie-Hellman Assumption, Strong Diffie-Hellman Assumption and Bilinear Strong Diffie-Hellman Assumption.



13:17 [Pub][ePrint] Discarding the Endpoints makes the Cryptanalytic Time-Memory Trade-Offs even Faster, by Gildas Avoine and Adrien Bourgeois and Xavier Carpent

  Cryptanalytic time-memory trade-offs were introduced by Hellman in 1980 in order to perform key-recovery attacks on cryptosystems. A major advance was presented at Crypto 2003 by Oechslin, with the rainbow table variant that outperforms Hellman\'s seminal work.

This paper introduces the fingerprint tables, which drastically reduce the number of false alarms during the attack compared to the rainbow tables. The key point of our technique consists in storing in the tables the fingerprints of the chains instead of their endpoints. The fingerprint tables provide a time-memory trade-off that is about two times faster than the rainbow tables on usual problem sizes. We experimentally illustrate the performance of our technique, and demonstrate that it is faster than Ophcrack, a Windows LM Hash password cracker considered so far to be the fastest one ever implemented.



13:17 [Pub][ePrint] Generic Related-key Attacks for HMAC, by Thomas Peyrin and Yu Sasaki and Lei Wang

  In this article we describe new generic distinguishing and forgery attacks in the related-key scenario (using only a single related-key) for the HMAC construction. When HMAC uses a k-bit key, outputs an n-bit MAC, and is instantiated with an l-bit inner iterative hash function processing m-bit message blocks where m=k, our distinguishing-R attack requires about 2^{n/2} queries which improves over the currently best known generic attack complexity 2^{l/2} as soon as l>n. This means that contrary to the general belief, using wide-pipe hash functions as internal primitive will not increase the overall security of HMAC in the related-key model when the key size is equal to the message block size.

We also present generic related-key distinguishing-H, internal state recovery and forgery attacks. Our method is new and elegant, and uses a simple cycle-size detection criterion. The issue in the HMAC construction (not present in the NMAC construction) comes from the non-independence of the two inner hash layers and we provide a simple patch in order to avoid this generic attack. Our work finally shows that the choice of the opad and ipad constants value in HMAC is important.



13:17 [Pub][ePrint] Square root computation over even extension fields , by Gora Adj and Francisco Rodr\\\'iguez-Henr\\\'iquez

  This paper presents a comprehensive study of the computation of square roots over finite extension fields.

We propose two novel algorithms for computing square roots over even field extensions

of the form $\\F_{q^{2}}$, with $q=p^n,$ $p$ an odd prime and $n\\geq 1$. Both algorithms have an associate

computational cost roughly equivalent to one exponentiation in $\\F_{q^{2}}$.

The first algorithm is devoted to the case when $q\\equiv 1 \\bmod 4$, whereas the second one handles the case when

$q\\equiv 3 \\bmod 4$. Numerical comparisons show that the two algorithms presented in this paper are competitive

and in some cases more efficient than the square root methods previously known.



13:17 [Pub][ePrint] Improved (Pseudo) Preimage Attack and Second Preimage Attack on Round-Reduced Gr{\\o}stl, by Jian Zou and Wenling Wu and Shuang Wu and Le Dong

  Gr{\\o}stl is one of the five finalists in the third round of SHA-3

competition hosted by NIST. In this paper, we use many techniques to

improve the pseudo preimage attack on Gr{\\o}stl hash function, such

as subspace preimage attack and guess-and-determine technique. We

present improved pseudo preimage attacks on 5-round Gr{\\o}stl-256

and 8-round Gr{\\o}stl-512 respectively. The complexity of the above

two attacks are ($2^{239.90},2^{240.40}$) (in time and memory) and

($2^{499.50},2^{499}$) respectively. Furthermore, we propose pseudo

preimage attack and pseudo second preimage attack on 6-round

Gr{\\o}stl-256. The complexity of our 6-round pseudo preimage and

second preimage attack is ($2^{253.26},2^{253.67}$) and

($2^{251.0},2^{252.0}$) respectively. As far as we know, these are

the best known attacks on round-reduced Gr{\\o}stl hash function.