Search

In frameworks for universal composability, complex protocols can be built from sub-protocols in a modular way using composition theorems. However, as first pointed out and studied by Canetti and Rabin, this modular approach often leads to impractical implementations. For example, when using a functionality for digital signatures within a more complex protocol, parties have to generate new verification and signing keys for every session of the protocol. This motivates to generalize composition theorems to so-called joint state (composition) theorems, where different copies of a functionality may share some state, e.g., the same verification and signing keys. In this paper, we present a joint state theorem which is more general than the original theorem of Canetti and Rabin, for which several problems and limitations are pointed out. We apply our theorem to obtain joint state realizations for three functionalities: public-key encryption, replayable public-key encryption, and digital signatures. Unlike most other formulations, our functionalities model that ciphertexts and signatures are computed locally, rather than being provided by the adversary. To obtain the joint state realizations, the functionalities have to be designed carefully. Other formulations proposed in the literature are shown to be unsuitable. Our work is based on the IITM model. Our definitions and results demonstrate the expressivity and simplicity of this model. For example, unlike Canetti's UC model, in the IITM model no explicit joint state operator needs to be defined and the joint state theorem follows immediately from the composition theorem in the IITM model. [ABSTRACT FROM AUTHOR]

In structure-preserving cryptography over bilinear groups, cryptographic schemes are restricted to exchange group elements only, and their correctness must be verifiable only by evaluating pairing product equations. Several primitives, such as structure-preserving signatures, commitments, and encryption schemes, have been proposed. Although deterministic primitives, such as verifiable pseudorandom functions or verifiable unpredictable functions, play an important role in the construction of cryptographic protocols, no structure-preserving realizations of them are known. This is not coincident: In this paper, we show that it is impossible to construct algebraic structure-preserving deterministic primitives that provide provability, uniqueness, and unpredictability. This includes verifiable random functions, unique signatures, and verifiable unpredictable functions as special cases. The restriction of structure-preserving primitives to be algebraic is natural, otherwise it would not be known how to verify correctness only by evaluating pairing product equations. We further extend our negative result to pseudorandom functions and deterministic public key encryption as well as non-strictly structure-preserving primitives, where target group elements are also allowed in their ranges and public keys. [ABSTRACT FROM AUTHOR]

Bellare, Boldyreva, and O’Neill (CRYPTO ’07) initiated the study of deterministic public-key encryption as an alternative in scenarios where randomized encryption has inherent drawbacks. The resulting line of research has so far guaranteed security only for adversarially chosen-plaintext distributions that are independent of the public key used by the scheme. In most scenarios, however, it is typically not realistic to assume that adversaries do not take the public key into account when attacking a scheme. We show that it is possible to guarantee meaningful security even for plaintext distributions that depend on the public key. We extend the previously proposed notions of security, allowing adversaries to adaptively choose plaintext distributions after seeing the public key, in an interactive manner. The only restrictions we make are that: (1) plaintext distributions are unpredictable (as is essential in deterministic public-key encryption), and (2) the number of plaintext distributions from which each adversary is allowed to adaptively choose is upper bounded by 2p, where p can be any predetermined polynomial in the security parameter and plaintext length. For example, with p=0 we capture plaintext distributions that are independent of the public key, and with p=O(slogs) we capture, in particular, all plaintext distributions that are samplable by circuits of size s. Within our framework we present both constructions in the random oracle model based on any public-key encryption scheme, and constructions in the standard model based on lossy trapdoor functions (thus, based on a variety of number-theoretic assumptions). Previously known constructions heavily relied on the independence between the plaintext distributions and the public key for the purposes of randomness extraction. In our setting, however, randomness extraction becomes significantly more challenging once the plaintext distributions and the public key are no longer independent. Our approach is inspired by research on randomness extraction from seed-dependent distributions. Underlying our approach is a new generalization of a method for such randomness extraction, originally introduced by Trevisan and Vadhan (FOCS ’00) and Dodis (Ph.D. Thesis, MIT, ’00). [ABSTRACT FROM AUTHOR]

In typical applications of homomorphic encryption, the first step consists for Alice of encrypting some plaintext m under Bob’s public key pk and of sending the ciphertext c=HEpk(m) to some third-party evaluator Charlie. This paper specifically considers that first step, i.e., the problem of transmitting c as efficiently as possible from Alice to Charlie. As others suggested before, a form of compression is achieved using hybrid encryption. Given a symmetric encryption scheme E, Alice picks a random key k and sends a much smaller ciphertext c′=(HEpk(k),Ek(m)) that Charlie decompresses homomorphically into the original c using a decryption circuit CE-1. In this paper, we revisit that paradigm in light of its concrete implementation constraints, in particular E is chosen to be an additive IV-based stream cipher. We investigate the performances offered in this context by Trivium, which belongs to the eSTREAM portfolio, and we also propose a variant with 128-bit security: Kreyvium. We show that Trivium, whose security has been firmly established for over a decade, and the new variant Kreyvium has excellent performance. We also describe a second construction, based on exponentiation in binary fields, which is impractical but sets the lowest depth record to 8 for 128-bit security. [ABSTRACT FROM AUTHOR]

The ASASA construction is a new design scheme introduced at ASIACRYPT 2014 by Biryukov, Bouillaguet and Khovratovich. Its versatility was illustrated by building two public-key encryption schemes, a secret-key scheme, as well as super S-box subcomponents of a white-box scheme. However, one of the two public-key cryptosystems was recently broken at CRYPTO 2015 by Gilbert, Plût and Treger. As our main contribution, we propose a new algebraic key-recovery attack able to break at once the secret-key scheme as well as the remaining public-key scheme, in time complexity 263 and 239, respectively (the security parameter is 128 bits in both cases). Furthermore, we present a second attack of independent interest on the same public-key scheme, which heuristically reduces the problem of breaking the scheme to an LPN instance with tractable parameters. This allows key recovery in time complexity 256. Finally, as a side result, we outline a very efficient heuristic attack on the white-box scheme, which breaks instances claiming 64 bits of security under one minute on a laptop computer. [ABSTRACT FROM AUTHOR]

We construct a general-purpose multi-input functional encryption scheme in the private-key setting. Namely, we construct a scheme where a functional key corresponding to a function f enables a user holding encryptions of x1,…,xt to compute f(x1,…,xt) but nothing else. This is achieved starting from any general-purpose private-key single-input scheme (without any additional assumptions) and is proven to be adaptively secure for any constant number of inputs t. Moreover, it can be extended to a super-constant number of inputs assuming that the underlying single-input scheme is sub-exponentially secure. Instantiating our construction with existing single-input schemes, we obtain multi-input schemes that are based on a variety of assumptions (such as indistinguishability obfuscation, multilinear maps, learning with errors, and even one-way functions), offering various trade-offs between security assumptions and functionality. Previous and concurrent constructions of multi-input functional encryption schemes either rely on stronger assumptions and provided weaker security guarantees (Goldwasser et al. in Advances in cryptology—EUROCRYPT, 2014; Ananth and Jain in Advances in cryptology—CRYPTO, 2015), or relied on multilinear maps and could be proven secure only in an idealized generic model (Boneh et al. in Advances in cryptology—EUROCRYPT, 2015). In comparison, we present a general transformation that simultaneously relies on weaker assumptions and guarantees stronger security. [ABSTRACT FROM AUTHOR]

