*19:17* [Pub][ePrint]
Space-efficient, byte-wise incremental and perfectly private encryption schemes, by Kévin Atighehchi
The problem raised by incremental encryption is the overhead due to the larger storage space required by the provision of random blocks together with the ciphered versions of a given document. Besides,permitting variable-length modifications on the ciphertext leads to privacy preservation issues. In this paper we present incremental encryption schemes which are space-efficient, byte-wise incremental and which preserve perfect privacy in the sense that they hide the fact that an update operation has been performed on a ciphered document. For each scheme, the run time of updates performed turns out to be very efficient and we discuss the statistically adjustable trade-off between computational cost and storage space required by the produced ciphertexts.

*16:17* [Pub][ePrint]
Unified, Minimal and Selectively Randomizable Structure-Preserving Signatures, by Masayuki Abe and Jens Groth and Miyako Ohkubo and Mehdi Tibouchi
We construct a structure-preserving signature scheme that is selectively randomizable and works in all types of bilinear groups. We give matching lower bounds showing that our structure-preserving signature scheme is optimal with respect to both signature size and public verification key size.

State of the art structure-preserving signatures in the asymmetric setting consist of 3 group elements, which is known to be optimal. Our construction preserves the signature size of 3 group elements and also at the same time minimizes the verification key size to 1 group element.

Depending on the application, it is sometimes desirable to have strong unforgeability and in other situations desirable to have randomizable signatures. To get the best of both worlds, we introduce the notion of selective randomizability where the signer may for specific signatures provide randomization tokens that enable randomization.

Our structure-preserving signature scheme unifies the different pairing-based settings since it can be instantiated in both symmetric and asymmetric groups. Since previously optimal structure-preserving signatures had only been constructed in asymmetric bilinear groups this closes an important gap in our knowledge. Having a unified signature scheme that works in all types of bilinear groups is not just conceptually nice but also gives a hedge against future cryptanalytic attacks. An instantiation of our signature scheme in an asymmetric bilinear group may remain secure even if cryptanalysts later discover an efficiently computable homomorphism between the source groups.

*16:17* [Pub][ePrint]
Tight security bounds for multiple encryption, by Yuanxi Dai, John Steinberger
Multiple encryption---the practice of composing a blockcipher severaltimes with itself under independent keys---has received considerable

attention of late from the standpoint of provable security. Despite

these efforts proving definitive security bounds (i.e., with matching

attacks) has remained elusive even for the special case of triple

encryption. In this paper we close the gap by improving both the best

known attacks and best known provable security, so that both bounds

match. Our results apply for arbitrary number of rounds and show that

the security of $\\ell$-round multiple encryption is precisely

$\\exp(\\kappa + \\min\\{\\kappa (\\ell\'-2)/2), n (\\ell\'-2)/\\ell\'\\})$ where

$\\exp(t) = 2^t$ and where $\\ell\' = 2\\lceil \\ell/2\\rceil$ is the even

integer closest to $\\ell$ and greater than or equal to $\\ell$, for all

$\\ell \\geq 1$. Our technique is based on Patarin\'s H-coefficient

method and reuses a combinatorial result of Chen and Steinberger

originally required in the context of key-alternating ciphers.

*16:17* [Pub][ePrint]
Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources, by Christina Brzuska and Pooya Farshim and Arno Mittelbach
Random oracles are powerful cryptographic objects. They facilitate the security proofs of an impressive number of practical cryptosystems ranging from KDM-secure and deterministic encryption to point-function obfuscation and many more. However, due to an uninstantiability result of Canetti, Goldreich, and Halevi (STOC 1998) random oracles have become somewhat controversial. Recently, Bellare, Hoang, and Keelveedhi (BHK; CRYPTO 2013 and ePrint 2013/424, August 2013) introduced a new abstraction called Universal Computational Extractors (UCEs), and showed that they suffice to securely replace random oracles in a number of prominent applications, including all those mentioned above, without suffering from the aforementioned uninstantiability result. This, however, leaves open the question of constructing UCEs in the standard model.We show that the existence of indistinguishability obfuscation (iO) implies (non-black-box) attacks on all the definitions that BHK proposed within their UCE framework in the original version of their paper, in the sense that no concrete hash function can satisfy them. We also show that this limitation can be overcome, to some extent, by restraining the class of admissible adversaries via a statistical notion of unpredictability. Following our attack, BHK (ePrint 2013/424, September 2013), independently adopted this approach in their work.

In the updated version of their paper, BHK (ePrint 2013/424, September 2013) also introduce two other novel source classes, called bounded parallel sources and split sources, which aim at recovering the computational applications of UCEs that fall outside the statistical fix. These notions keep to a computational notion of unpredictability, but impose structural restrictions on the adversary so that our original iO attack no longer applies. We extend our attack to show that indistinguishability obfuscation is sufficient to also break the UCE security of any hash function against bounded parallel sources. Towards this goal, we use the randomized encodings paradigm of Applebaum, Ishai, and Kushilevitz (STOC 2004) to parallelize the obfuscated circuit used in our attack, so that it can be computed by a bounded parallel source whose second stage consists of constant-depth circuits. We conclude by discussing the composability and feasibility of hash functions secure against split sources.