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

2015-03-26
12:17 [Pub][ePrint] Impossible Differential Cryptanalysis of Reduced Round SIMON, by Zhan Chen and Ning Wang and Xiaoyun Wang

  Impossible differential is a useful method for cryptanalysis. SIMON is a light weight block cipher that has attracted lots of attention ever since its publication in 2013. In this paper we propose impossible differential attack on five versions of SIMON, using bit conditions to minimize key bits guessed. We calculate keybits and give the exact attack results.





2015-03-25
20:54 [Job][New] Internship – M.S./Ph.D. student in Computer Science or a closely related field, Bosch Research and Technology Center North America – 2835 East Carson St., Pittsburgh, PA, 15203 USA

 

Robert Bosch RTC is looking to fill several internship positions in its Software Intensive Systems research group in Pittsburgh to work on a variety of applied cryptography, (embedded and hardware) security, and privacy related projects. Applicants with a history of building secure systems are particular encouraged to apply. Ideal candidates for this position should have experience in one of the following:

  • Applied cryptography and protocols
  • Distributed system security and cloud computing
  • Privacy enhancing technologies
  • Data mining and security
  • Embedded security, hardware security and noisy crypto, PUFs, etc.

Candidates pursuing a Ph.D. in Computer Science or a related area are preferred. Specific internship projects and requirements are as follows:

  • Secure Databases: requires expertise in SQL databases and applied cryptography.
  • Distributed Security: requires expertise in distributed systems and applied crypto. Knowledge and or familiarity with two party or multi-party computation highly desirable.
  • Hardware supported encryption operations: requires expertise in VHDL, FPGAs, and applied crypto. Knowledge of trusted computing, computer architecture are highly desirable.
  • Physics-based security I: requires expertise in signal processing and applied crypto mechanisms. Familiarity and knowledge of data mining, PUFs, watermarking highly desirable.
  • Physics-based security II: requires expert knowledge of image processing algorithms. Familiarity with cryptographic algorithms will be helpful.
  • Software Engineer: expert knowledge of java, software architecture and GUI design. Familiarity with security risk analysis and assessments is desirable.



15:17 [Pub][ePrint] Leakage-Flexible CCA-secure Public-Key Encryption: Simple Construction and Free of Pairing, by Baodong Qin and Shengli Liu

  In AsiaCrypt~2013, Qin and Liu proposed a new approach to CCA-security of Public-Key Encryption (PKE) in the presence of bounded key-leakage, from any universal hash proof system (due to Cramer and Shoup) and any one-time lossy filter (a simplified version of lossy algebraic filters, due to Hofheinz). They presented two instantiations under the DDH and DCR assumptions, which result in leakage rate (defined as the ratio of leakage amount to the secret-key length) of $1/2-o(1)$. In this paper, we extend their work to broader assumptions and to flexible leakage rate, more specifically to leakage rate of $1-o(1)$.

\\begin{itemize}

\\item We introduce the Refined Subgroup Indistinguishability (RSI) assumption, which is a subclass of subgroup indistinguishability assumptions, including many standard number-theoretical assumptions, like the quadratic residuosity assumption, the decisional composite residuosity assumption and the subgroup decision assumption over a group of known order defined by Boneh et al.

\\item We show that universal hash proof (UHP) system and one-time lossy filter (OT-LF) can be simply and efficiently constructed from the RSI assumption. Applying Qin and Liu\'s paradigm gives simple and efficient PKE schemes under the RSI assumption.

\\item With the RSI assumption over a specific group (free of pairing), public parameters of UHP and OT-LF can be chosen in a flexible way, resulting in a leakage-flexible CCA-secure PKE scheme. More specifically, we get the first CCA-secure PKE with leakage rate of $1-o(1)$ without pairing.

\\end{itemize}



