Search

Imagine many small devices send data to a single receiver, encrypted using the receiver΄s public key. Assume an adversary that has the power to adaptively corrupt a subset of these devices. Given the information obtained from these corruptions, do the ciphertexts from uncorrupted devices remain secure? Recent results suggest that conventional security notions for encryption schemes (like IND-CCA security) do not suffice in this setting. To fill this gap, the notion of security against selective-opening attacks (SOA security) has been introduced. It has been shown that lossy encryption implies SOA security against a passive, i.e., only eavesdropping and corrupting, adversary (SO-CPA). However, the known results on SOA security against an active adversary (SO-CCA) are rather limited. Namely, while there exist feasibility results, the (time and space) complexity of currently known SO-CCA secure schemes depends on the number of devices in the setting above. In this contribution, we devise a new solution to the selective opening problem that does not build on lossy encryption. Instead, we combine techniques from non-committing encryption and hash proof systems with a new technique (dubbed ˵cross-authentication codes″) to glue several ciphertext parts together. The result is a rather practical SO-CCA secure public-key encryption scheme that does not suffer from the efficiency drawbacks of known schemes. Since we build upon hash proof systems, our scheme can be instantiated using standard number-theoretic assumptions such as decisional Diffie-Hellman DDH), decisional composite residuosity (DCR), and quadratic residuosity (QR). Besides, we construct a conceptually very simple and comparatively efficient SO-CPA secure scheme from (slightly enhanced) trapdoor one-way permutations. We stress that our schemes are completely independent of the number of challenge ciphertexts, and we do not make assumptions about the underlying message distribution (beyond being efficiently samplable). In particular, we do not assume efficient conditional re-samplability of the message distribution. Hence, our schemes are secure in arbitrary settings, even if it is not known in advance how many ciphertexts might be considered for corruptions. [ABSTRACT FROM AUTHOR]

We propose a framework for analyzing classical sampling strategies for estimating the Hamming weight of a large string from a few sample positions, when applied to a multi-qubit quantum system instead. The framework shows how to interpret the result of such a strategy and how to define its accuracy when applied to a quantum system. Furthermore, we show how the accuracy of any strategy relates to its accuracy in its classical usage, which is well understood for the important examples. We show the usefulness of our framework by using it to obtain new and simple security proofs for the following quantum-cryptographic schemes: BB84 quantum-key-distribution, and quantum oblivious-transfer from bit-commitment. [ABSTRACT FROM AUTHOR]

We propose a general security definition for cryptographic quantum protocols that implement classical non-reactive two-party tasks. The definition is expressed in terms of simple quantum- information-theoretic conditions which must be satisfied by the protocol to be secure. The conditions are uniquely determined by the ideal functionality ]> defining the cryptographic task to be implemented. We then show the following composition result. If quantum protocols Π1,...,Πℓ securely implement ideal functionalities ]> according to our security definition, then any purely classical two-party protocol, which makes sequential calls to ]> , is equally secure as the protocol obtained by replacing the calls to ]> with the respective quantum protocols Π1,...,Πℓ. Hence, our approach yields the minimal security requirements which are strong enough for the typical use of quantum protocols as subroutines within larger classical schemes. Finally, we show that recently proposed quantum protocols for secure identification and oblivious transfer in the bounded-quantum-storage model satisfy our security definition, and thus compose in the above sense. [ABSTRACT FROM AUTHOR]

We consider two-party quantum protocols starting with a transmission of some random BB84 qubits followed by classical messages. We show a general ˵compiler″ improving the security of such protocols: if the original protocol is secure against an ˵almost honest″ adversary, then the compiled protocol is secure against an arbitrary computationally bounded (quantum) adversary. The compilation preserves the number of qubits sent and the number of rounds up to a constant factor. The compiler also preserves security in the bounded-quantum-storage model (BQSM), so if the original protocol was BQSM-secure, the compiled protocol can only be broken by an adversary who has large quantum memory and large computing power. This is in contrast to known BQSM-secure protocols, where security breaks down completely if the adversary has larger quantum memory than expected. We show how our technique can be applied to quantum identification and oblivious transfer protocols. [ABSTRACT FROM AUTHOR]

