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

2014-10-12
03:17 [Pub][ePrint]

We consider interactive proof systems over adversarial communication channels. We show that the seminal result that $\\ip = \\pspace$ still holds when the communication channel is malicious, allowing even a constant fraction of the communication to be arbitrarily corrupted.

00:17 [Pub][ePrint]

We present a lattice-based stateless signature scheme provably secure in the standard model. Our

scheme has a constant number of matrices in the public key and a single lattice vector (plus a tag) in the

signatures. The best previous lattice-based encryption schemes were the scheme of Ducas and Micciancio

(CRYPTO 2014), which required a logarithmic number of matrices in the public key and that of Bohl et.

al (J. of Cryptology 2014), which required a logarithmic number of lattice vectors in the signature. Our

main technique involves using fully homomorphic computation to compute a degree d polynomial over

the tags hidden in the matrices in the public key. In the scheme of Ducas and Micciancio, only functions

linear over the tags in the public key matrices were used, which necessitated having d matrices in the

public key.

As a matter of independent interest, we extend Wichs\' (eprint 2014) recent construction of homomorphic

trapdoor functions into a primitive we call puncturable homomorphic trapdoor functions (PHTDFs).

This primitive abstracts out most of the properties required in many different lattice-based cryptographic

constructions. We then show how to combine a PHTDF along with a function satisfying certain properties

(to be evaluated homomorphically) to give an eu-scma signature scheme.

00:17 [Pub][ePrint]

We introduce a novel concept of dual-system simulation-sound non-interactive zero-knowledge (NIZK) proofs. Dual-system NIZK proof system can be seen as a two-tier proof system. As opposed to the usual notion of zero-knowledge proofs, dual-system defines an intermediate partial-simulation world, where the proof simulator may have access to additional auxiliary information about the potential language member, for example a membership bit, and simulation of proofs is only guaranteed if the membership bit is correct. Further, dual-system NIZK proofs allow a quasi-adaptive setting where the CRS can be generated based on language parameters. This allows for the further possibility that the partial-world CRS simulator may have access to further trapdoors related to the language parameters. We show that for important hard languages like the Diffie-Hellman language, such dual-system proof systems can be given which allow unbounded partial simulation soundness, and which further allow transition between partial simulation world and single-theorem full simulation world even when proofs are sought on non-members. The construction is surprisingly simple, involving only two additional group elements in asymmetric bilinear pairing groups.

As a first application we show a first single-round universally-composable password authenticated key-exchange (UC-PAKE) protocol

which is secure under dynamic corruption in the erasure model. The single message flow only requires four group elements under the SXDH assumption, which is at least two times shorter than earlier schemes.

As another application we give a short keyed-homomorphic CCA-secure encryption scheme. The ciphertext in this scheme consist of only six group elements (under the SXDH assumption) and the security reduction is linear-preserving. An earlier scheme of Libert et al based on their efficient unbounded simulation-sound QA-NIZK proofs only provided a quadratic-preserving security reduction, and further had ciphertexts almost twice as long as ours.

00:17 [Pub][ePrint]

The paper is about the discrete logarithm problem for elliptic curves over characteristic 2 finite fields F_2^n of prime degree n. We consider practical issues about index calculus attacks using summation polynomials in this setting. The contributions of the paper include: a choice of variables for binary Edwards curves (invariant under the action of a relatively large group) to lower the degree of the summation polynomials; a choice of factor base that \"breaks symmetry\" and increases the probability of finding a relation; an experimental investigation of the use of SAT solvers rather than Gr{\\\" o}bner basis methods for solving multivariate polynomial equations over F2. We show that our choice of variables gives a significant improvement to previous work in this case. The symmetry breaking factor base and use of SAT solvers seem to give some benefits in practice, but our experimental results are not conclusive. Our work indicates that Pollard rho is still much faster than index calculus algorithms for the ECDLP (and even for variants such as the oracle-assisted static Diffie-Hellman problem of Granger and Joux-Vitse) over prime extension fields F_2^n of reasonable size.

00:17 [Pub][ePrint]

A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \\emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \\emph{tampering} attacks where the adversary can modify this state. One of the popular tools used to provide tamper-resistance are the \\emph{non-malleable codes} introduced by Dziembowski, Pietrzak and Wichs (ICS 2010). These codes can be defined in several variants, but arguably the most natural of them are the information-theoretically secure codes in the k-split-state model (the most desired case being k=2).

Such codes were constucted recently by Aggarwal et al.~(STOC 2014). Unfortunately, unlike the earlier, computationally-secure constructions (Liu and Lysyanskaya, CRYPTO 2012) these codes are not known to be resilient to leakage. This is unsatisfactory, since in practice one always aims at providing resilience against both leakage and tampering (especially considering tampering without leakage is problematic, since the leakage attacks are usually much easier to perform than the tampering attacks).

