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 get this service via

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2012-04-23
00:17 [Pub][ePrint]

In Europe and North America, the most widely used stream cipher to ensure privacy and confidentiality of conversations in GSM mobile phones is the A5/1. In this paper, we present a new attack on the A5/1 stream cipher with a minimum time complexity of around 2^(40) and an average complexity of 2^(48.5), which is much lesser than the brute-force attack with a complexity of 2^(64). The attack has a 100% success rate and requires about 5.65GB storage. We provide a detailed description of our new attack along with its implementation and results.

00:17 [Pub][ePrint]

In the last few years, the need to design new cryptographic hash

functions has led to the intense study of when desired hash

multi-properties are preserved or assured under compositions and

domain extensions. In this area, it is important to identify the

exact notions and provide often complex proofs of the resulting

properties. Getting this analysis right (as part of provable security

studies) is, in fact, analogous to cryptanalysis. We note that it is

important and quite subtle to get indeed the right\'\' notions and

properties, and right\'\' proofs in this relatively young

area. Specifically, the security notion we deal with is adaptive

preimage resistance\'\' (apr) which was introduced by Lee and Park as an extension of preimage resistance\'\' (pr). In

Eurocrypt 2010, in turn, Lee and Steinberger already

used the apr security notion to prove preimage awareness\'\' and

indifferentiable security\'\' of their new double-piped mode of

operation. They claimed that if $H^P$ is collision-resistant (cr) and apr,

then $F(M)=\\mathcal{R}(H^P(M))$ is indifferentiable from a variable

output length (VIL) random oracle $\\mathcal{F}$, where $H^P$ is a

function based on an ideal primitive $P$ and $\\mathcal{R}$ is a fixed

input length (FIL) random oracle. However, there are some limitations in their claim, because they considered only indifferentiability security notion in the information-theoretic adversarial model, not in the computation-theoretic adversarial model. As we show in the current

work, the above statement is \\textit{not} correct in the computation-theoretic adversarial model. First in our

studies, we give a counterexample to the above. Secondly, we describe