The study of deterministic public-key encryption was initiated by Bellare et al. (CRYPTO ΄07), who provided the ˵strongest possible″ notion of security for this primitive (called PRIV) and constructions in the random oracle (RO) model. We focus on constructing efficient deterministic encryption schemes without random oracles. To do so, we propose a slightly weaker notion of security, saying that no partial information about encrypted messages should be leaked as long as each message is a-priori hard-to-guess given the others (while PRIV did not have the latter restriction). Nevertheless, we argue that this version seems adequate for many practical applications. We show equivalence of this definition to single-message and indistinguishability-based ones, which are easier to work with. Then we give general constructions of both chosen-plaintext (CPA) and chosen-ciphertext-attack (CCA) secure deterministic encryption schemes, as well as efficient instantiations of them under standard number-theoretic assumptions. Our constructions build on the recently-introduced framework of Peikert and Waters (STOC ΄08) for constructing CCA-secure probabilistic encryption schemes, extending it to the deterministic-encryption setting as well. [ABSTRACT FROM AUTHOR]

Consider an abstract storage device ]> that can hold a single element x from a fixed, publicly known finite group ]> . Storage is private in the sense that an adversary does not have read access to ]> at all. However, ]> is non-robust in the sense that the adversary can modify its contents by adding some offset ]> . Due to the privacy of the storage device, the value ∆ can only depend on an adversary΄s a priori knowledge of x. We introduce a new primitive called an algebraic manipulation detection (AMD) code, which encodes a source s into a value x stored on ]> so that any tampering by an adversary will be detected. We give a nearly optimal construction of AMD codes, which can flexibly accommodate arbitrary choices for the length of the source s and security level. We use this construction in two applications: We show how to efficiently convert any linear secret sharing scheme into a robust secret sharing scheme, which ensures that no unqualified subset of players can modify their shares and cause the reconstruction of some value s' ≠ s. We show how to build nearly optimal robust fuzzy extractors for several natural metrics. Robust fuzzy extractors enable one to reliably extract and later recover random keys from noisy and non-uniform secrets, such as biometrics, by relying only on non-robust public storage. In the past, such constructions were known only in the random oracle model, or required the entropy rate of the secret to be greater than half. Our construction relies on a randomly chosen common reference string (CRS) available to all parties. [ABSTRACT FROM AUTHOR]

Randomness extraction is of fundamental importance for information-theoretic cryptography. It allows to transform a raw key about which an attacker has some limited knowledge into a fully secure random key, on which the attacker has essentially no information. Up to date, only very few randomness-extraction techniques are known to work against an attacker holding quantum information on the raw key. This is very much in contrast to the classical (non-quantum) setting, which is much better understood and for which a vast amount of different techniques are known and proven to work. We prove a new randomness-extraction technique, which is known to work in the classical setting, to be secure against a quantum attacker as well. Randomness extraction is done by xor΄ing a so-called δ-biased mask to the raw key. Our result allows to extend the classical applications of this extractor to the quantum setting. We discuss the following two applications. We show how to encrypt a long message with a short key, information-theoretically secure against a quantum attacker, provided that the attacker has enough quantum uncertainty on the message. This generalizes the concept of entropically-secure encryption to the case of a quantum attacker. As second application, we show how to do error-correction without leaking partial information to a quantum attacker. Such a technique is useful in settings where the raw key may contain errors, since standard error-correction techniques may provide the attacker with information on, say, a secret key that was used to obtain the raw key. [ABSTRACT FROM AUTHOR]

This paper presents a very simple and efficient adaptively-sound perfect NIZK argument system for any NP-language. In contrast to recently proposed schemes by Groth, Ostrovsky and Sahai, our scheme does not pose any restriction on the statements to be proven. Besides, it enjoys a number of desirable properties: it allows to re-use the common reference string (CRS), it can handle arithmetic circuits, and the CRS can be set-up very efficiently without the need for an honest party. We then show an application of our techniques in constructing efficient NIZK schemes for proving arithmetic relations among committed secrets, whereas previous methods required expensive generic NP-reductions. The security of the proposed schemes is based on a strong non-standard assumption, an extended version of the so-called Knowledge-of-Exponent Assumption (KEA) over bilinear groups. We give some justification for using such an assumption by showing that the commonly-used approach for proving NIZK arguments sound does not allow for adaptively-sound statistical NIZK arguments (unless NP ⊂ P/poly). Furthermore, we show that the assumption used in our construction holds with respect to generic adversaries that do not exploit the specific representation of the group elements. We also discuss how to avoid the non-standard assumption in a pre-processing model. [ABSTRACT FROM AUTHOR]

