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-08-17
21:17 [Pub][ePrint]

An argument system for NP is a proof system that allows efficient verification of NP statements, given proofs produced by an untrusted yet computationally-bounded prover. Such a system is non-interactive and publicly-verifiable if, after a trusted party publishes a proving key and a verification key, anyone can use the proving key to generate non-interactive proofs for adaptively-chosen NP statements, and proofs can be verified by anyone by using the verification key.

We present an implementation of a publicly-verifiable non-interactive argument system for NP. The system, moreover, is a zero-knowledge proof-of-knowledge. It directly proves correct executions of programs on TinyRAM, a random-access machine tailored for efficient verification of nondeterministic computations. Given a program $P$ and time bound T, the system allows for proving correct execution of $P$, on any input $x$, for up to T steps, after a one-time setup requiring $\\tilde{O}(|P| T)$ cryptographic operations. An honest prover requires $\\tilde{O}(|P| \\cdot T)$ cryptographic operations to generate such a proof, while proof verification can be performed with only $O(|x|)$ cryptographic operations. This system can be used to prove the correct execution of C programs, using our TinyRAM port of the GCC compiler.

This yields a zero-knowledge Succinct Non-interactive ARgument of Knowledge (zk-SNARK) for program executions in the preprocessing model -- a powerful solution for delegating NP computations, with several features not achieved by previously-implemented primitives.

Our approach builds on recent theoretical progress in the area. We present efficiency improvements and implementations of two main ingredients:

* Given a C program, we produce a circuit whose satisfiability encodes the correctness of execution of the program. Leveraging nondeterminism, the generated circuit\'s size is merely quasilinear in the size of the computation. In particular, we efficiently handle arbitrary and data-dependent loops, control flow, and memory accesses. This is in contrast with existing circuit generators\'\', which in the general case produce circuits of quadratic size.

* Given a linear PCP for verifying satisfiability of circuits, we produce a corresponding SNARK. We construct such a linear PCP (which, moreover, is zero-knowledge and very efficient) by building on and improving on recent work on quadratic arithmetic programs.

21:17 [Pub][ePrint]

We construct a searchable encryption scheme that enables keyword search over data encrypted with {\\em different} keys. The scheme is practical and was designed to be included in a new system for protecting data confidentiality in client-server applications against attacks on the server.

21:17 [Pub][ePrint]

Our main result gives a way to instantiate the

random oracle with a concrete hash function in

\"full domain hash\" applications.

The term full domain hash was first proposed by Bellare and

Rogaway and referred to a signature scheme from any

trapdoor permutation that was part of their seminal work introducing

the random oracle heuristic. Over time the term full domain hash has

informally encompassed a broader range of notable cryptographic

schemes including the Boneh-Franklin IBE scheme and

Boneh-Lynn-Shacham (BLS) signatures.

All of the above described schemes required a hash function that had

to be modeled as a random oracle to prove security. Our work utilizes

recent advances in indistinguishability obfuscation to construct

specific hash functions for use in these schemes. We then prove

security of the original cryptosystems when instantiated with

our specific hash function.

Of particular interest, our work evades the impossibility result of

Dodis, Oliveira, and Pietrzak, who showed that there can

be no black-box construction of hash functions that allow Full-Domain

Hash Signatures to be based on trapdoor permutations. This indicates

that our techniques applying indistinguishability obfuscation may be

useful in the future for circumventing other such black-box

impossibility proofs.

21:17 [Pub][ePrint]

Several lattice-based cryptosystems require to sample from a discrete Gaussian distribution over the integers. Existing methods to sample from such a distribution either need large amounts of memory or they are very slow. In this paper we explore a different method that allows for a flexible time-memory trade-off, offering developers freedom in choosing how much space they can spare to store precomputed values. We prove that the generated distribution is close enough to a discrete Gaussian to be used in lattice-based cryptography. Moreover, we report on an implementation of the method and compare its performance to existing methods from the literature. We show that for large standard deviations, the Ziggurat algorithm outperforms all existing methods.

21:17 [Pub][ePrint]

In this paper, we present a framework for biclique cryptanalysis of block ciphers with an extremely low data complexity. To that end, we enjoy a new representation of biclique attack. Then an algorithm for choosing two dierential characteristics is also presented to simultaneously minimize the data complexity and control the computational complexity.

Then we characterize those block ciphers that are vulnerable to this technique and among them, we apply this attack on lightweight block ciphers Piccolo-80, Piccolo-128 and HIGHT. The data complexities of these attacks are considerably less than the existing results. For full-round Piccolo-80 and 128, the data complexity of the attacks are only 16

plaintext-ciphertext pairs and for full-round HIGHT our attack requires

256 pairs. In all attacks the computational complexity remains the same

as the previous ones or even it is slightly improved.

21:17 [Pub][ePrint]

In a seminal work at EUROCRYPT \'96, Coppersmith showed how to find all small roots of a univariate polynomial congruence in polynomial time:

this has found many applications in public-key cryptanalysis and in a few security proofs.

However, the running time of the algorithm is a high-degree polynomial,

which limits experiments:

the bottleneck is an LLL reduction of a high-dimensional matrix with extra-large coefficients.