\\textit{a new requirement} on $H^P$ (called admissibility\'\') so that

the above statement is correct even in the computation-theoretic adversarial model. Thirdly, we show that apr is, in fact,

not a strengthened notion of preimage resistance. Fourthly, we

explain the relation between preimage awareness and cr+apr+(our new

requirement) in the computation-theoretic adversarial model. Finally, we show that a polynomial-based mode of

operation \\cite{LeSt10} satisfies our new requirement; namely, the

polynomial-based mode of operation with fixed-input-length random

oracles is indifferentiable from a variable-input-length random oracle in the computation-theoretic adversarial model.

00:17 [Pub][ePrint]

It has been pointed out that an $n$-variable Boolean function $f$ has optimal resistance against fast algebraic attacks if and only if there does not exist a nonzero $n$-variable Boolean function $g$ of degree lower than $\\frac{n}{2}$ such that $fg=h$ and $\\mathrm{deg}(g)+\\mathrm{deg}(h) 00:17 [Pub][ePrint] An unresolved problem in research on authenticated key exchange (AKE) is to construct a secure protocol against advanced attacks such as key compromise impersonation and maximal exposure attacks without relying on random oracles. HMQV, a state of the art AKE protocol, achieves both efficiency and the strong security model proposed by Krawczyk (we call it the CK+ model), which includes resistance to advanced attacks. However, the security proof is given under the random oracle model. We propose a generic construction of AKE from a key encapsulation mechanism (KEM). The construction is based on a chosen-ciphertext secure KEM, and the resultant AKE protocol is$\\CKHMQV$secure in the standard model. The protocol gives the first CK+ secure AKE protocols based on the hardness of integer factorization problem, code-based problems, or learning problems with errors. In addition, instantiations under the Diffie-Hellman assumption or its variant can be proved to have strong security without non-standard assumptions such as$\\pi$PRF and KEA1. 00:17 [Pub][ePrint] A perfect algebraic immune function is a Boolean function with perfect immunity against algebraic and fast algebraic attacks. The main results are that for a perfect algebraic immune balanced function the number of input variables is one more than a power of two; for a perfect algebraic immune unbalanced function the number of input variables is a power of two. Also the Carlet-Feng function on$2^s+1$variables and the modified Carlet-Feng function on$2^s$variables are shown to be perfect algebraic immune functions. Furthermore, it is shown that a perfect algebraic immune function behaves good against probabilistic algebraic attacks as well. 00:17 [Pub][ePrint] Verifiable random functions (VRF) and selectively-convertible undeniable signature (SCUS) schemes were proposed independently in the literature. In this paper, we observe that they are tightly related. This directly yields several deterministic SCUS schemes based on existing VRF constructions. In addition, we create a new probabilistic SCUS scheme, which is very compact. The confirmation and disavowal protocols of these SCUS are efficient, and can be run either sequentially, concurrently, or arbitrarily. These protocols are based on what we call zero-knowledge protocols for generalized DDH and non-DDH, which are of independent interest. 00:17 [Pub][ePrint] Finding the longest impossible differentials is an essential assignment in proceeding impossible differential cryptanalysis. In this paper, we introduce a novel tool to search the longest truncated impossible differentials for word-oriented block ciphers with bijective S-boxes. It costs polynomial time to return a flag indicating whether a truncated differential is impossible under several filter conditions. To demonstrate the strength of our tool, we show that it allows to automatically find the longest truncated impossible differentials for many word-oriented block ciphers. It independently rediscovers all known truncated impossible differentials on nine round CLEFIA. What\'s more, it finds new and longest truncated impossible differentials for the AES, ARIA, Camellia without$FL$and$FL^{-1}$layers, E2, MIBS, LBlock and Piccolo. Finally, we give an impossible differential of 14-round LBlock to illustrate that our tool is more powerful than the$\\mathcal{U}$-method and UID-method. We expect that the tool proposed in this paper will be useful for evaluating the security of block ciphers against impossible differentials, especially when one tries to design a word-oriented block cipher with bijective S-boxes. 00:17 [Pub][ePrint] We introduce a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), which is a natural extension of span programs defined by Karchmer and Wigderson. Our main motivation is the construction of succinct arguments of NP-statements that are quick to construct and verify. QSPs seem well-suited for this task, perhaps even better than Probabilistically Checkable Proofs (PCPs). In 2010, Groth constructed a NIZK argument in the common reference string (CRS) model for Circuit-SAT consisting of only 42 elements in a bilinear group. Interestingly, his argument does not (explicitly) use PCPs. But his scheme has some disadvantages -- namely, the CRS size and prover computation are both quadratic in the circuit size. In 2011, Lipmaa reduced the CRS size to quasi-linear, but with prover computation still quadratic. Using QSPs we construct a NIZK argument in the CRS model for Circuit-SAT consisting of just 7 group elements. The CRS size is linear in the circuit size, and prover computation is quasi-linear, making our scheme seemingly quite practical. (The prover only needs to do a linear number of group operations; the quasi-linear computation is a multipoint evaluation and interpolation.) Our results are complementary to those of Valiant (TCC 2008) and Bitansky et al. (2012), who use \"bootstrapping\" (recursive composition) of arguments to reduce CRS size and prover and verifier computation. QSPs also provide a crisp mathematical abstraction of some of the techniques underlying Groth\'s and Lipmaa\'s constructions. 00:17 [Pub][ePrint] We consider designing broadcast encryption schemes with constant-size secret keys and ciphertexts, achieving chosen-ciphertext security. We first argue that known CPA-to-CCA transforms currently do not yield such schemes. We then propose a scheme, modifying a previous selective CPA secure proposal by Boneh, Gentry, and Waters. Our proposed scheme has constant-size secret keys and ciphertexts and we prove that it is selective chosen-ciphertext secure based on standard assumptions. Our scheme has ciphertexts that are shorter than those of the previous CCA secure proposals. Then we propose a second scheme that provides the functionality of both broadcast encryption and revocation schemes simultaneously using the same set of parameters. Finally we show that it is possible to prove our first scheme adaptive chosen-ciphertext secure under reasonable extensions of the bilinear Diffie-Hellman exponent and the knowledge of exponent assumptions. We prove both of these extended assumptions in the generic group model. Hence, our scheme becomes the first to achieve constant-size secret keys and ciphertexts (both asymptotically optimal) and adaptive chosen-ciphertext security at the same time. 00:17 [Pub][ePrint] In this paper we show that a large class of diverse problems have a bicomposite structure which makes it possible to solve them with a new type of algorithm called {\\it dissection}, which has much better time/memory tradeoffs than previously known algorithms. A typical example is the problem of finding the key of multiple encryption schemes with$r$independent$n$-bit keys. All the previous error-free attacks required time$T$and memory$M$satisfying$TM = 2^{rn}$, and even if false negatives\'\' are allowed, no attack could achieve$TM

00:17 [Pub][ePrint]

We consider applications scenarios where an untrusted aggregator wishes to continually monitor the heavy-hitters across a set of distributed streams. Since each stream can contain sensitive data, such as the purchase history of customers, we wish to guarantee the privacy of each stream, while allowing the untrusted aggregator to accurately detect the heavy hitters and their approximate frequencies.

Our protocols are scalable in settings where the volume of streaming data is large, since we guarantee low memory usage and processing overhead by each data source, and low communication overhead between the data sources and the aggregator.