15:17 [Pub][ePrint] Dual System Encryption via Predicate Encodings, by Hoeteck Wee

  We introduce the notion of predicate encodings, an information-theoretic primitive reminiscent of linear secret-sharing that in addition, satisfies a novel notion of reusability. Using this notion, we obtain a unifying framework for adaptively-secure public-index predicate encryption schemes for a large class of predicates. Our framework relies on Waters\' dual system encryption methodology (Crypto \'09), and encompass the identity-based encryption scheme of Lewko and Waters (TCC \'10), and the attribute-based encryption scheme of Lewko et al. (Eurocrypt \'10). In addition, we obtain several concrete improvements over prior works. Our work offers a novel interpretation of dual system encryption as a methodology for amplifying a one-time private-key primitive (i.e. predicate encodings) into a many-time public-key primitive (i.e. predicate encryption).



15:17 [Pub][ePrint] Low Depth Circuits for Efficient Homomorphic Sorting, by Gizem S. \\c{C}etin and Yark{\\i}n Dor\\\"{o}z and Berk Sunar and Erkay Sava\\c{s}

  We introduce a sorting scheme which is capable of efficiently sorting encrypted data without the secret key. The technique is obtained by focusing on the multiplicative depth of the sorting circuit alongside the more traditional metrics such as number of comparisons and number of iterations. The reduced depth allows much reduced noise growth and thereby makes it possible to select smaller parameter sizes in somewhat homomorphic encryption instantiations resulting in greater efficiency savings. We first consider a number of well known comparison based sorting algorithms as well as some sorting networks, and analyze their circuit implementations with respect to multiplicative depth. In what follows, we introduce a new ranking based sorting scheme and rigorously analyze the multiplicative depth complexity as $O(\\log(N)+\\log(\\ell))$, where $N$ is the size of the array to be sorted and $\\ell$ is the bit size of the array elements. Finally, we simulate our sorting scheme using a leveled/batched instantiation of a SWHE library. Our sorting scheme performs favorably over the analyzed classical sorting algorithms.



15:17 [Pub][ePrint] MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems, by Takanori Yasuda and Xavier Dahan and Yun-Ju Huang and Tsuyoshi Takagi and Kouichi Sakurai

  Multivariate Quadratic polynomial (MQ) problem serve as the basis of

security for potentially post-quantum cryptosystems.

The hardness of solving MQ problem depends on a number of parameters,

most importantly the number of variables and the degree of the

polynomials, as well as the number of equations, the size of the base

field etc. We investigate the relation among these parameters and the

hardness of solving MQ problem, in order to construct hard instances

of MQ problem. These instances are used to create a challenge, which

may be helpful in determining appropriate parameters for multivariate

public key cryptosystems, and stimulate further the research in

solving MQ problem.



15:17 [Pub][ePrint] An Improvment of the Elliptic Net Algorithm, by Binglong Chen and Chang-An Zhao

  In this paper we propose a modified Elliptic Net algorithm to compute pairings. By reducing the number of the intermediate variables which should be updated in the iteration loop of the Elliptic Net algorithm, we speed up the computation of pairings. Experimental results show that the proposed method is about $14\\%$ faster than the original Elliptic Net algorithm on certain supersingular elliptic curves with embedding degree $two$.



15:17 [Pub][ePrint] One-Sided Device-Independent QKD and Position-based Cryptography from Monogamy Games, by Marco Tomamichel and Serge Fehr and J\\k{e}drzej Kaniewski and Stephanie Wehner

  A serious concern with quantum key distribution (QKD) schemes is that, when under attack, the quantum devices in a real-life implementation may behave differently than modeled in the security proof. This can lead to real-life attacks against provably secure QKD schemes.

In this work, we show that the standard BB84 QKD scheme is one-sided device-independent. This means that security holds even if Bob\'s quantum device is arbitrarily malicious, as long as Alice\'s device behaves as it should. Thus, we can completely remove the trust into Bob\'s quantum device for free, without the need for changing the scheme, and without the need for hard-to-implement loophole-free violations of Bell inequality, as is required for fully (meaning two-sided) device-independent QKD.