We derive a new entropic quantum uncertainty relation involving min-entropy. The relation is tight and can be applied in various quantum-cryptographic settings. Protocols for quantum 1-out-of-2 Oblivious Transfer and quantum Bit Commitment are presented and the uncertainty relation is used to prove the security of these protocols in the bounded-quantum-storage model according to new strong security definitions. As another application, we consider the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers. The uncertainty relation allows to prove the security of QKD protocols in this setting while tolerating considerably higher error rates compared to the standard model with unbounded adversaries. For instance, for the six-state protocol with one-way communication, a bit-flip error rate of up to 17% can be tolerated (compared to 13% in the standard model). Our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. Previously, the key uncertainty of these ciphers was only known with respect to Shannon entropy. [ABSTRACT FROM AUTHOR]

We consider the problem of secure identification: user U proves to server S that he knows an agreed (possibly low-entropy) password w, while giving away as little information on w as possible, namely the adversary can exclude at most one possible password for each execution of the scheme. We propose a solution in the bounded-quantum-storage model, where U and S may exchange qubits, and a dishonest party is assumed to have limited quantum memory. No other restriction is posed upon the adversary. An improved version of the proposed identification scheme is also secure against a man-in-the-middle attack, but requires U and S to additionally share a high-entropy key k. However, security is still guaranteed if one party loses k to the attacker but notices the loss. In both versions of the scheme, the honest participants need no quantum memory, and noise and imperfect quantum sources can be tolerated. The schemes compose sequentially, and w and k can securely be re-used. A small modification to the identification scheme results in a quantum-key-distribution (QKD) scheme, secure in the bounded-quantum-storage model, with the same re-usability properties of the keys, and without assuming authenticated channels. This is in sharp contrast to known QKD schemes (with unbounded adversary) without authenticated channels, where authentication keys must be updated, and unsuccessful executions can cause the parties to run out of keys. [ABSTRACT FROM AUTHOR]

We study unconditionally secure 1-out-of-2 Oblivious Transfer (1-2 OT). We first point out that a standard security requirement for 1-2 OT of bits, namely that the receiver only learns one of the bits sent, holds if and only if the receiver has no information on the XOR of the two bits. We then generalize this to 1-2 OT of strings and show that the security can be characterized in terms of binary linear functions. More precisely, we show that the receiver learns only one of the two strings sent if and only if he has no information on the result of applying any binary linear function (which non-trivially depends on both inputs) to the two strings. We then argue that this result not only gives new insight into the nature of 1-2 OT, but it in particular provides a very powerful tool for analyzing 1-2 OT protocols. We demonstrate this by showing that with our characterization at hand, the reducibility of 1-2 OT (of strings) to a wide range of weaker primitives follows by a very simple argument. This is in sharp contrast to previous literature, where reductions of 1-2 OT to weaker flavors have rather complicated and sometimes even incorrect proofs. [ABSTRACT FROM AUTHOR]

A black-box secret sharing scheme (BBSSS) for a given access structure works in exactly the same way over any finite Abelian group, as it only requires black-box access to group operations and to random group elements. In particular, there is no dependence on e.g. the structure of the group or its order. The expansion factor of a BBSSS is the length of a vector of shares (the number of group elements in it) divided by the number of players n. At CRYPTO 2002 Cramer and Fehr proposed a threshold BBSSS with an asymptotically minimal expansion factor Θ(log n). In this paper we propose a BBSSS that is based on a new paradigm, namely, primitive sets in algebraic number fields. This leads to a new BBSSS with an expansion factor that is absolutely minimal up to an additive term of at most 2, which is an improvement by a constant additive factor. We provide good evidence that our scheme is considerably more efficient in terms of the computational resources it requires. Indeed, the number of group operations to be performed is instead of for sharing and instead of for reconstruction. Finally, we show that our scheme, as well as that of Cramer and Fehr, has asymptotically optimal randomness efficiency. [ABSTRACT FROM AUTHOR]