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]

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]

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]

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