We analyze the security of the Thorp shuffle, or, equivalently, a maximally unbalanced Feistel network. Roughly said, the Thorp shuffle on N cards mixes any N1-1/r of them in O(rlgN) steps. Correspondingly, making O(r) passes of maximally unbalanced Feistel over an n-bit string ensures CCA security to 2n(1-1/r) queries. Our results, which employ Markov chain techniques, particularly couplings, help to justify a practical, although still relatively inefficient, blockcipher-based scheme for deterministically enciphering credit card numbers and the like. [ABSTRACT FROM AUTHOR]

We provide a provable-security treatment of “robust” encryption. Robustness means it is hard to produce a ciphertext that is valid for two different users. Robustness makes explicit a property that has been implicitly assumed in the past. We argue that it is an essential conjunct of anonymous encryption. We show that natural anonymity-preserving ways to achieve it, such as adding recipient identification information before encrypting, fail. We provide transforms that do achieve it, efficiently and provably. We assess the robustness of specific encryption schemes in the literature, providing simple patches for some that lack the property. We explain that robustness of the underlying anonymous IBE scheme is essential for public-key encryption with keyword search (PEKS) to be consistent (meaning, not have false positives), and our work provides the first generic conversions of anonymous IBE schemes to consistent (and secure) PEKS schemes. Overall, our work enables safer and simpler use of encryption. [ABSTRACT FROM AUTHOR]

Functional encryption supports restricted decryption keys that allow users to learn specific functions of the encrypted messages. Although the vast majority of research on functional encryption has so far focused on the privacy of the encrypted messages, in many realistic scenarios it is crucial to offer privacy also for the functions for which decryption keys are provided. Whereas function privacy is inherently limited in the public-key setting, in the private-key setting it has a tremendous potential. Specifically, one can hope to construct schemes where encryptions of messages $$\mathsf{m}_1, \ldots , \mathsf{m}_T$$ together with decryption keys corresponding to functions $$f_1, \ldots , f_T$$ , reveal essentially no information other than the values $$\{ f_i(\mathsf{m}_j)\}_{i,j\in [T]}$$ . Despite its great potential, the known function-private private-key schemes either support rather limited families of functions (such as inner products) or offer somewhat weak notions of function privacy. We present a generic transformation that yields a function-private functional encryption scheme, starting with any non-function-private scheme for a sufficiently rich function class. Our transformation preserves the message privacy of the underlying scheme and can be instantiated using a variety of existing schemes. Plugging in known constructions of functional encryption schemes, we obtain function-private schemes based either on the learning with errors assumption, on obfuscation assumptions, on simple multilinear-maps assumptions, and even on the existence of any one-way function (offering various trade-offs between security and efficiency). [ABSTRACT FROM AUTHOR]

Homomorphic message authenticators allow the holder of a (public) evaluation key to perform computations over previously authenticated data, in such a way that the produced tag $$\sigma $$ can be used to certify the authenticity of the computation. More precisely, a user, knowing the secret key $$\mathsf{sk}$$ used to authenticate the original data, can verify that $$\sigma $$ authenticates the correct output of the computation. This primitive has been recently formalized by Gennaro and Wichs, who also showed how to realize it from fully homomorphic encryption. In this paper, we show new constructions of this primitive that, while supporting a smaller set of functionalities (i.e., polynomially bounded arithmetic circuits as opposite to boolean ones), are much more efficient and easy to implement. Moreover, our schemes can tolerate any number of (malicious) verification queries. Our first construction relies on the sole assumption that one-way functions exist, allows for arbitrary composition (i.e., outputs of previously authenticated computations can be used as inputs for new ones) but has the drawback that the size of the produced tags grows with the degree of the circuit. Our second solution, relying on the D-Diffie-Hellman Inversion assumption, offers somewhat orthogonal features as it allows for very short tags (one single group element!) but poses some restrictions on the composition side. [ABSTRACT FROM AUTHOR]

We present a construction of a private-key functional encryption scheme for any family of randomized functionalities based on any such scheme for deterministic functionalities that is sufficiently expressive. Instantiating our construction with existing schemes for deterministic functionalities, we obtain schemes for any family of randomized functionalities based on a variety of assumptions (including the LWE assumption, simple assumptions on multilinear maps, and even the existence of any one-way function) offering various trade-offs between security and efficiency. Previously, Goyal et al. (Proceedings of the 12th theory of cryptography conference (TCC), pp 325-351, 2015) constructed a public-key functional encryption scheme for any family of randomized functionalities based on indistinguishability obfuscation. One of the key insights underlying our work is that, in the private-key setting, a sufficiently expressive functional encryption scheme may be appropriately utilized for implementing proof techniques that were so far implemented based on obfuscation assumptions [such as the punctured programming technique of Sahai and Waters (Proceedings of the 46th annual ACM symposium on theory of computing (STOC), pp. 475-484, 2014)]. We view this as a contribution of independent interest that may be found useful in other settings as well. [ABSTRACT FROM AUTHOR]

We show how to transform any semantically secure encryption scheme into a non-malleable one, with a black-box construction that achieves a quasi-linear blow-up in the size of the ciphertext. This improves upon the previous non-black-box construction of Pass, Shelat and Vaikuntanathan (Crypto '06). Our construction also extends readily to guarantee non-malleability under a bounded-CCA2 attack, thereby simultaneously improving on both results in the work of Cramer et al. (Asiacrypt '07). Our construction departs from the oft-used paradigm of re-encrypting the same message with different keys and then proving consistency of encryption. Instead, we encrypt an encoding of the message; the encoding is based on an error-correcting code with certain properties of reconstruction and secrecy from partial views, satisfied, e.g., by a Reed-Solomon code. [ABSTRACT FROM AUTHOR]

We present a new cryptographic primitive, called all-but-many encryption (ABME). An ABME scheme is a tag-based public-key encryption scheme with the following additional properties: A sender given the secret key can generate a fake ciphertext to open to any message with consistent randomness. In addition, anyone who does not own the secret key can neither distinguish a fake ciphertext from a real (honestly generated) one, nor produce a fake one (on a fresh tag) even after seeing many fake ciphertexts and their opening. A motivating application of ABME is universally composable (UC) commitment schemes. We prove that an ABME scheme implies a non-interactive UC commitment scheme that is secure against adaptive adversaries in the non-erasure model under a reusable common reference string. Previously, such a 'fully equipped' UC commitment scheme has been known only in Canetti and Fischlin (CRYPTO 2001, vol 2139, Lecture notes in computer science. Springer, Heidelberg, pp 19-40, 2001), Canetti et al. (STOC 2002, pp 494-503, 2002), with expansion factor $$O(\kappa )$$ , meaning that to commit $$\lambda $$ bits, communication strictly requires $$O(\lambda \kappa )$$ bits, where $$\kappa $$ denotes the security parameter. We provide a general framework for constructing ABME and several concrete instantiations from a variety of assumptions. In particular, we present an ABME scheme with expansion factor O(1) from DCR-related assumptions, which results in showing the first fully equipped UC commitment scheme with a constant expansion factor. In addition, the DCR-based ABME scheme can be transformed to an all-but-many lossy trapdoor function (ABM-LTF), proposed by Hofheinz (EUROCRYPT 2012, vol 7237, Lecture notes in computer science. Springer, Heidelberg, pp 209-227, 2012), with a better lossy rate than Hofheinz (2012). [ABSTRACT FROM AUTHOR]

