We consider (almost) k-wise independent hash functions, whose evaluations on any k inputs are (almost) uniformly random, for very large values of k. Such hash functions need to have a large key that grows linearly with k. However, it may be possible to evaluate them in sub-linear time by only reading a small subset of t ≪ k locations during each evaluation; we call such hash functions t-local. Such hash functions have applications to nearly optimal bounded-use information-theoretic cryptography. Local hash functions were previously studied in several works starting with Siegel (FOCS’89, SICOMP’04). For a hash function with n-bit input and output size, we get the following new results:

Modern messengers use advanced end-to-end encryption protocols to protect message content even if user secrets are ever temporarily exposed. Yet, encryption alone does not prevent user tracking, as protocols often attach metadata, such as sequence numbers, public keys, or even plain user identifiers. This metadata reveals the social network as well as communication patterns between users. Existing protocols that hide metadata in Signal (i.e., Sealed Sender), for MLS-like constructions (Hashimoto et al., CCS 2022), or in mesh networks (Bienstock et al., CCS 2023) are relatively inefficient or specially tailored for only particular settings. Moreover, all existing practical solutions reveal crucial metadata upon exposures of user secrets.

The random oracle model (ROM) allows us to opti-mistically reason about security properties of cryptographic hash functions, and has been hugely influential in designing practical cryptosystems. But it is overly optimistic against non-uniform adversaries, and often suggests security properties and security levels unachievable by any real hash function. To reconcile with this discrepancy, Unruh [CRYPTO '07] proposed the auxiliary-input random oracle model (AI-ROM), where a non-uniform attacker additionally gets a bounded amount of advice about the random oracle. Proving security in the AI-ROM is often much more difficult, but a series of works starting with Unruh provided useful technical tools to do so. Although these tools lead to good results in the information-theoretic setting, they are unsatisfactory in the computational setting, where the random oracle is used alongside other computational hardness assumptions. At the most basic level, we did not even know whether it is possible to efficiently simulate random oracle queries given auxiliary input, which has remained as an explicit open problem since the work of Unruh. In this work, we resolve the above open problem and show how to efficiently simulate auxiliary-input random oracles. Moreover, the simulation has low concrete overhead, leading to small losses in exact security. We use it to prove the security of a broad class of computational schemes in the AI-ROM, including the first non-interactive zero-knowledge (NIZK) scheme in the AI-ROM. As a tool of independent interest, we develop a new notion of ultra-secure pseudorandom functions with fast RAM evaluation, which can achieve$2^{\lambda}$security while having sublinear$\mathrm{o}(\lambda)$evaluation time.

The Messaging Layer Security (MLS) project is an IETF effort aiming to establish an industry-wide standard for secure group messaging (SGM). Its development is supported by several major secure-messaging providers (with a combined user base in the billions) and a growing body of academic research. MLS has evolved over many iterations to become a complex, non-trivial, yet relatively ad-hoc cryptographic protocol. In an effort to tame its complexity and build confidence in its security, past analyses of MLS have restricted themselves to sub-protocols of MLS---most prominently a type of sub-protocol embodying so-called continuous group key agreement (CGKA). However, to date the task of proving or even defining the security of the full MLS protocol has been left open. In this work, we fill in this missing piece. First, we formally capture the security of SGM protocols by defining a corresponding security game, which is parametrized by a safety predicate that characterizes the exact level of security achieved by a construction. Then, we cast MLS as an SGM protocol, showing how to modularly build it from the following three main components (and some additional standard cryptographic primitives) in a black-box fashion: (a) CGKA, (b) forward-secure group AEAD (FS-GAEAD), which is a new primitive and roughly corresponds to an "epoch'' of group messaging, and (c) a so-called PRF-PRNG, which is a two-input hash function that is a pseudorandom function (resp.\ generator with input) in its first (resp.\ second) input. Crucially, the security predicate for the SGM security of MLS can be expressed purely as a function of the security predicates of the underlying primitives, which allows to swap out any of the components and immediately obtain a security statement for the resulting SGM construction. Furthermore, we provide instantiations of all component primitives, in particular of CGKA with MLS's TreeKEM sub-protocol (which we prove adaptively secure) and of FS-GAEAD with a novel construction (which has already been adopted by MLS). Along the way we introduce a collection of new techniques, primitives, and results with applications to other SGM protocols and beyond. For example, we extend the Generalized Selective Decryption proof technique (which is central in CGKA literature) and prove adaptive security for another (practical) more secure CGKA protocol called RTreeKEM (Alwen et al.,\ CRYPTO '20). The modularity of our approach immediately yields a corollary characterizing the security of an SGM construction using RTreeKEM.

One approach toward basing public-key encryption (PKE) schemes on weak and credible assumptions is to build “stronger” or more general schemes generically from “weaker” or more restricted ones. One particular line of work in this context was initiated by Myers and Shelat (FOCS ’09) and continued by Hohenberger, Lewko, and Waters (Eurocrypt ’12), who provide constructions of multi-bit CCA-secure PKE from single-bit CCA-secure PKE. It is well known that encrypting each bit of a plaintext string independently is not CCA-secure—the resulting scheme is malleable. We therefore investigate whether this malleability can be dealt with using the conceptually simple approach of applying a suitable non-malleable code (Dziembowski et al., ICS ’10) to the plaintext and subsequently encrypting the resulting codeword bit by bit. We find that an attacker’s ability to ask multiple decryption queries requires that the underlying code be continuously non-malleable (Faust et al., TCC ’14). Since, as we show, this flavor of non-malleability can only be achieved if the code is allowed to “self-destruct,” the resulting scheme inherits this property and therefore only achieves a weaker variant of CCA security. We formalize this new notion of so-called indistinguishability under self-destruct attacks (IND-SDA) as CCA security with the restriction that the decryption oracle stops working once the attacker submits an invalid ciphertext. We first show that the above approach based on non-malleable codes yields a solution to the problem of domain extension for IND-SDA-secure PKE, provided that the underlying code is continuously non-malleable against (a reduced form of) bit-wise tampering. Then, we prove that the code of Dziembowski et al. is actually already continuously non-malleable against bit-wise tampering. We further investigate the notion of security under self-destruct attacks and combine IND-SDA security with non-malleability under chosen-ciphertext attacks (NM-CPA) to obtain the strictly stronger notion of non-malleability under self-destruct attacks (NM-SDA). We show that NM-SDA security can be obtained from basic IND-CPA security by means of a black-box construction based on the seminal work by Choi et al. (TCC ’08). Finally, we provide a domain extension technique for building a multi-bit NM-SDA scheme from a single-bit NM-SDA scheme. To achieve this goal, we define and construct a novel type of continuous non-malleable code, called secret-state NMC, since, as we show, standard continuous NMCs are insufficient for the natural “encode-then-encrypt-bit-by-bit” approach to work.

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible, for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message or a completely unrelated value. Although such codes do not exist if the family of “tampering functions” ${\mathcal F}$ is completely unrestricted, they are known to exist for many broad tampering families ${\mathcal F}$. One such natural family is the family of tampering functions in the so-called split-state model. Here the message $m$ is encoded into two shares $L$ and $R$, and the attacker is allowed to arbitrarily tamper with $L$ and $R$ individually. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model. Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature but either (1) were constructed in the random oracle model, or (2) relied on advanced cryptographic assumptions (such as noninteractive zero-knowledge proofs and leakage-resilient encryption), or (3) could only encode 1-bit messages. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model. The heart of our construction uses the following new property of the inner-product function $\langle{L,R\rangle}$ over the vector space ${{F}_p}^n$ (for a prime $p$ and large enough dimension $n$): if $L$ and $R$ are uniformly random over ${\mathbb{F}_p}^n$, and $f,g:{\mathbb{F}_p}^n\rightarrow {\mathbb{F}_p}^n$ are two arbitrary functions on $L$ and $R$, then the joint distribution $(\langle{L,R\rangle},\langle{f(L),g(R)\rangle})$ is “close” to the convex combination of “affine distributions” $\{(U,aU+b)\mid a,b\in \mathbb{F}_p\}$, where $U$ is uniformly random in ${\mathbb{F}_p}$. In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so-called quasi-polynomial Freiman--Ruzsa theorem, which was recently established by Sanders [Anal. PDE, 5 (2012), pp. 627--655] as a step toward resolving the polynomial Freiman--Ruzsa conjecture [B. Green, in Surveys in Combinatorics, London Mathematical Society, London, 2005, pp. 1--29].

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs [DPW10], provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely "unrelated value". Although such codes do not exist if the family of "tampering functions" cF allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families cF. The family which received the most attention [DPW10,LL12,DKO13,ADL14,CG14a,CG14b] is the family of tampering functions in the so called (2-part) split-state model: here the message x is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with each L and R individually. Despite this attention, the following problem remained open: Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate: |L|=|R|=O(|x|).

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional errorcorrection (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. Although such codes do not exist if the family of "tampering functions" F is completely unrestricted, they are known to exist for many broad tampering families F. One such natural family is the family of tampering functions in the so called split-state model. Here the message m is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with L and R individually. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model.

In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a nonmalleable extractor. A nonmalleable extractor dramatically strengthens the notion of a strong extractor. A strong extractor takes two inputs, a weakly random $x$ and a uniformly random seed $y$, and outputs a string which appears uniform, even given $y$. For a nonmalleable extractor ${\mathsf{nmExt}}$, the output ${\mathsf{nmExt}}(x,y)$ should appear uniform given $y$ as well as ${\mathsf{nmExt}}(x,{\mathcal A}(y))$, where ${\mathcal A}$ is an arbitrary function with ${\mathcal A}(y) \neq y$. We show that an extractor introduced by Chor and Goldreich is nonmalleable when the entropy rate (the ratio between the entropy and the length of the weakly random string) is above half. It outputs a linear number of bits when the entropy rate is $1/2 + \alpha$ for any $\alpha>0$. Previously, no explicit construction was known for any entropy rate less than 1. To achieve a polynomial running time when outputting more than one bit, we rely on a widely believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves character sum estimates, which may be of independent interest. Using our nonmalleable extractor, we obtain protocols for “privacy amplification": key agreement between two parties who share a weakly random secret. Our protocols work in the presence of an active adversary with unlimited computational power and have asymptotically optimal entropy loss. When the secret has entropy rate greater than $1/2$, the protocol follows from a result of Dodis and Wichs and takes two (or three, for strongest security guarantees) rounds. When the secret has entropy rate $\delta$ for any constant $\delta>0$, our new protocol takes a constant (polynomial in $1/\delta$) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.

A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. A formal security model for PRNGs with input was proposed in 2005 by Barak and Halevi (BH). This model involves an internal state that is refreshed with a (potentially biased) external random source, and a cryptographic function that outputs random numbers from the continually internal state. In this work we extend the BH model to also include a new security property capturing how it should accumulate the entropy of the input data into the internal state after state compromise. This property states that a good PRNG should be able to eventually recover from compromise even if the entropy is injected into the system at a very slow pace, and expresses the real-life expected behavior of existing PRNG designs. Unfortunately, we show that neither the model nor the specific PRNG construction proposed by BH meet this new property, despite meeting a weaker robustness notion introduced by BH. From a practical side, we give a precise assessment of the Linux PRNGs, /dev/random and /dev/urandom. In particular, we show attacks proving that these PRNGs are not robust according to our definition, due to vulnerabilities in their entropy estimator and their internal mixing function. Finally, we propose a simple PRNG construction that is provably robust in our new and stronger adversarial model and we show that it is more efficient than the Linux PRNGs. We therefore recommend to use this construction whenever a PRNG with input is used for cryptography.

Software-based attacks (e.g., malware) pose a big threat to cryptographic software because they can compromise the associated cryptographic keys in their entirety. In this paper, we investigate key-insulated symmetric key cryptography, which can mitigate the damage caused by repeated attacks against cryptographic software. To illustrate the feasibility of key-insulated symmetric key cryptography, we also report a proof-of-concept implementation in the Kernel-based Virtual Machine (KVM) environment.

Recently, there has been renewed interest in basing cryptographic primitives on weak secrets, where the only information about the secret is some non-trivial amount of (min-) entropy. From a formal point of view, such results require to upper bound the expectation of some function f(X), where X is a weak source in question. We show an elementary inequality which essentially upper bounds such `weak expectation' by two terms, the first of which is independent of f, while the second only depends on the `variance' of f under uniform distribution. Quite remarkably, as relatively simple corollaries of this elementary inequality, we obtain some `unexpected' results, in several cases noticeably simplifying/improving prior techniques for the same problem. Examples include non-malleable extractors, leakage-resilient symmetric encryption, seed-dependent condensers and improved entropy loss for the leftover hash lemma.

Abstract We study the price of anarchy of selfish routing with variable traffic rates and when the path cost is a nonadditive function of the edge costs. Nonadditive path costs are important, for example, in networking applications, where a key performance metric is the achievable throughput along a path, which is controlled by its bottleneck (most congested) edge. We prove the following results. In multicommodity networks, the worst‐case price of anarchy under the ℓp path cost with 1 < p ≤∞ can be dramatically larger than under the standard ℓ1 path cost. In single‐commodity networks, the worst‐case price of anarchy under the ℓp path cost with 1 < p < ∞ is no more than with the standard ℓ1 path norm. (A matching lower bound follows trivially from known results.) This upper bound also applies to the ℓ∞ path cost if and only if attention is restricted to the natural subclass of equilibria generated by distributed shortest path routing protocols. For a natural cost‐minimization objective function, the price of anarchy with endogenous traffic rates (and under any ℓp path cost) is no larger than that in fixed‐demand networks. Intuitively, the worst‐case inefficiency arising from the “tragedy of the commons” is no more severe than that from routing inefficiencies. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

Consider two parties holding samples from correlated distributions$W$and$W^{\prime}$, respectively, where these samples are within distance$t$of each other in some metric space. The parties wish to agree on a close-to-uniformly distributed secret key$R$by sending a single message over an insecure channel controlled by an all-powerful adversary who may read and modify anything sent over the channel. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret${\ssr SK}_{\ssr Ext}$that they can use to generate a sequence of session keys$\{R_{j}\}$using multiple pairs$\{(W_{j}, W^{\prime}_{j})\}$. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded-storage model with errors. We show solutions that improve upon previous work in several respects.The best prior solution for the keyless case with no errors (i.e.,$t=0$) requires the min-entropy of$W$to exceed$2n/3$, where$n$is the bit length of$W$. Our solution applies whenever the min-entropy of$W$exceeds the minimal threshold$n/2$, and yields a longer key.

We consider the question of how to store a value secretly on devices that continually leak information about their internal state to an external attacker. If the secret value is stored on a single device from which it is efficiently retrievable, and the attacker can leak even a single predicate of the internal state of that device, then she may learn some information about the secret value itself. Therefore, we consider a setting where the secret value is shared between multiple devices (or multiple components of a single device), each of which continually leaks arbitrary adaptively chosen predicates its individual state. Since leakage is continual, each device must also continually update its state so that an attacker cannot just leak it entirely one bit at a time. In our model, the devices update their state individually and asynchronously, without any communication between them. The update process is necessarily randomized, and its randomness can leak as well. As our main result, we construct a sharing scheme for two devices, where a constant fraction of the internal state of each device can leak in between and during updates. Our scheme has the structure of a public-key encryption, where one share is a secret key and the other is a ciphertext. As a contribution of independent interest, we also get public-key encryption in the continual leakage model, introduced by Brakerski et al. and Dodis et al. (FOCS '10). This scheme tolerates continual leakage on the secret key and the updates, and simplifies the recent construction of Lewko, Lewko and Waters (STOC '11). For our main result, we show how to update the ciphertexts of the encryption scheme so that the message remains hidden even if an attacker interleaves leakage on secret key and ciphertext shares. The security of our scheme is based on the linear assumption in prime-order bilinear groups. We also provide an extension to general access structures realizable by linear secret sharing schemes across many devices. The main advantage of this extension is that the state of some devices can be compromised entirely, while that of the all remaining devices is susceptible to continual leakage. Lastly, we show impossibility of information theoretic sharing schemes in our model, where continually leaky devices update their state individually.

In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable extractor dramatically strengthens the notion of a strong ex- tractor. A strong extractor takes two inputs, a weakly-random x and a uniformly random seed y, and outputs a string which appears uniform, even given y. For a non-malleable extractor nmExt, the output nmExt(x,y) should appear uniform given y as well as nmExt(x, A(y)), where A is an arbitrary function with A(y) ≠ y. We show that an extractor introduced by Chor and Goldreich is non-malleable when the entropy rate is above half. It outputs a linear number of bits when the entropy rate is 1/2 + α, for any α >; 0. Previously, no nontrivial parameters were known for any non-malleable extractor. To achieve a polynomial running time when outputting many bits, we rely on a widely-believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves a character sum estimate, which may be of independent interest. Using our non-malleable extractor, we obtain protocols for "privacy amplification": key agreement between two parties who share a weakly-random secret. Our protocols work in the presence of an active adversary with unlimited computational power, and have asymptotically optimal entropy loss. When the secret has entropy rate greater than 1/2, the protocol fol- lows from a result of Dodis and Wichs, and takes two rounds. When the secret has entropy rate δ for any constant δ >; 0, our new protocol takes a constant (polynomial in 1/δ) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.

We design the first Leakage-Resilient Identity-Based Encryption (LR-IBE) systems from static assumptions in the standard model. We derive these schemes by applying a hash proof technique from Alwen et.al. (Eurocrypt '10) to variants of the existing IBE schemes of Boneh-Boyen, Waters, and Lewko-Waters. As a result, we achieve leakage-resilience under the respective static assumptions of the original systems in the standard model, while also preserving the efficiency of the original schemes. Moreover, our results extend to the Bounded Retrieval Model (BRM), yielding the first regular and identity-based BRM encryption schemes from static assumptions in the standard model.

We say that a cryptographic scheme is Continuous Leakage-Resilient (CLR), if it allows users to refresh their secret keys, using only fresh local randomness, such that: 1. The scheme remains functional after any number of key refreshes, although the public key never changes. Thus, the “outside world'' is neither affected by these key refreshes, nor needs to know about their frequency. 2. The scheme remains secure even if the adversary can continuously leak arbitrary information about the current secret-key, as long as the amount of leaked information is bounded in between any two successive key refreshes. There is no bound on the total amount of information that can be leaked during the lifetime of the system. In this work, we construct a variety of practical CLR schemes, including CLR one-way relations, CLR signatures, CLR identification schemes, and CLR authenticated key agreement protocols. For each of the above, we give general constructions, and then show how to instantiate them efficiently using a well established assumption on bilinear groups, called the K-Linear assumption (for any constant K greater than or equal to 1). Our constructions are highly modular, and we develop many interesting techniques and building-blocks along the way, including: leakage-indistinguishable re-randomizable relations, homomorphic NIZKs, and leakage-of-cipher text non-malleable encryption schemes.

We describe a simple, but powerful local encoding technique, implying two surprising results: 1. We show how to represent a vector of n values from some alphabet S using ceiling(n * log2 |S|) bits, such that reading or writing any entry takes O(1) time. This demonstrates, for instance, an "equivalence" between decimal and binary computers, and has been a central toy problem in the field of succinct data structures. Previous solutions required space of n * log2 |S| + n/logO(1) n bits for constant access. 2. Given a stream of n bits arriving online (for any n, not known in advance), we can output a *prefix-free* encoding that uses n + log2 n + O(loglog n) bits. The encoding and decoding algorithms only require O(log n) bits of memory, and run in constant time per word. This result is interesting in cryptographic applications, as prefix-free codes are the simplest counter-measure to extensions attacks on hash functions, message authentication codes and pseudorandom functions. Our result refutes a conjecture of [Maurer, Sjodin 2005] on the hardness of online prefix-free encodings.

We study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of the secret key is leaked, as long as the secret key sk is still (exponentially) hard to compute from this auxiliary input. This setting of auxiliary input is more general than the more traditional setting, which assumes that some of information about the secret key sk may be leaked, but sk still has high min-entropy left. In particular, we deal with situations where f(sk) information-theoretically determines the entire secret key sk.

We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2<k<

We provide formal definitions and efficient secure techniques for turning noisy information into keys usable for any cryptographic application, and, in particular, reliably and securely authenticating biometric data. Our techniques apply not just to biometric information, but to any keying material that, unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly. We propose two primitives: a fuzzy extractor reliably extracts nearly uniform randomness R from its input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original. Thus, R can be used as a key in a cryptographic application. A secure sketch produces public information about its input w that does not reveal w and yet allows exact recovery of w given another value that is close to w. Thus, it can be used to reliably reproduce error-prone biometric inputs without incurring the security risk inherent in storing them. We define the primitives to be both formally secure and versatile, generalizing much prior work. In addition, we provide nearly optimal constructions of both primitives for various measures of “closeness” of input data, such as Hamming distance, edit distance, and set difference.

This paper explores what kinds of information two parties must communicate in order to correct errors which occur in a shared secret string W. Any bits they communicate must leak a significant amount of information about W --- that is, from the adversary's point of view, the entropy of W will drop significantly. Nevertheless, we construct schemes with which Alice and Bob can prevent an adversary from learning any useful information about W. Specifically, if the entropy of W is sufficiently high, then there is no function f(W) which the adversary can learn from the error-correction information with significant probability.This leads to several new results: (a) the design of noise-tolerant "perfectly one-way" hash functions in the sense of Canetti et al. [7], which in turn leads to obfuscation of proximity queries for high entropy secrets W; (b) private fuzzy extractors [11], which allow one to extract uniformly random bits from noisy and nonuniform data W, while also insuring that no sensitive information about W is leaked; and (c) noise tolerance and stateless key re-use in the Bounded Storage Model, resolving the main open problem of Ding [10].The heart of our constructions is the design of strong randomness extractors with the property that the source W can be recovered from the extracted randomness and any string W' which is close to W.

We propose several highly-practical and optimized constructions for joint signature and encryption primitives often referred to as signcryption. All our signcryption schemes, built directly from trapdoor permutations such as RSA, share features such as simplicity, efficiency, generality, near-optimal exact security, flexible and ad-hoc key management, key reuse for sending/receiving data, optimally-low message expansion, "backward" use for plain signature/encryption, long message and associated data support, the strongest-known qualitative security and, finally, complete compatibility with the PKCS#1 infrastructure.

A forward-secure encryption scheme protects secret keys from exposure by evolving the keys with time. Forward security has several unique requirements in hierarchical identity-based encryption (HIBE) scheme: (1) users join dynamically; (2) encryption is joining-time-oblivious; (3) users evolve secret keys autonomously.We present a scalable forward-secure HIBE (fs-HIBE) scheme satisfying the above properties. We also show how our fs-HIBE scheme can be used to construct a forward-secure public-key broadcast encryption scheme, which protects the secrecy of prior transmissions in the broadcast encryption setting. We further generalize fs-HIBE into a collusion-resistant multiple hierarchical ID-based encryption scheme, which can be used for secure communications with entities having multiple roles in role-based access control. The security of our schemes is based on the bilinear Diffie-Hellman assumption in the random oracle model.

We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) we propose and motivate a definition for quantum broadcast. Our model of quantum broadcast channel is new. (2) We discovered that quantum broadcast is essentially a combination of pairwise quantum channels and a classical broadcast channel. This is a somewhat surprising conclusion, but helps us in both our lower and upper bounds. (3) We provide tight upper and lower bounds on the optimal bias /spl epsiv/ of a coin which can be flipped by k parties of which exactly g parties are honest: for any 1 /spl les/ g /spl les/ k, /spl epsiv/ = 1/2 - /spl Theta/ (g/k). Thus, as long as a constant fraction of the players are honest, they can prevent the coin from being fixed with at least a constant probability. This result stands in sharp contrast with the classical setting, where no non-trivial coin-flipping is possible when g /spl les/ k/2.

We investigate the feasibility of a variety of cryptographic tasks with imperfect randomness. The kind of imperfect randomness we consider are entropy sources, such as those considered by Santha and Vazirani, Chor and Goldreich, and Zuckerman. We show the following: (1) certain cryptographic tasks like bit commitment, encryption, secret sharing, zero-knowledge, non-interactive zero-knowledge, and secure two-party computation for any non-trivial junction are impossible to realize if parties have access to entropy sources with slightly less-than-perfect entropy, i.e., sources with imperfect randomness. These results are unconditional and do not rely on any un-proven assumption. (2) On the other hand, based on stronger variants of standard assumptions, secure signature schemes are possible with imperfect entropy sources. As another positive result, we show (without any unproven assumption) that interactive proofs can be made sound with respect to imperfect entropy sources.

In PODC 2003, Park, Chong, Siegel and Ray [22] proposed an optimistic protocol for fair exchange, based on RSA signatures. We show that their protocol is totally breakable already in the registration phase: the honest-but-curious arbitrator can easily determine the signer's secret key.On a positive note, the authors of [22] informally introduced a connection between fair exchange and "sequential two-party multisignature schemes" (which we call two-signatures), but used an insecure two-signature scheme in their actual construction. Nonetheless, we show that this connection can be properly formalized to imply provably secure fair exchange protocols. By utilizing the state-of-the-art non-interactive two-signature of Boldyreva [6], we obtain an efficient and provably secure (in the random oracle model) fair exchange protocol, which is based on GDH signatures [9].Of independent interest, we introduce a unified model for non-interactive fair exchange protocols, which results in a new primitive we call verifiably committed signatures. Verifiably committed signatures generalize (non-interactive) verifiably encrypted signatures [8] and two-signatures, both of which are sufficient for fair exchange.

Traitor Tracing Schemes constitute a very useful tool against piracy in the context of digital content broadcast. In such multi-recipient encryption schemes, each decryption key is fingerprinted and when a pirate decoder is discovered, the authorities can trace the identities of the users that contributed in its construction (called traitors). Public-key traitor tracing schemes allow for a multitude of non trusted content providers using the same set of keys, which makes the scheme "server-side scalable." To make such schemes also "client-side scalable," i.e. long lived and usable for a large population of subscribers that changes dynamically over time, it is crucial to implement efficient Add-user and Remove-user operations. Previous work on public-key traitor tracing did not address this dynamic scenario thoroughly, and there is no efficient scalable public key traitor tracing scheme that allows an increasing number of Add-user and Remove-user operations.To address these issues, we introduce the model of Scalable Public-Key Traitor Tracing, and present the first construction of such a scheme. Our model mandates for deterministic traitor tracing and an unlimited number of efficient Add-user operations and Remove-user operations. A scalable system achieves an unlimited number of revocations while retaining high level of efficiency by dividing the run-time of the system into periods. Each period has a saturation level for the number of revocations. When a period becomes saturated, an efficient new-period operation is issued by the system server that resets the saturation level. We present a formal adversarial model for our system taking into account its periodic structure, and we prove our construction secure, both against adversaries that attempt to cheat the revocation mechanism as well as against adversaries that attempt to cheat the traitor tracing mechanism.

We study economic incentives for influencing selfish behavior in networks. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to selfishly route traffic on minimum-latency paths. The quality of a routing of traffic is historically measured by the sum of all travel times, also called the total latency.It is well known that the outcome of selfish routing (a Nash equilibrium) does not minimize the total latency and can be improved upon with coordination, and that marginal cost pricing---charging each network user for the congestion effects caused by its presence---eliminates the inefficiency of selfish routing. However, the principle of marginal cost pricing assumes that (possibly very large) taxes cause no disutility to network users; this is appropriate only when collected taxes can be feasibly returned (directly or indirectly) to the users, for example via a lump-sum refund. If this assumption does not hold and we wish to minimize the total user disutility (latency plus taxes paid)---the total cost---how should we price the network edges? Intuition may suggest that taxes should never be able to improve the cost of a Nash equilibrium, but the famous Braess's Paradox shows this intuition to be incorrect.We consider strategies for pricing network edges to reduce the cost of a Nash equilibrium. Since levying a sufficiently large tax on an edge effectively removes it from the network, our study generalizes previous work on network design citend_hard. In this paper, we prove the following results.

We study the negative consequences of selfish behavior in a congested network and economic means of influencing such behavior. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to selfishly route traffic on minimum-latency paths. The quality of a routing of traffic is measured by the sum of travel times (the total latency).It is well known that the outcome of selfish routing (a Nash equilibrium) does not minimize the total latency. An ancient strategy for improving the selfish solution is the principle of marginal cost pricing, which asserts that on each edge of the network, each network user on the edge should pay a tax offsetting the congestion effects caused by its presence. By pricing network edges according to this principle, the inefficiency of selfish routing can always be eradicated.This result, while fundamental, assumes a very strong homogeneity property: all network users are assumed to trade off time and money in an identical way. The guarantee also ignores both the algorithmic aspects of edge pricing and the unfortunate possibility that an efficient routing of traffic might only be achieved with exorbitant taxes. Motivated by these shortcomings, we extend this classical work on edge pricing in several different directions and prove the following results.We prove that the edges of a single-commodity network can always be priced so that an optimal routing of traffic arises as a Nash equilibrium, even for very general heterogeneous populations of network users.When there are only finitely many different types of network users and all edge latency functions are convex, we show how to compute such edge prices efficiently.We prove that an easy-to-check mathematical condition on the population of heterogeneous network users is both necessary and sufficient for the existence of edge prices that induce an optimal routing while requiring only moderate taxes.

Randomization is vital in cryptography: secret keys should be randomly generated and most cryptographic primitives (e.g., encryption) must be probabilistic. We initiate the quantitative study concerning feasibility of building secure cryptographic primitives using imperfect random sources. Specifically, we concentrate on symmetric-key encryption and message authentication, where the shared secret key comes from an imperfect random source instead of being assumed truly random. In each case, we compare the class of "cryptographic" sources for the task at hand with the classes of "extractable" and "simulatable" sources, where: (1) "cryptographic" refers to sources for which the corresponding symmetric-key primitive can be built; (2) "extractable" refers to a very narrow class of sources from which one can extract nearly perfect randomness; and (3) "simulatable" refers to a very general class of weak random sources which are known to suffice for BPP simulation. For both encryption and authentication, we show that the corresponding cryptographic sources lie strictly in between extractable and simulatable sources, which implies that "cryptographic usage" of randomness is more demanding than the corresponding "algorithmic usage", but still does not require perfect randomness. Interestingly, cryptographic sources for encryption and authentication are also quite different from each other, which suggests that there might not be an elegant way to describe imperfect sources sufficient for "general cryptographic use". We believe that our initial investigation in this new area will inspire a lot of further research.

We study the following network design problem: Given a communication network, find a minimum cost subset of missing links such that adding these links to the network makes every pair of points within distance at most d from each other.The problem has been studied earlier [17] under the assumption that all link costs as well as link lengths are identical, and was shown to be R(logn)-hard for every d 2 4.We present a novel linear programming based approach to obtain an O(log la log d) approximation algorithm for the case of uniform link lengths and costs.We also extend the Cl(Iogn) hardness to d E {Z, 3).On the other hand, if link costs can vary, we show that the prob-" '-' n lem is n(Z s )-hard for d > 3.This version of our problem can be viewed as a special case of the minimum cost d-spanner problem and thus our hardness result applies there as well.For d = 2, however, we show that the problem continues to be O(logn) approximable by giving an O(log n)-approximation to the more general minimum cost Z-spanner problem.An n(2"s'-' ")-hardness result also holds when all link costs are identical but link lengths may vary (applies even when all lengths are 1 or 2).Our reduction from the label cower problem [3] also applies to another well-studied network design problem.We show that the directed genemlized steiner network problem [6] is n(2 I'&-' ")-hard, significantly improving upon the Q(logn) hardness known prior to our work.We also present O(n log d) approximation algorithm for our problem under arbitrary link costs and polynomially bounded link lengths.Same result holds for the minimum cost d-spanner problem.Finally, all our positive results extend to the case where each pair (u,u) of nodes has a distinct distance requirement, say d(u, v).The approximation guarantees above hold provided d is replaced by max,,, d(u, v).All our algorithmic as well as hardness results hold for both undirected and directed versions of the problem.