In this paper we close this gap by showing a non-malleable code in the $2$-split state model that is secure against leaking almost a $1/12$-th fraction of the bits from the codeword (in the bounded-leakage model). This is achieved via a generic transformation that takes as input any non-malleable code $(\\Enc,\\Dec)$ in the $2$-split state model, and constructs out of it another non-malleable code $(\\Enc\',\\Dec\')$ in the $2$-split state model that is additionally leakage-resilient. The rate of $(\\Enc\',\\Dec\')$ is linear in the rate of $(\\Enc,\\Dec)$. Our construction requires that $\\Dec$ is \\emph{symmetric}, i.e., for all $x, y$, it is the case that $\\Dec(x,y) = \\Dec(y,x)$, but this property holds for all currently known information-theoretically secure codes in the $2$-split state model. In particular, we can apply our transformation to the code of Aggarwal et al., obtaining the first leakage-resilient code secure in the split-state model. Our transformation can be applied to other codes (in particular it can also be applied to a recent code of Aggarwal, Dodis, Kazana and Obremski constructed in the work subsequent to this one).

00:17 [Pub][ePrint]

The article proposes an Online/Off-line Ring Signature Scheme in random oracle model.Security of the scheme relies on both Computational Diffie-Hellman and k-CAA problems. The proposed scheme is proven the two most important security goals Existential

Unforgeability and Signer Ambiguity. Also it has robustness property where the misbehavior of the signer can be detected. Signing process is performed in two phases online and offline. All heavy computations are performed in Off-line stage. So the overall computational cost is reduced and very less than the traditional signature scheme. The scheme can be applied to Mobile Ad Hoc Networks (MANETs) that undergo node mobility.

00:17 [Pub][ePrint]

We consider secure two-party computation in the client-server model where there are two adversaries that operate separately but simultaneously, each of them corrupting one of the parties and a restricted subset of servers that they interact with. We model security via the local universal composability framework introduced by Canetti and Vald and we show that information-theoretically secure two-party computation is possible if and only if there is always at least one server which remains uncorrupted.

00:17 [Pub][ePrint]

In recent years, there has been great interest in Functional Encryption (FE), a generalization of traditional encryption where a token enables a user to learn a specific function of the encrypted data and nothing else.

One of the main lines of research in the area has consisted in studying the security notions for FE and their achievability. This study was initiated by [Boneh et al. -- TCC\'11, O\'Neill -- ePrint\'10] where it was first shown that for FE the indistinguishability-based (IND) security notion is not sufficient in the sense that there are FE schemes that are provably IND-Secure but concretely insecure. For this reason, researchers investigated the achievability of Simulation-based (SIM) security, a stronger notion of security. Unfortunately, the above-mentioned works and others [e.g., Agrawal et al. -- CRYPTO\'13] have shown strong impossibility results for SIM-Security.

One way to overcome these impossibility results was first suggested in the work of Boneh et al. where it was shown how to construct, in the Random Oracle (RO) model, SIM-Secure FE for restricted functionalities and was asked the generalization to more complex functionalities as a challenging problem in the area.

Subsequently, [De Caro et al. -- CRYPTO\'13] proposed a candidate construction of SIM-Secure FE for all circuits in the RO model assuming the existence of an IND-Secure FE scheme for circuits {\\emph {with RO gates}}. This means that the functionality has to depend on the RO, thus it is not fixed in advance as in the standard definitions of FE. Moreover, to our knowledge there are no proposed candidate IND-Secure FE schemes for circuits with RO gates and they seem unlikely to exist.

In this paper, we propose the first constructions of SIM-Secure FE schemes in the RO model that overcome the current impossibility results in different settings. We can do that because we resort to the two following models:

In the public-key setting we assume a bound $q$ on the number of queries but this bound only affects the {\\emph {running-times}} of our encryption and decryption procedures. We stress that our FE schemes in this model are SIM-Secure and have ciphertexts and tokens of {\\emph {constant-size}}, whereas in the standard model, the current SIM-Secure FE schemes for general functionalities [De Caro et al., Gorbunov et al. -- CRYPTO\'12] have ciphertexts and tokens of size growing as the number of queries.

In the symmetric-key setting we assume a timestamp on both ciphertexts and tokens. This is reasonable because in the symmetric-key setting, there is only one user that encrypts and generates tokens. In this model, we provide FE schemes with short ciphertexts and tokens that are SIM-Secure against adversaries asking an {\\em {unbounded}} number of queries.

Both results also assume the RO model, but not functionalities with RO gates and rely on the existence of extractability obfuscation w.r.t. distributional auxiliary input [Boyle et al. -- TCC\'14] (and other standard primitives) secure only in the \\emph{standard model}.

00:17 [Pub][ePrint]

We investigate the security of the family of MQQ public key cryptosystems using multivariate quadratic quasigroups (MQQ). These cryptosystems show especially good performance properties. In particular, the MQQ-SIG signature scheme is the fastest scheme in the ECRYPT benchmarking of cryptographic systems (eBACS).

We show that both the signature scheme MQQ-SIG and the encryption scheme MQQ-ENC, although using different types of MQQs, share a common algebraic structure that introduces a weakness in both schemes. We use this weakness to mount a successful polynomial time key-recovery attack. Our key-recovery attack finds an equivalent key using the idea of so-called good keys that reveals the structure gradually. In the process we need to solve a MinRank problem that, because of the structure, can be solved in polynomial-time assuming some mild algebraic assumptions. We highlight that our theoretical results work in characteristic 2 which

is known to be the most difficult case to address in theory for MinRank attacks. Also, we emphasize that our attack works without any restriction on the number of polynomials removed from the public-key, that is, using the minus modifier. This was not the case for previous MinRank like-attacks against MQ schemes.

From a practical point of view, we are able to break an MQQ-SIG instance of $80$ bits security in less than 2 days,

and one of the more conservative MQQ-ENC instances of 128 bits security in little bit over 9 days. Altogether, our attack shows that it is very hard to design a secure public key scheme based on an easily invertible MQQ structure.

00:17 [Pub][ePrint]

Private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the user\'s sensitive data will be protected from exposure. Given an encrypted database, the users typically submit queries similar to the following examples:

- How many employees in an organization make over 100,000?

- What is the average age of factory workers suffering from leukemia?

Answering the above questions requires one to \\textbf{search} and then \\textbf{compute} over the encrypted databases \\emph{in sequence}. In the case of privately processing queries with only one of these operations, many efficient solutions have been developed using a special-purpose encryption scheme (e.g., searchable encryption). In this paper, we are interested in efficiently processing queries that need to perform both operations on \\emph{fully} encrypted databases. One immediate solution is to use several special-purpose encryption schemes at the same time, but this approach is associated with a high computational cost for maintaining multiple encryption contexts. The other solution is to use a privacy homomorphism (or fully homomorphic encryption) scheme. However, no secure solutions have been developed that meet the efficiency requirements.

In this work, we construct a unified framework so as to efficiently and privately process queries with search\'\' and compute\'\' operations. To this end, the first part of our work involves devising some underlying circuits as primitives for queries on encrypted data. Second, we apply two optimization techniques to improve the efficiency of the circuit primitives. One technique is to exploit SIMD techniques to accelerate their basic operations. In contrast to general SIMD approaches, our SIMD implementation can be applied even when one basic operation is executed. The other technique is to take a large integer ring (\\textit{e.g.}, $\\Z_{2^{t}}$) as a message space instead of a binary field. Even for an integer of $k$ bits with $k>t$, addition can be performed with degree 1 circuits with lazy carry operations.

As a result, search queries including a conjunctive or disjunctive query on encrypted databases of $N$ tuples with $\\mu$-bit attributes require $\\bigo(N \\log \\mu)$ homomorphic operations with depth $\\bigo(\\log \\mu)$ circuits. Search-and-compute queries, such as a conjunctive query with aggregate functions in the same conditions, are processed using $\\bigo(\\mu N)$ homomorphic operations with at most depth $\\bigo(\\log \\mu \\log N)$ circuits. Further, we can process search-and-compute queries using only $\\bigo(N \\log \\mu)$ homomorphic operations with depth $\\bigo(\\log \\mu)$ circuits, even in the large domain. Finally, we present various experiments by varying the parameters, such as the query type and the number of tuples.

00:17 [Pub][ePrint]

We show a technique to transform a linearly-homomorphic encryption into a homomorphic encryption scheme capable of evaluating degree-2 computations on ciphertexts. Our transformation is surprisingly simple and requires only one very mild property on the underlying linearly-homomorphic scheme: the message space must be a public ring in which it is possible to sample elements uniformly at random. This essentially allows us to instantiate our transformation with virtually all existing number-theoretic linearly-homomorphic schemes, such as Goldwasser-Micali, Paillier, or ElGamal. Our resulting schemes achieve circuit privacy and are compact when considering a subclass of degree-2 polynomials in which the number of additions of degree-2 terms is bounded by a constant.

As an additional contribution we extend our technique to build a protocol for outsourcing computation on encrypted data using two (non-communicating) servers. Somewhat interestingly, in this case we can boost a linearly-homomorphic scheme to support the evaluation of any degree-2 polynomial while achieving full compactness.