We give generic constructions of several fundamental cryptographic primitives based on a new encryption primitive that combines circular security for bit encryption with the so-called reproducibility property (Bellare et al. in Public key cryptography-PKC 2003, vol. 2567, pp. 85-99, Springer, 2003). At the heart of our constructions is a novel technique which gives a way of de-randomizing reproducible public-key bit encryption schemes and also a way of reducing one-wayness conditions of a constructed trapdoor function family (TDF) to circular security of the base scheme. The main primitives that we build from our encryption primitive include k-wise one-way TDFs (Rosen and Segev in SIAM J Comput 39(7):3058-3088, 2010), chosen-ciphertext-attack-secure encryption and deterministic encryption. Our results demonstrate a new set of applications of circularly secure encryption beyond fully homomorphic encryption and symbolic soundness. Finally, we show the plausibility of our assumptions by showing that the decisional Diffie-Hellman-based circularly secure scheme of Boneh et al. (Advances in cryptology-CRYPTO 2008, vol. 5157, Springer, 2008) and the subgroup indistinguishability-based scheme of Brakerski and Goldwasser (Advances in cryptology-CRYPTO 2010, vol. 6223, pp. 1-20, Springer, 2010) are both reproducible. [ABSTRACT FROM AUTHOR]

Transport Layer Security (TLS) is the most important cryptographic protocol in use today. However, finding a cryptographic security proof for the complete, unaltered protocol has proven to be a challenging task. We give the first such proof in the standard model for the core cryptographic protocol underlying TLS cipher suites based on ephemeral Diffie-Hellman key exchange (TLS-DHE). This includes the cipher suite TLS_DHE_DSS_WITH_3DES_EDE_CBC_SHA, which is mandatory in TLS 1.0 and TLS 1.1. It is impossible to prove the TLS Handshake secure in the classical security models of Bellare-Rogaway and Canetti-Krawczyk. The reason for this is that the final Finished messages of the TLS Handshake are encrypted with the session key, which provides an opportunity to distinguish real keys from random values. Therefore we start with proving the security of a truncated version of the TLS Handshake protocol, which has also been considered in previous work on TLS, and give the first proof of this variant in the standard model. Then we define the new notion of authenticated and confidential channel establishment (ACCE), which allows the monolithic analysis of protocols for which a modular security proof is not possible. We show that the combination of the TLS-DHE Handshake protocol and the TLS Record Layer encryption is secure in this model. Since the conference publication of this paper, the notion of ACCE has found many further applications, for example to the analysis of further TLS cipher suites (Krawczyk et al., Crypto 2013; Li et al., PKC 2014), advanced mechanisms like secure renegotiation of TLS session keys (Giesen et al., CCS 2013), and other practical protocols like EMV channel establishment (Brzuska et al., CCS 2013), SSH (Bergsma et al., CCS 2014), and QUIC (Lychev et al., S&P 2015). [ABSTRACT FROM AUTHOR]

We study the problem of constructing locally computable universal one-way hash functions (UOWHFs) $$\mathcal {H}:\{0,1\}^n \rightarrow \{0,1\}^m$$ . A construction with constant output locality, where every bit of the output depends only on a constant number of bits of the input, was established by Applebaum et al. (SIAM J Comput 36(4):845-888, 2006). However, this construction suffers from two limitations: (1) it can only achieve a sublinear shrinkage of $$n-m=n^{1-\epsilon }$$ and (2) it has a super-constant input locality, i.e., some inputs influence a large super-constant number of outputs. This leaves open the question of realizing UOWHFs with constant output locality and linear shrinkage of $$n-m= \epsilon n$$ , or UOWHFs with constant input locality and minimal shrinkage of $$n-m=1$$ . We settle both questions simultaneously by providing the first construction of UOWHFs with linear shrinkage, constant input locality and constant output locality. Our construction is based on the one-wayness of 'random' local functions-a variant of an assumption made by Goldreich (Studies in Complexity and Cryptography, 76-87, 2011; ECCC 2010). Using a transformation of Ishai et al. (STOC, 2008), our UOWHFs give rise to a digital signature scheme with a minimal additive complexity overhead: signing n-bit messages with security parameter $$\kappa $$ takes only $$O(n+\kappa )$$ time instead of $$O(n\kappa )$$ as in typical constructions. Previously, such signatures were only known to exist under an exponential hardness assumption. As an additional contribution, we obtain new locally computable hardness amplification procedures for UOWHFs that preserve linear shrinkage. [ABSTRACT FROM AUTHOR]

We show that the widely deployed RSA-OAEP encryption scheme of Bellare and Rogaway (Eurocrypt 1994), which combines RSA with two rounds of an underlying Feistel network whose hash ( i.e., round) functions are modeled as random oracles, meets indistinguishability under chosen-plaintext attack (IND-CPA) in the standard model based on simple, non-interactive, and non-interdependent assumptions on RSA and the hash functions. To prove this, we first give a result on a more general notion called 'padding-based' encryption, saying that such a scheme is IND-CPA if (1) its underlying padding transform satisfies a 'fooling" condition against small-range distinguishers on a class of high-entropy input distributions, and (2) its trapdoor permutation is sufficiently lossy as defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satisfies condition (1) if its hash function is t-wise independent for t roughly proportional to the allowed message length. We clarify that this result requires the hash function to be keyed, and for its key to be included in the public key of RSA-OAEP. We also show that RSA satisfies condition (2) under the $$\Phi $$ -Hiding Assumption of Cachin et al. (Eurocrypt 1999). This is the first positive result about the instantiability of RSA-OAEP. In particular, it increases confidence that chosen-plaintext attacks are unlikely to be found against the scheme. In contrast, RSA-OAEP's predecessor in PKCS #1 v1.5 was shown to be vulnerable to such attacks by Coron et al. (Eurocrypt 2000). [ABSTRACT FROM AUTHOR]

Homomorphic encryption schemes are useful in designing conceptually simple protocols that operate on encrypted inputs. On the other hand, non-malleable encryption schemes are vital for designing protocols with robust security against malicious parties, in a composable setting. In this paper, we address the problem of constructing public-key encryption schemes that meaningfully combine these two opposing demands. The intuitive tradeoff we desire in an encryption scheme is that anyone should be able to change encryptions of unknown messages $$m_1, \ldots , m_k$$ into a (fresh) encryption of $$T(m_1, \ldots , m_k)$$ for a specific set of allowed functions T, but the scheme should be otherwise 'non-malleable.' That is, no adversary should be able to construct a ciphertext whose value is related to that of other ciphertexts in any other way. For the case where the allowed functions T are all unary, we formulate precise definitions that capture our intuitive requirements and show relationships among these new definitions and other more standard ones (IND-CCA, gCCA, and RCCA). We further justify these new definitions by showing their equivalence to a natural formulation of security in the framework of Universally Composable security. Next, we describe a new family of encryption schemes that satisfy our definitions for a wide variety of allowed transformations T and prove their security under the Decisional Diffie-Hellman (DDH) assumption in two groups with related sizes. Finally, we demonstrate how encryption schemes that satisfy our definitions can be used to implement conceptually simple protocols for non-trivial computation on encrypted data, which are secure against malicious adversaries in the UC framework without resorting to general-purpose multi-party computation or zero-knowledge proofs. For the case where the allowed functions T are binary, we show that a natural generalization of our definitions is unattainable if some T is a group operation. On the positive side, we show that if one of our security requirements is relaxed in a natural way, we can in fact obtain a scheme that is homomorphic with respect to (binary) group operations, and non-malleable otherwise. [ABSTRACT FROM AUTHOR]

