IACR News Central

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.

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.

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.

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

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.