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

2015-03-25
15:17 [Pub][ePrint]

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]

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]

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]

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

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.

15:17 [Pub][ePrint]

We show a general connection between various types of statistical zero-knowledge (SZK) proof systems and (unconditionally secure) secret sharing schemes. Viewed through the SZK lens, we obtain several new results on secret-sharing:

Characterizations: We obtain an almost-characterization of access structures for which there are secret-sharing schemes with an efficient sharing algorithm (but not necessarily efficient reconstruction). In particular, we show that for every language $L \\in \\SZKL$ (the class of languages that have statistical zero knowledge proofs with log-space verifiers and simulators), a (monotonized) access structure associated with $L$ has such a secret-sharing scheme. Conversely, we show that such secret-sharing schemes can only exist for languages in $\\SZK$.

Constructions: We show new constructions of secret-sharing schemes with efficient sharing and reconstruction for access structures that are in $\\P$, but are not known to be in $\\NC$, namely Bounded-Degree Graph Isomorphism and constant-dimensional lattice problems. In particular, this gives us the first combinatorial access structure that is conjectured to be outside $\\NC$ but has an efficient secret-sharing scheme. Previous such constructions (Beimel and Ishai; CCC 2001) were algebraic and number-theoretic in nature.

Limitations: We show that universally-efficient secret-sharing schemes, where the complexity of computing the shares is a polynomial independent of the complexity of deciding the access structure, cannot exist for all (monotone languages in) $\\P$, unless there is a polynomial $q$ such that $\\P \\subseteq \\DSPACE(q(n))$.

15:17 [Pub][ePrint]

In recent years, secure two-party computation (2PC) has been demonstrated to be feasible in practice. However, all efficient general-computation 2PC protocols require multiple rounds of interaction between the two players. This property restricts 2PC to be only relevant to scenarios where both players can be simultaneously online, and where communication latency is not an issue.

This work considers the model of 2PC with a single round of interaction, called Non-Interactive Secure Computation (NISC). In addition to the non-interaction property, we also consider a flavor of NISC that allows reusing the first message for many different 2PC invocations, possibly with different players acting as the player who sends the second message, similar to a public-key encryption where a single public-key can be used to encrypt many different messages.

We present a NISC protocol that is based on the cut-and-choose paradigm of Lindell and Pinkas (Eurocrypt 2007). This protocol achieves concrete efficiency similar to that of best multi-round 2PC protocols based on the cut-and-choose paradigm. The protocol requires only $t$ garbled circuits for achieving cheating probability of $2^{-t}$, similar to the recent result of Lindell (Crypto 2013), but only needs a single round of interaction.

To validate the efficiency of our protocol, we provide a prototype implementation of it and show experiments that confirm its competitiveness with that of the best multi-round 2PC protocols. This is the first prototype implementation of an efficient NISC protocol.

In addition to our NISC protocol, we introduce a new encoding technique that significantly reduces communication in the NISC setting. We further show how our NISC protocol can be improved in the multi-round setting, resulting in a highly efficient constant-round 2PC that is also suitable for pipelined implementation.

11:35 [Event][New]

Submission: 13 July 2015
From January 10 to January 13
Location: Tel Aviv, Israel

10:36 [News]

Starting this year, the IACR is introducing an annual TCC Test-of-Time (ToT) award. The award recognizes outstanding papers, published in TCC at least eight years ago, making a significant contribution to the theory of cryptography, preferably with influence also in other area of cryptography, theory, and beyond. The inaugural 2015 TCC ToT award was announced this week at the TCC business meeting in Warsaw. The winners are Silvio Micali and Leonid Reyzin, for their paper "Physically Observable Cryptography" from TCC 2004. The award committee recognized Micali and Reyzin "for pioneering a mathematical foundation of cryptography in the presence of information leakage in physical systems."

10:23 [News]

Dear members of the IACR

With the spring conference season in full swing, you have certainly noticed a few changes in IACR's workshops and conferences.

Online proceedings

The online proceedings of TCC 2015 and PKC 2015 are now available to members via the IACR online library at http://www.iacr.org/services/springer.php

Based on IACR's arrangement with Springer, we install access for members to conference proceedings as soon as these are available, which is usually a few weeks before the event. We also implement online access to everyone during the time of the conference and this is valid for a few weeks afterwards. Technically, this uses "referer" authorization, where the general chair includes a link to the online proceedings in the conference website.

In that context, recall that all IACR proceedings four years and older are available as "Gold Open Access" (that is, openly from the publisher's online library), and the younger ones are "Green Open Access."

Submission format:

Compared to when IACR started to publish conference proceedings, authors are nowadays formatting the "final" versions of papers almost by themselves; based on common tools and style files, the result also looks much more uniform than 30 years ago. Discussions among authors, program chairs, the Board of Directors, and conference reviewers during 2014 have now resulted in a change to the "traditional" submission format of N pages, 11pt font, and A4/letter size. For EUROCRYPT and CRYPTO in 2015, the LNCS style of the final version has been preferred or even declared mandatory. As could be expected, this change has created some confusion, but we trust that this was just a transition effect.

The Board, as the representative of all IACR members, acknowledges that there should be continuity across IACR publications. A corresponding policy is being worked out right now and should be adopted uniformly by the community. The main reason to format submissions in the same way as the final accepted version is to make transparent to readers, as well as to reviewers, that the published version and the reviewed version correspond to each other in length and scope. However, no bound on "supplementary material" is foreseen and authors are still strongly encouraged to revise and improve their submissions based on the feedback received.

Parallel sessions:

As explained in my news update from September last year, the Board has asked EUROCRYPT, CRYPTO, and ASIACRYPT to organize parallel sessions for a significant part of the program. EUROCRYPT in Sofia will be the first IACR conference with parallel sessions, and I invite you to check out the program on the website. At the end of this year, we will hold a referendum among the IACR membership for deciding whether the format should be kept like this.

Cryptology Schools:

The Board has approved funding for the following IACR Cryptology Schools:

1. SAC Summer School (S3). August 10--12, 2015, Sackville, New Brunswick, Canada. Contact: Orr Dunkelman and Liam Keliher
2. School on Computer-Aided Cryptography: sometime between May 20th and July 10th, 2015, University of Maryland. Contact: Benedikt Schmidt