A computational secret-sharing scheme is a method that enables a dealer, that has a secret, to distribute this secret among a set of parties such that a 'qualified' subset of parties can efficiently reconstruct the secret while any 'unqualified' subset of parties cannot efficiently learn anything about the secret. The collection of 'qualified' subsets is defined by a monotone Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing scheme. Yao suggested a method for secret-sharing for any function that has a polynomial-size monotone circuit (a class which is strictly smaller than the class of monotone functions in $${\mathsf {P}}$$ ). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in $${\mathsf {NP}}$$ : in order to reconstruct the secret a set of parties must be 'qualified' and provide a witness attesting to this fact. Recently, Garg et al. (Symposium on theory of computing conference, STOC, pp 467-476, 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement $$x\in L$$ for a language $$L\in {\mathsf {NP}}$$ such that anyone holding a witness to the statement can decrypt the message; however, if $$x\notin L$$ , then it is computationally hard to decrypt. Garg et al. showed how to construct several cryptographic primitives from witness encryption and gave a candidate construction. One can show that computational secret-sharing implies witness encryption for the same language. Our main result is the converse: we give a construction of a computational secret-sharing scheme for any monotone function in $${\mathsf {NP}}$$ assuming witness encryption for $${\mathsf {NP}}$$ and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone $${\mathsf {NP}}$$ -complete function implies a computational secret-sharing scheme for every monotone function in $${\mathsf {NP}}$$ . [ABSTRACT FROM AUTHOR]

Goldwasser and Micali (J Comput Syst Sci 28(2):270-299, 1984) highlighted the importance of randomizing the plaintext for public-key encryption and introduced the notion of semantic security. They also realized a cryptosystem meeting this security notion under the standard complexity assumption of deciding quadratic residuosity modulo a composite number. The Goldwasser-Micali cryptosystem is simple and elegant but is quite wasteful in bandwidth when encrypting large messages. A number of works followed to address this issue and proposed various modifications. This paper revisits the original Goldwasser-Micali cryptosystem using $$2^k$$ -th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for $$k \ge 2$$ (the case $$k=1$$ corresponds exactly to the Goldwasser-Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular, they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function-based thereon. [ABSTRACT FROM AUTHOR]

We put forward a new algebraic framework to generalize and analyze Diffie-Hellman like decisional assumptions which allows us to argue about security and applications by considering only algebraic properties. Our $$\mathcal {D}_{\ell ,k}\text{- }\textsf {MDDH}$$ Assumption states that it is hard to decide whether a vector in $$\mathbb {G}^\ell $$ is linearly dependent of the columns of some matrix in $$\mathbb {G}^{\ell \times k}$$ sampled according to distribution $$\mathcal {D}_{\ell ,k}$$ . It covers known assumptions such as $$\textsf {DDH},\, 2\text{- }\textsf {Lin}$$ (Linear Assumption) and $$k\text{- }\textsf {Lin}$$ (the k-Linear Assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of $$\mathcal {D}_{\ell ,k}$$ . We use the hardness results to find new distributions for which the $$\mathcal {D}_{\ell ,k}\text{- }\textsf {MDDH}$$ Assumption holds generically in m-linear groups. In particular, our new assumptions $$2\text{- }\textsf {SCasc}$$ and $$2\text{- }\textsf {ILin}$$ are generically hard in bilinear groups and, compared to $$2\text{- }\textsf {Lin}$$ , have shorter description size, which is a relevant parameter for efficiency in many applications. These results support using our new assumptions as natural replacements for the $$2\text{- }\textsf {Lin}$$ assumption which was already used in a large number of applications. To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any $$\textsf {MDDH}$$ Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs. As an independent contribution, we give more efficient NIZK and NIWI proofs for membership in a subgroup of $$\mathbb {G}^\ell $$ . The results imply very significant efficiency improvements for a large number of schemes. [ABSTRACT FROM AUTHOR]

Adaptive security is a strong security notion that captures additional security threats that are not addressed by static corruptions. For instance, it captures real-world scenarios where 'hackers' actively break into computers, possibly while they are executing secure protocols. Studying this setting is interesting from both theoretical and practical points of view. A primary building block in designing adaptively secure protocols is a non-committing encryption (NCE) that implements secure communication channels in the presence of adaptive corruptions. Current constructions require a number of public key operations that grow linearly with the length of the message. Furthermore, general two-party protocols require a number of NCE calls that dependent both on the circuit size and on the security parameter. In this paper, we study the two-party setting in which at most one of the parties is adaptively corrupted, and demonstrate the feasibility of ( 1) NCE with constant number of public key operations for large message spaces, ( 2) oblivious transfer with constant number of public key operations for large sender's input spaces, and ( 3) constant round secure computation protocols with an overall number of public key operations that is linear in the circuit size. Our study demonstrates that such primitives indeed exist in the presence of single corruptions without erasures, while this is not known for fully adaptive security under standard assumptions (where both parties may get corrupted). Our results are shown in the UC setting with a CRS setup. [ABSTRACT FROM AUTHOR]

In this work, we present several new generic second-preimage attacks on hash functions. Our first attack is based on the herding attack and applies to various Merkle-Damgård-based iterative hash functions. Compared to the previously known long-message second-preimage attacks, our attack offers more flexibility in choosing the second-preimage message at the cost of a small computational overhead. More concretely, our attack allows the adversary to replace only a few blocks in the original target message to obtain the second preimage. As a result, our new attack is applicable to constructions previously believed to be immune to such second-preimage attacks. Among others, these include the dithered hash proposal of Rivest, Shoup's UOWHF, and the ROX constructions. In addition, we also suggest several time-memory-data tradeoff attack variants, allowing for a faster online phase, and even finding second preimages for shorter messages. We further extend our attack to sequences stronger than the ones suggested in Rivest's proposal. To this end we introduce the kite generator as a new tool to attack any dithering sequence over a small alphabet. Additionally, we analyse the second-preimage security of the basic tree hash construction. Here we also propose several second-preimage attacks and their time-memory-data tradeoff variants. Finally, we show how both our new and the previous second-preimage attacks can be applied even more efficiently when multiple short messages, rather than a single long target message, are available. [ABSTRACT FROM AUTHOR]

At Crypto 1999, Coron, Naccache and Stern described an existential signature forgery against two popular RSA signature standards, ISO 9796-1 and ISO 9796-2. Following this attack, ISO 9796-1 was withdrawn, and ISO 9796-2 was amended by increasing the message digest to at least 160 bits. In this paper, we describe an attack against the amended version of ISO 9796-2, for all modulus sizes. Our new attack is based on Bernstein's algorithm for detecting smooth numbers, instead of trial division. In practice, we were able to compute a forgery in only 2 days on a network of 19 servers. Our attack can also be extended to EMV signatures, an ISO 9796-2-compliant format with extra redundancy. In response to this new attack, the ISO 9796-2 standard was amended again in late 2010. [ABSTRACT FROM AUTHOR]

In this paper, we present three digital signature schemes with tight security reductions in the random oracle model. Our first signature scheme is a particularly efficient version of the short exponent discrete log-based scheme of Girault et al. (J Cryptol 19(4):463-487, ). Our scheme has a tight reduction to the decisional short discrete logarithm problem, while still maintaining the non-tight reduction to the computational version of the problem upon which the original scheme of Girault et al. is based. The second signature scheme we construct is a modification of the scheme of Lyubashevsky (Advances in Cryptology-ASIACRYPT 2009, vol 5912 of Lecture Notes in Computer Science, pp 598-616, Tokyo, Japan, December 6-10, 2009. Springer, Berlin, ) that is based on the worst-case hardness of the shortest vector problem in ideal lattices. And the third scheme is a very simple signature scheme that is based directly on the hardness of the subset sum problem. We also present a general transformation that converts what we term $$lossy $$ identification schemes into signature schemes with tight security reductions. We believe that this greatly simplifies the task of constructing and proving the security of such signature schemes. [ABSTRACT FROM AUTHOR]

We present new constructions of leakage-resilient cryptosystems, which remain provably secure even if the attacker learns some arbitrary partial information about their internal secret-key. For any polynomial $$\ell $$ , we can instantiate these schemes so as to tolerate up to $$\ell $$ bits of leakage. While there has been much prior work constructing such leakage-resilient cryptosystems under concrete number-theoretic and algebraic assumptions, we present the first schemes under general and minimal assumptions. In particular, we construct: These are the first constructions of leakage-resilient symmetric-key primitives that do not rely on public-key assumptions. We also get the first constructions of leakage-resilient public-key encryption from 'search assumptions,' such as the hardness of factoring or CDH. Although our schemes can tolerate arbitrarily large amounts of leakage, the tolerated rate of leakage (defined as the ratio of leakage amount to key size) is rather poor in comparison with prior results under specific assumptions. As a building block of independent interest, we study a notion of weak hash-proof systems in the public-key and symmetric-key settings. While these inherit some of the interesting security properties of standard hash-proof systems, we can instantiate them under general assumptions. [ABSTRACT FROM AUTHOR]

Yao's garbled circuit (GC) technique is a powerful cryptographic tool which allows to 'encrypt' a circuit $$C$$ by another circuit $${\hat{C}}$$ in a way that hides all information except for the final output. Yao's original construction incurs a constant overhead in both computation and communication per gate of the circuit $$C$$ (proportional to the complexity of symmetric encryption). Kolesnikov and Schneider (ICALP 2008) introduced an optimized variant that garbles XOR gates 'for free' in a way that involves no cryptographic operations and no communication. This variant has become very popular and has lead to notable performance improvements. The security of the free-XOR optimization was originally proved in the random oracle model. Despite some partial progress (Choi et al., TCC 2012), the question of replacing the random oracle with a standard cryptographic assumption has remained open. We resolve this question by showing that the free-XOR approach can be realized in the standard model under the learning parity with noise (LPN) assumption. Our result is obtained in two steps: As an additional contribution, we prove that the combination of RK and KDM security is nontrivial in the following sense: There exists an encryption scheme which achieves RK security and KDM security separately, but breaks completely at the presence of combined RK-KDM attacks. [ABSTRACT FROM AUTHOR]

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: They can be described by a sparse input-output dependency graph $$G$$ and a small predicate $$P$$ that is applied at each output. Following the works of Cryan and Miltersen (MFCS'01) and by Mossel et al (STOC'03), we ask: which graphs and predicates yield 'small-bias' generators (that fool linear distinguishers)? We identify an explicit class of degenerate predicates and prove the following. For most graphs, all non-degenerate predicates yield small-bias generators, $$f:\{0,1\}^n \rightarrow \{0,1\}^m$$ , with output length $$m = n^{1 + \epsilon }$$ for some constant $$\epsilon > 0$$ . Conversely, we show that for most graphs, degenerate predicates are not secure against linear distinguishers, even when the output length is linear $$m=n+\Omega (n)$$ . Taken together, these results expose a dichotomy: Every predicate is either very hard or very easy, in the sense that it either yields a small-bias generator for almost all graphs or fails to do so for almost all graphs. As a secondary contribution, we attempt to support the view that small-bias is a good measure of pseudorandomness for local functions with large stretch. We do so by demonstrating that resilience to linear distinguishers implies resilience to a larger class of attacks. [ABSTRACT FROM AUTHOR]

We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve (Proceedings of the 18th annual ACM symposium on theory of computing, pp 364-369, ) showed that for any two-party $$r$$ -round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by $$\varOmega (1/r)$$ . However, the best previously known protocol only guarantees $$O(1/\sqrt{r})$$ bias, and the question of whether Cleve's bound is tight has remained open for more than 20 years. In this paper, we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: We construct an $$r$$ -round protocol with bias $$O(1/r)$$ . [ABSTRACT FROM AUTHOR]

A modular approach to constructing cryptographic protocols leads to simple designs but often inefficient instantiations. On the other hand, ad hoc constructions may yield efficient protocols at the cost of losing conceptual simplicity. We suggest a new design paradigm, structure-preserving cryptography, that provides a way to construct modular protocols with reasonable efficiency while retaining conceptual simplicity. A cryptographic scheme over a bilinear group is called structure-preserving if its public inputs and outputs consist of elements from the bilinear groups and their consistency can be verified by evaluating pairing-product equations. As structure-preserving schemes smoothly interoperate with each other, they are useful as building blocks in modular design of cryptographic applications. This paper introduces structure-preserving commitment and signature schemes over bilinear groups with several desirable properties. The commitment schemes include homomorphic, trapdoor and length-reducing commitments to group elements, and the structure-preserving signature schemes are the first ones that yield constant-size signatures on multiple group elements. A structure-preserving signature scheme is called automorphic if the public keys lie in the message space, which cannot be achieved by compressing inputs via a cryptographic hash function, as this would destroy the mathematical structure we are trying to preserve. Automorphic signatures can be used for building certification chains underlying privacy-preserving protocols. Among a vast number of applications of structure-preserving protocols, we present an efficient round-optimal blind-signature scheme and a group signature scheme with an efficient and concurrently secure protocol for enrolling new members. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the intersection of private datasets of two parties, where the datasets contain lists of elements taken from a large domain. This problem has many applications for online collaboration. In this work, we present protocols based on the use of homomorphic encryption and different hashing schemes for both the semi-honest and malicious environments. The protocol for the semi-honest environment is secure in the standard model, while the protocol for the malicious environment is secure in the random oracle model. Our protocols obtain linear communication and computation overhead. We further implement different variants of our semi-honest protocol. Our experiments show that the asymptotic overhead of the protocol is affected by different constants. (In particular, the degree of the polynomials evaluated by the protocol matters less than the number of polynomials that are evaluated.) As a result, the protocol variant with the best asymptotic overhead is not necessarily preferable for inputs of reasonable size. [ABSTRACT FROM AUTHOR]

A non-interactive zero-knowledge (NIZK) proof can be used to demonstrate the truth of a statement without revealing anything else. It has been shown under standard cryptographic assumptions that NIZK proofs of membership exist for all languages in NP. While there is evidence that such proofs cannot be much shorter than the corresponding membership witnesses, all known NIZK proofs for NP languages are considerably longer than the witnesses. Soon after Gentry's construction of fully homomorphic encryption, several groups independently contemplated the use of hybrid encryption to optimize the size of NIZK proofs and discussed this idea within the cryptographic community. This article formally explores this idea of using fully homomorphic hybrid encryption to optimize NIZK proofs and other related cryptographic primitives. We investigate the question of minimizing the communication overhead of NIZK proofs for NP and show that if fully homomorphic encryption exists then it is possible to get proofs that are roughly of the same size as the witnesses. Our technique consists in constructing a fully homomorphic hybrid encryption scheme with ciphertext size $$|m|+{\mathrm {poly}}(k)$$ , where $$m$$ is the plaintext and $$k$$ is the security parameter. Encrypting the witness for an NP-statement allows us to evaluate the NP-relation in a communication-efficient manner. We apply this technique to both standard non-interactive zero-knowledge proofs and to universally composable non-interactive zero-knowledge proofs. The technique can also be applied outside the realm of non-interactive zero-knowledge proofs, for instance to get witness-size interactive zero-knowledge proofs in the plain model without any setup or to minimize the communication in secure computation protocols. [ABSTRACT FROM AUTHOR]

This paper addresses deterministic public-key encryption schemes (DE), which are designed to provide meaningful security when only source of randomness in the encryption process comes from the message itself. We propose a general construction of DE that unifies prior work and gives novel schemes. Specifically, its instantiations include: The security proofs for these schemes are enabled by three tools that are of broader interest: We also extend our result about computational entropy to the average case, which is useful in reasoning about leakage-resilient cryptography: leaking λ bits of information reduces the quality of computational entropy by a factor of 2 and its quantity by λ. [ABSTRACT FROM AUTHOR]

In tandem with recent progress on computing on encrypted data via fully homomorphic encryption, we present a framework for computing on authenticated data via the notion of slightly homomorphic signatures, or $$P$$ -homomorphic signatures. With such signatures, it is possible for a third party to derive a signature on the object $$m'$$ from a signature of $$m$$ as long as $$P(m,m')=1$$ for some predicate $$P$$ which captures the 'authenticatable relationship" between $$m'$$ and $$m$$ . Moreover, a derived signature on $$m'$$ reveals no extra information about the parent $$m$$ . Our definition is carefully formulated to provide one unified framework for a variety of distinct concepts in this area, including arithmetic, homomorphic, quotable, redactable, transitive signatures, and more. It includes being unable to distinguish a derived signature from a fresh one even when given the original signature. The inability to link derived signatures to their original sources prevents some practical privacy and linking attacks, which is a challenge not satisfied by most prior works. Under this strong definition, we then provide generic constructions for all univariate and closed predicates, and specific efficient constructions for a broad class of natural predicates such as quoting, subsets, weighted sums, averages, and Fourier transforms. To our knowledge, these are the first efficient constructions for these predicates (excluding subsets) that provably satisfy this strong security notion. [ABSTRACT FROM AUTHOR]

In private information retrieval (PIR), a client queries an $$n$$ -bit database in order to retrieve an entry of her choice, while maintaining privacy of her query value. Chor et al. [J ACM 45(6):965-981, ] showed that, in the information-theoretical setting, a linear amount of communication is required for classical PIR protocols (thus the trivial protocol is optimal). This linear lower bound was shown by Nayak [FOCS 1999, pp. 369-376, ] to hold also in the quantum setting. Here, we extend Nayak's result by considering approximate privacy, and requiring security only against specious adversaries, which are, in analogy to classical honest-but-curious adversaries, the weakest reasonable quantum adversaries. We show that, even in this weakened scenario, quantum private information retrieval (QPIR) requires $$n$$ qubits of communication. From this follows that Le Gall's recent QPIR protocol with sublinear communication complexity [Theory Comput. 8(1):369-374, ] is not information-theoretically private, against the weakest reasonable cryptographic adversary. [ABSTRACT FROM AUTHOR]

IND- CCA (indistinguishability under adaptive chosen-ciphertext attacks) is a central notion of security for public-key encryption, defined and targeted in many papers. Non-triviality of the notion requires that the adversary not query the challenge ciphertext to the decryption oracle. We point out that this 'no-challenge-decryption' condition can be formalized in several different ways and the literature is not consistent, sometimes doing it one way, sometimes another, and assuming it makes no difference. We show that the latter perception is incorrect. It does make a difference, for the resulting notions are not equivalent. Specifically, we consider four notions corresponding to whether challenge decryption is disallowed in both phases of the adversary's attack or just in the second, and, orthogonally, whether the disallowance is 'penalty' or 'exclusion' based. We show that the notions are not all equivalent for public-key encryption (PKE). We then show that, in contrast, they are equivalent for key-encapsulation mechanisms (KEMs). Our work shows that subtle foundational issues exist even with notions that are supposedly well-established and unambiguous, and highlights the need to be careful and precise with regard to 'minor' definitional 'details'. [ABSTRACT FROM AUTHOR]

Secure Multi-Party Computation (MPC) providing information-theoretic security allows a set of n parties to securely compute an agreed function over a finite field, even if t parties are under the control of a computationally unbounded active adversary. Asynchronous MPC (AMPC) is an important variant of MPC, which works over an asynchronous network. It is well known that perfect AMPC is possible if and only if t< n/4, while statistical AMPC is possible if and only if t< n/3. In this paper, we study the communication complexity of AMPC protocols (both statistical and perfect) designed with exactly n=4 t+1 parties. Our major contributions in this paper are as follows: [ABSTRACT FROM AUTHOR]

The Even-Mansour cryptosystem was developed in 1991 in an attempt to obtain the simplest possible block cipher, using only one publicly known random permutation and two whitening keys. Its exact security remained open for more than 20 years in the sense that the lower bound proof considered known plaintexts, whereas the best published attack (which is based on differential cryptanalysis) required chosen plaintexts. In this paper, we solve this open problem by introducing the new extended slide attack (abbreviated as slidex) which matches the T= Ω(2/ D) lower bound on the time T for any number of known plaintexts D. By using this tight security result, we show that a simplified single-key variant of the Even-Mansour scheme has exactly the same security as the original two-key scheme. We then show how to apply variants of the slidex attack to several other cryptosystems, including an Even-Mansour variant which adds rather than XORs its whitening keys, DES protected with decorrelation modules, various flavors of DESX, and a reduced-round version of GOST. In addition, we show how to apply the slidex attack in extreme scenarios in which the cryptanalyst is only given some partial information about the plaintexts, or when he can only use a tiny amount of memory. [ABSTRACT FROM AUTHOR]

We present new techniques for the cryptanalysis of hash functions. Our contributions are two-fold: both on the search level of the compression function and on the meta-structure. The former led to the neutral bits technique, while the latter led to the multi-block technique. The usefulness of these techniques is demonstrated on SHA-0 and SHA-1, but they are applicable to other hash functions as well. We use these techniques to find a collision of the full SHA-0 which is the first published collision of this function, and very efficient collision attacks on reduced versions of SHA-1. [ABSTRACT FROM AUTHOR]

We put forward a new technique to construct very efficient and compact signature schemes. Our technique combines several instances of only a mildly secure signature scheme to obtain a fully secure scheme. Since the mild security notion we require is much easier to achieve than full security, we can combine our strategy with existing techniques to obtain a number of interesting new (stateless and fully secure) signature schemes. Concretely, we get (1) A scheme based on the computational Diffie-Hellman (CDH) assumption in pairing-friendly groups. Signatures contain $$\mathbf {O}(1)$$ and verification keys $$\mathbf {O}(\log k)$$ group elements, where $$k$$ is the security parameter. Our scheme is the first fully secure CDH-based scheme with such compact verification keys. (2) A scheme based on the (nonstrong) RSA assumption in which both signatures and verification keys contain $$\mathbf {O}(1)$$ group elements. Our scheme is significantly more efficient than existing RSA-based schemes. (3) A scheme based on the Short Integer Solutions (SIS) assumption. Signatures contain $$\mathbf {O}(\log (k)\cdot m)$$ and verification keys $$\mathbf {O}(n\cdot m) {\mathbb {Z}}_p$$ -elements, where $$p$$ may be polynomial in $$k$$ , and $$n,m$$ denote the usual SIS matrix dimensions. Compared to state-of-the-art SIS-based schemes, this gives very small verification keys, at the price of slightly larger signatures. In all cases, the involved constants are small, and the arising schemes provide significant improvements upon state-of-the-art schemes. The only price we pay is a rather large (polynomial) loss in the security reduction. However, this loss can be significantly reduced at the cost of an additive term in signature and verification key size. [ABSTRACT FROM AUTHOR]

The common random string model introduced by Blum, Feldman, and Micali permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. We can think of this model as a trusted party generating a random string and giving it to all parties in the protocol. However, the introduction of such a third party should set alarm bells going off: Who is this trusted party? Why should we trust that the string is random? Even if the string is uniformly random, how do we know it does not leak private information to the trusted party? The very point of doing cryptography in the first place is to prevent us from trusting the wrong people with our secrets. In this paper, we propose the more realistic multi-string model. Instead of having one trusted authority, we have several authorities that generate random strings. We do not trust any single authority; we only assume a majority of them generate random strings honestly. Our results also hold even if different subsets of these strings are used in different instances, as long as a majority of the strings used at any particular invocation is honestly generated. This security model is reasonable and at the same time very easy to implement. We could for instance imagine random strings being provided on the Internet, and any set of parties that want to execute a protocol just need to agree on which authorities' strings they want to use. We demonstrate the use of the multi-string model in several fundamental cryptographic tasks. We define multi-string non-interactive zero-knowledge proofs and prove that they exist under general cryptographic assumptions. Our multi-string NIZK proofs have very strong security properties such as simulation-extractability and extraction zero-knowledge, which makes it possible to compose them with arbitrary other protocols and to reuse the random strings. We also build efficient simulation-sound multi-string NIZK proofs for circuit satisfiability based on groups with a bilinear map. The sizes of these proofs match the best constructions in the single common random string model. We also suggest a universally composable commitment scheme in the multi-string model. It has been proven that UC commitment does not exist in the plain model without setup assumptions. Prior to this work, constructions were only known in the common reference string model and the registered public key model. The UC commitment scheme can be used in a simple coin-flipping protocol to create a uniform random string, which in turn enables the secure realization of any multi-party computation protocol. [ABSTRACT FROM AUTHOR]

In this paper we show a relation between the notions of verifiable random functions (VRFs) and identity-based key encapsulation mechanisms (IB-KEMs). In particular, we propose a class of IB-KEMs that we call VRF-suitable, and we propose a direct construction of VRFs from VRF-suitable IB-KEMs. Informally, an IB-KEM is VRF-suitable if it provides what we call unique decapsulation (i.e., given a ciphertext C produced with respect to an identity ID, all the secret keys corresponding to identity ID′, decapsulate to the same value, even if ID≠ ID′), and it satisfies an additional property that we call pseudo-random decapsulation. In a nutshell, pseudo-random decapsulation means that if one decapsulates a ciphertext C, produced with respect to an identity ID, using the decryption key corresponding to any other identity ID′, the resulting value looks random to a polynomially bounded observer. Our construction is of interest both from a theoretical and a practical perspective. Indeed, apart from establishing a connection between two seemingly unrelated primitives, our methodology is direct in the sense that, in contrast to most previous constructions, it avoids the inefficient Goldreich-Levin hardcore bit transformation. As an additional contribution, we propose a new VRF-suitable IB-KEM based on the decisional ℓ-weak Bilinear Diffie-Hellman Inversion assumption. Interestingly, when applying our transformation to this scheme, we obtain a new VRF construction that is secure under the same assumption, and it efficiently supports a large input space. [ABSTRACT FROM AUTHOR]

An obfuscator is a compiler that transforms any program (which we will view in this work as a boolean circuit) into an obfuscated program (also a circuit) that has the same input-output functionality as the original program, but is 'unintelligible'. Obfuscation has applications for cryptography and for software protection. Barak et al. (CRYPTO 2001, pp. 1-18, ) initiated a theoretical study of obfuscation, which focused on black-box obfuscation, where the obfuscated circuit should leak no information except for its (black-box) input-output functionality. A family of functionalities that cannot be obfuscated was demonstrated. Subsequent research has showed further negative results as well as positive results for obfuscating very specific families of circuits, all with respect to black box obfuscation. This work is a study of a new notion of obfuscation, which we call best-possible obfuscation. Best possible obfuscation makes the relaxed requirement that the obfuscated program leaks as little information as any other program with the same functionality (and of similar size). In particular, this definition allows the program to leak information that cannot be obtained from a black box. Best-possible obfuscation guarantees that any information that is not hidden by the obfuscated program is also not hidden by any other similar-size program computing the same functionality, and thus the obfuscation is (literally) the best possible. In this work we study best-possible obfuscation and its relationship to previously studied definitions. Our main results are: (1) A separation between black-box and best-possible obfuscation. We show a natural obfuscation task that can be achieved under the best-possible definition, but cannot be achieved under the black-box definition. (2) A hardness result for best-possible obfuscation, showing that strong (information-theoretic) best-possible obfuscation implies a collapse in the Polynomial-Time Hierarchy. (3) An impossibility result for efficient best-possible (and black-box) obfuscation in the presence of random oracles. This impossibility result uses a random oracle to construct hard-to-obfuscate circuits, and thus it does not imply impossibility in the standard model. [ABSTRACT FROM AUTHOR]

Key-dependent message (KDM) secure encryption schemes provide secrecy even when the attacker sees encryptions of messages related to the secret-key sk. Namely, the scheme should remain secure even when messages of the form f( sk) are encrypted, where f is taken from some function class $\mathcal{F}$. A KDM amplification procedure takes an encryption scheme which satisfies $\mathcal{F}$-KDM security, and boosts it into a $\mathcal{G}$-KDM secure scheme, where the function class $\mathcal{G}$ should be richer than $\mathcal{F}$. It was recently shown by Brakerski et al. (TCC 2011) and Barak et al. (EUROCRYPT 2010) that a strong form of amplification is possible, provided that the underlying encryption scheme satisfies some special additional properties. In this work, we prove the first generic KDM amplification theorem which relies solely on the KDM security of the underlying scheme without making any other assumptions. Specifically, we show that an elementary form of KDM security against functions in which each output bit either copies or flips a single bit of the key (a.k.a. projections) can be amplified into KDM security with respect to any function family that can be computed in arbitrary fixed polynomial-time. Furthermore, our amplification theorem and its proof are insensitive to the exact setting of KDM security, and they hold in the presence of multiple-keys and in the symmetric-key/public-key and the CPA/CCA cases. As a result, we can amplify the security of most known KDM constructions, including ones that could not be amplified before. Finally, we study the minimal conditions under which full-KDM security (with respect to all functions) can be achieved. We show that under strong notion of KDM security, the existence of fully homomorphic encryption which allows to encrypt the secret-key (i.e., 'cyclic-secure') is not only sufficient for full-KDM security, as shown by Barak et al., but also necessary. On the other hand, we observe that for standard KDM security, this condition can be relaxed by adopting Gentry's bootstrapping technique (STOC 2009) to the KDM setting. [ABSTRACT FROM AUTHOR]

Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O'Neill (CRYPTO '07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security when the plaintext is distributed over a small set. Bellare et al. addressed this difficulty by requiring semantic security to hold only when the plaintext has high min-entropy from the adversary's point of view. In many applications, however, an adversary may obtain auxiliary information that is related to the plaintext. Specifically, when deterministic encryption is used as a building block of a larger system, it is rather likely that plaintexts do not have high min-entropy from the adversary's point of view. In such cases, the framework of Bellare et al. might fall short from providing robust security guarantees. We formalize a framework for studying the security of deterministic public-key encryption schemes with respect to auxiliary inputs. Given the trivial requirement that the plaintext should not be efficiently recoverable from the auxiliary input, we focus on hard-to-invert auxiliary inputs. Within this framework, we propose two schemes: the first is based on the d-linear assumption for any d≥1 (including, in particular, the decisional Diffie-Hellman assumption), and the second is based on a rather general class of subgroup indistinguishability assumptions (including, in particular, the quadratic residuosity assumption and Paillier's composite residuosity assumption). Our schemes are secure with respect to any auxiliary input that is subexponentially hard to invert (assuming the standard hardness of the underlying computational assumptions). In addition, our first scheme is secure even in the multi-user setting where related plaintexts may be encrypted under multiple public keys. Constructing a scheme that is secure in the multi-user setting (even without considering auxiliary inputs) was identified by Bellare et al. as an important open problem. [ABSTRACT FROM AUTHOR]

The Virtual Black Box (VBB) property for program obfuscators provides a strong guarantee: anything computable by an efficient adversary, given the obfuscated program, can also be computed by an efficient simulator, with only oracle access to the program. However, we know how to achieve this notion only for very restricted classes of programs. This work studies a simple relaxation of VBB: allow the simulator unbounded computation time, while still allowing only polynomially many queries to the oracle. We demonstrate the viability of this relaxed notion, which we call Virtual Grey Box (VGB), in the context of composable obfuscators for point programs: it is known that, with respect to VBB, if such obfuscators exist, then there exist multi-bit point obfuscators (also known as 'digital lockers') and subsequently also very strong variants of encryption that are resilient to various attacks, such as key leakage and key-dependent-messages. However, no composable VBB-obfuscators for point programs have been shown. We show composable VGB-obfuscators for point programs under a strong variant of the Decision Diffie-Hellman assumption. We show that VGB (instead of VBB) obfuscation still suffices for the above applications, as well as for new applications. This includes extensions to the public key setting and to encryption schemes with resistance to certain related key attacks (RKA). [ABSTRACT FROM AUTHOR]

Plaintext-aware encryption is a simple concept: a public-key encryption scheme is plaintext aware if no polynomial-time algorithm can create a ciphertext without 'knowing' the underlying message. However, the formal definitions of plaintext awareness are complex. This paper analyses these formal security definitions and presents the only known viable strategy for proving a scheme is PA2 plaintext aware. At the heart of this strategy is a new notion called PA1+ plaintext awareness. This security notion conceptually sits between PA1 and PA2 plaintext awareness (although it is formally distinct from either of these notions). We show exactly how this new security notion relates to the existing notions and how it can be used to prove PA2 plaintext awareness. [ABSTRACT FROM AUTHOR]

A signature scheme is fully leakage resilient (Katz and Vaikuntanathan, ASIACRYPT'09) if it is existentially unforgeable under an adaptive chosen-message attack even in a setting where an adversary may obtain bounded (yet arbitrary) leakage information on all intermediate values that are used throughout the lifetime of the system. This is a strong and meaningful notion of security that captures a wide range of side-channel attacks. One of the main challenges in constructing fully leakage-resilient signature schemes is dealing with leakage that may depend on the random bits used by the signing algorithm, and constructions of such schemes are known only in the random-oracle model. Moreover, even in the random-oracle model, known schemes are only resilient to leakage of less than half the length of their signing key. In this paper we construct the first fully leakage-resilient signature schemes without random oracles. We present a scheme that is resilient to any leakage of length (1− o(1)) L bits, where L is the length of the signing key. Our approach relies on generic cryptographic primitives, and at the same time admits rather efficient instantiations based on specific number-theoretic assumptions. In addition, we show that our approach extends to the continual-leakage model, recently introduced by Dodis, Haralambiev, Lopez-Alt and Wichs (FOCS'10), and by Brakerski, Tauman Kalai, Katz and Vaikuntanathan (FOCS'10). In this model the signing key is allowed to be refreshed, while its corresponding verification key remains fixed, and the amount of leakage is assumed to be bounded only in between any two successive key refreshes. [ABSTRACT FROM AUTHOR]

Predicate encryption is a new paradigm for public-key encryption that generalizes identity-based encryption and more. In predicate encryption, secret keys correspond to predicates and ciphertexts are associated with attributes; the secret key SK corresponding to a predicate f can be used to decrypt a ciphertext associated with attribute I if and only if f( I)=1. Constructions of such schemes are currently known only for certain classes of predicates. We construct a scheme for predicates corresponding to the evaluation of inner products over ℤ (for some large integer N). This, in turn, enables constructions in which predicates correspond to the evaluation of disjunctions, polynomials, CNF/DNF formulas, thresholds, and more. Besides serving as a significant step forward in the theory of predicate encryption, our results lead to a number of applications that are interesting in their own right. [ABSTRACT FROM AUTHOR]

We present the first aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a novel application of a recent signature scheme due to Waters. Signatures in our aggregate signature scheme are sequentially constructed, but knowledge of the order in which messages were signed is not necessary for verification. The aggregate signatures obtained are shorter than Lysyanskaya et al.'s sequential aggregates and can be verified more efficiently than Boneh et al.'s aggregates. We also consider applications to secure routing and proxy signatures. [ABSTRACT FROM AUTHOR]