For our analysis, we introduce a new quantum game, called a monogamy-of-entanglement game, and we show a strong parallel repetition theorem for this game. This new notion is likely to be of independent interest and to find additional applications. Indeed, besides the application to QKD, we also show a direct application to position-based quantum cryptography: we give the first security proof for a one-round position-verification scheme that requires only single-qubit operations.



15:17 [Pub][ePrint] Efficient Delegation of Zero-Knowledge Proofs of Knowledge in a Pairing-Friendly Setting, by Sébastien Canard and David Pointcheval and Olivier Sanders

  Since their introduction in 1985, by Goldwasser, Micali and Rackoff, followed by Feige, Fiat and Shamir, zero-knowledge proofs have played a significant role in modern cryptography: they allow a party to convince another party of the validity of a statement (proof of membership) or of its knowledge of a secret (proof of knowledge).

Cryptographers frequently use them as building blocks in complex protocols since they offer quite useful soundness features, which exclude cheating players.

In most of modern telecommunication services, the execution of these protocols involves a prover on a portable device, with limited capacities, and namely distinct trusted part and more powerful part. The former thus has to delegate some computations to the latter.

However, since the latter is not fully trusted, it should not learn any secret information.

This paper focuses on proofs of knowledge of discrete logarithm relations sets (DLRS), and the delegation of some prover\'s computations, without leaking any critical information to the delegatee. We will achieve various efficient improvements ensuring perfect zero-knowledge against the verifier and partial zero-knowledge, but still reasonable in many contexts, against the delegatee.



15:17 [Pub][ePrint] Improved Cryptanalysis of AES-like Permutations, by Jérémy Jean and Maria Naya-Plasencia and Thomas Peyrin

  AES-based functions have attracted of a lot of analysis in the recent years,

mainly due to the SHA-3 hash function competition. In particular, the rebound

attack allowed to break several proposals and many improvements/variants of

this method have been published. Yet, it remained an open question whether it

was possible to reach one more round with this type of technique compared to

the state-of-the-art. In this article, we close this open problem by providing

a further improvement over the original rebound attack and its variants, that

allows the attacker to control one more round in the middle of a differential

path for an AES-like permutation. Our algorithm is based on lists merging as

defined by Naya-Plasencia at CRYPTO 2011, and we generalized the concept to

non-full active truncated differential paths proposed by Sasaki et al. at

ASIACRYPT 2010.

As an illustration, we applied our method to the internal permutations used in

Grostl, one of the five finalist hash functions of the SHA-3 competition. When

entering this final phase, the designers tweaked the function so as to thwart

attacks proposed by Peyrin at CRYPTO 2010 that exploited relations between the

internal permutations. Until our results, no analysis was published on Grostl

and the best results reached 8 and 7 rounds for the 256-bit and 512-bit version

respectively. By applying our algorithm, we present new internal permutation

distinguishers on 9 and 10 rounds respectively.



15:17 [Pub][ePrint] Feasibility and Infeasibility of Adaptively Secure Fully Homomorphic Encryption, by Jonathan Katz and Aishwarya Thiruvengadam and Hong-Sheng Zhou

  Fully homomorphic encryption (FHE) is a form of public-key encryption that

enables arbitrary computation over encrypted data.

The past few years have seen several realizations of

FHE under different assumptions, and FHE has been used as a building block in many cryptographic

applications.

\\emph{Adaptive security} for public-key encryption schemes is an important security notion that was proposed

by Canetti et al.\\ over 15 years ago. It is intended to ensure security when encryption is used within an

interactive protocol, and parties may be \\emph{adaptively} corrupted by an adversary

during the course of the protocol execution. Due to the extensive applications of FHE to protocol design, it is natural

to understand whether adaptively secure FHE is achievable.

In this paper we show two contrasting results in this direction. First, we show that adaptive security

is \\emph{impossible} for FHE satisfying the (standard) \\emph{compactness} requirement. On the other hand,

we show a construction of adaptively secure FHE that is not compact, but which does achieve circuit privacy.