We present in this paper a polynomial speedup over Coppersmith\'s algorithm.

Our improvement is based on a special property of the matrices used by Coppersmith\'s algorithm,

which allows us to speed up the LLL reduction by rounding.

The exact speedup depends on the LLL algorithm used: for instance, the speedup is quadratic

in the bit-size of the small-root bound if one uses the Nguyen-Stehl\\\'e L^2 algorithm.

2013-08-15
09:17 [Pub][ePrint]

In this paper, we present an efficient public-key broadcast encryption (PKBE) scheme with sub-linear size of public keys, private keys, and ciphertexts and prove its adaptive security under standard assumptions. Compared with the currently best scheme that provides adaptive security under standard assumptions and sub-linear size of various parameters, the ciphertext size of our scheme is $94\\%$ shorter and the encryption algorithm of our scheme is also $2.8$ times faster than those of the currently best scheme.

To achieve our scheme, we adapt the dual system encryption technique of Waters. However, there is a challenging problem to use this technique for the construction of PKBE with sub-linear size of ciphertexts such as a tag compression problem. To overcome this problem, we first devise a novel tag update technique for broadcast encryption. Using this technique, we build an efficient PKBE scheme in symmetric bilinear groups, and prove its adaptive security under standard assumptions. After that, we build another PKBE scheme in asymmetric bilinear groups and also prove its adaptive security under simple assumptions.

09:17 [Pub][ePrint]

The increasing demand for on-line collaborative applications has sparked the interest for multicast services, which in many cases have to guarantee properties such as authentication or confidentiality within groups of users.To do so, cryptographic protocols are generally used and the cryptographic keys, in which they rely, have to be managed (e.g. created, updated, distributed). The procedures to perform these operations are determined by the so-called Group Key Management Schemes. Many schemes have been proposed and some

of them have been proven to be vulnerable. This is the case of the Piao et al. scheme, whose scalability/efficiency is very good but it is vulnerable to many attacks because its security is based on a weak\'\' mathematical problem, so it can be broken in polynomial time.

Inspired by the concepts proposed in the Piao et al. scheme we have re-designed the protocol and we have founded it on a hard mathematical problem and tweaked some of the procedures. This way, we propose a new scheme that is efficient, collusion free, and provides backward and forward secrecy.

09:17 [Pub][ePrint]

In this paper we present new constraints to EPCglobal Class 1 Generation 2 (EPC-C1 G2) standard which if they have been considered in the design of EPC-C1 G2 complaint authentication protocols, lead to prevent predecessor\'s protocols\' weaknesses and also present the secure ones. Also in this paper as an example, we use Pang \\textit{et al.} EPC-C1 G2-friendly protocol which has been recently proposed, to show our proposed constraints in EPC-C1 G2 standard. Pang \\textit{et al.}\'s protocol security analysis show how its security claim based on untraceability and resistance against de-synchronization attacks is ruined. More precisely, we present very efficient de-synchronization attack and traceability attack against the protocol. Finally, take Pang \\textit{et al.} protocol\'s vulnerability points, we present new conditions to design EPC-C1 G2 complaint protocols and based on it we propose a secure (EPC-C1 G2) RFID authentication scheme which is a good sample to EPC-C1 G2 complaint protocols.

09:17 [Pub][ePrint]

We propose an optimization and generalization of OT extension of Ishai et al. of Crypto 2003. For computational security parameter k, our OT extension for short secrets offers O(log k) factor performance improvement in communication and computation, compared to prior work. In concrete terms, for today\'s security parameters, this means approx. factor 2-3 improvement.

This results in corresponding improvements in applications relying on

such OT. In particular, for two-party semi-honest SFE, this results in O(log k) factor improvement in communication over state of the art Yao Garbled Circuit, and has the same asymptotic complexity as the recent multi-round construction of Kolesnikov and Kumaresan of SCN 2012. For multi-party semi-honest SFE, where their construction is inapplicable, our construction implies O(log k) factor communication and computation improvement over best previous constructions. As with our OT extension, for today\'s security parameters, this means approximately factor 2 improvement in semi-honest multi-party SFE.

Our building block of independent interest is a novel IKNP-based framework for 1-out-of-n OT extension, which offers O(log n) factor performance improvement over previous work (for n

09:17 [Pub][ePrint]

Cryptographic access control promises to offer easily distributed trust and broader applicability, while reducing reliance on low-level online monitors. Traditional implementations of cryptographic access control rely on simple cryptographic primitives whereas recent endeavors employ primitives with richer functionality and security guarantees. Worryingly, few of the existing cryptographic access-control schemes come with precise guarantees, the gap between the policy specication and the implementation being analyzed only informally, if at all.

In this paper we begin addressing this shortcoming. Unlike prior work that targeted ad-hoc policy specification, we look at the well-established Role-Based Access Control (RBAC) model, as used in a

typical file system. In short, we provide a precise syntax for a computational version of RBAC, offer rigorous denitions for cryptographic policy enforcement of a large class of RBAC security policies, and demonstrate that an implementation based on attribute-based encryption meets our security notions.

We view our main contribution as being at the conceptual level. Although we work with RBAC for concreteness, our general methodology could guide future research for uses of cryptography in other

access-control models.