A powerful feature in mechanism design is the ability to irrevocably commit to the rules of a mechanism. Commitment is achieved by public declaration, which enables players to verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that the mechanism designer might prefer not to disclose, such as her target function or private costs. Avoiding this may be possible via a trusted mediator; however, the availability of a trustworthy mediator, especially if mechanism secrecy must be maintained for years, might be unrealistic. We propose a new approach to commitment, and show how to commit to, and run, any given mechanism without disclosing it, while enabling the verification of incentive properties and the outcome—all without the need for any mediators. Our framework is based on zero-knowledge proofs—a cornerstone of modern cryptographic theory. Applications include both private-type settings such as auctions and private-action settings such as contracts, as well as non-mediated bargaining with hidden yet binding offers.

In February 2024, Israel's Ministry of Health released microdata of live births in Israel in 2014. The dataset is based on Israel's National Registry of Live Births and offers substantial value in multiple areas, such as scientific research and policy-making, while providing pure differential privacy guarantee with ε = 9.98 for 2014's mothers and newborns. The release was co-designed by the authors along with stakeholders from both inside and outside the Ministry of Health. This paper presents the methodology used to obtain that release, which, to the best of our knowledge, is the first of its kind in the world. The design process has been challenging and required flexibility and open-mindedness on all sides involved, along with substantial technical innovation. In particular, we introduce new concepts regarding the desiderata from dataset releases in a microdata format, as well as a way to bundle together multiple quantitative desiderata for a differentially private release using the private selection algorithm of Liu and Talwar (STOC 2019). We hope that the experiences reported here will be useful to future differentially private releases.

Society appears to be on the verge of recognizing the need for control over sensitive data in modern web applications. Recently, many systems claim to give control to individuals, promising the preeminent goal of data sovereignty. However, despite recent attention, research and industry efforts are fragmented and lack a holistic system overview. In this paper, we provide the first transecting systematization of data sovereignty by drawing from a dispersed body of knowledge. We clarify the field by identifying its three main areas: (i) decentralized identity, (ii) decentralized access control and (iii) policy-compliant decentralized computation. We find that literature lacks a cohesive set of formal definitions. Each area is considered in isolation, and priorities in industry and academia are not aligned due to a lack of clarity regarding user control. To solve this issue, we propose formal definitions for each sub-area. By highlighting that data sovereignty transcends the domain of decentralized identity, we aim to guide future works to embrace a broader perspective on user control. In each section, we augment our definition with security and privacy properties, discuss the state of the art and proceed to identify open challenges. We conclude by highlighting synergies between areas, emphasizing the real-world benefit obtained by further developing data sovereign systems.

In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.

Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds? We answer this question in the affirmative. We define a new type of symmetric encryption, called functionally equivocal encryption (FEE), and show that when Yao's scheme is implemented with FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one-way function. Combining our scheme with noncommitting encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. Using standard techniques, this protocol can be made standalone secure against malicious corruptions in the plain model and universal composability secure in the common random string model. Additional applications include the first fully leakage-tolerant general multiparty computation protocol (with preprocessing), as well as a public-key version of FEE which can serve as a replacement for noncommitting encryption with better efficiency than what is possible for the latter.

Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS '18), we present two threshold ECDSA protocols, for any number of signatories and any threshold, that improve as follows over the state of the art: -- For both protocols, only the last round requires knowledge of the message, and the other rounds can take place in a preprocessing stage, lending to a non-interactive threshold ECDSA protocol. -- Both protocols withstand adaptive corruption of signatories. Furthermore, they include a periodic refresh mechanism and offer full proactive security. -- Both protocols realize an ideal threshold signature functionality within the UC framework, in the global random oracle model, assuming Strong RSA, DDH, semantic security of the Paillier encryption, and a somewhat enhanced variant of existential unforgeability of ECDSA. -- Both protocols achieve accountability by identifying corrupted parties in case of failure to generate a valid signature. The two protocols are distinguished by the round-complexity and the identification process for detecting cheating parties. Namely: -- For the first protocol, signature generation takes only 4 rounds (down from the current state of the art of 8 rounds), but the identification process requires computation and communication that is quadratic in the number of parties. -- For the second protocol, the identification process requires computation and communication that is only linear in the number of parties, but signature generation takes 7 rounds. These properties (low latency, compatibility with cold-wallet architectures, proactive security, identifiable abort and composable security) make the two protocols ideal for threshold wallets for ECDSA-based cryptocurrencies.

Modern hardware typically is characterized by a multitude of interacting physical components and software mechanisms. To address this complexity, security analysis should be modular: We would like to formulate and prove security properties of individual components, and then deduce the security of the overall design (encompassing hardware and software) from the security of the components. While this seems like an elusive goal, we argue that this is essentially the only feasible way to provide rigorous security analysis of modern hardware.This paper investigates the possibility of using the Universally Composable (UC) security framework towards this aim. The UC framework has been devised and successfully used in the theoretical cryptography community to study and formally prove security of arbitrarily interleaving cryptographic protocols. In particular, a sophisticated analytical toolbox has been developed using this framework. We provide an introduction to this frame-work, and investigate, via a number of examples, ways by which this framework can be used to facilitate a novel type of modular security analysis. This analysis applies to combined hardware and software systems, and investigates their security against attacks that combine both physical and digital steps.

This work presents a general framework for describing cryptographic protocols and analyzing their security. The framework allows specifying the security requirements of practically any cryptographic task in a unified and systematic way. Furthermore, in this framework the security of protocols is preserved under a general composition operation, called universal composition. The proposed framework with its security-preserving composition operation allows for modular design and analysis of complex cryptographic protocols from simpler building blocks. Moreover, within this framework, protocols are guaranteed to maintain their security in any context, even in the presence of an unbounded number of arbitrary protocol sessions that run concurrently in an adversarially controlled manner. This is a useful guarantee, which allows arguing about the security of cryptographic protocols in complex and unpredictable environments such as modern communication networks.

We present a methodology for using the EasyCrypt proof assistant (originally designed for mechanizing the generation of proofs of game-based security of cryptographic schemes and protocols) to mechanize proofs of security of cryptographic protocols within the universally composable (UC) security framework. This allows, for the first time, the mechanization and formal verification of the entire sequence of steps needed for proving simulation-based security in a modular way: Specifying a protocol and the desired ideal functionality; Constructing a simulator and demonstrating its validity, via reduction to hard computational problems; Invoking the universal composition operation and demonstrating that it indeed preserves security. We demonstrate our methodology on a simple example: stating and proving the security of secure message communication via a one-time pad, where the key comes from a Diffie-Hellman key-exchange, assuming ideally authenticated communication. We first put together EasyCrypt-verified proofs that: (a) the Diffie-Hellman protocol UC-realizes an ideal key-exchange functionality, assuming hardness of the Decisional Diffie-Hellman problem, and (b) one-time-pad encryption, with a key obtained using ideal key-exchange, UC-realizes an ideal secure-communication functionality. We then mechanically combine the two proofs into an EasyCrypt-verified proof that the composed protocol realizes the same ideal secure-communication functionality. Although formulating a methodology that is both sound and workable has proven to be a complex task, we are hopeful that it will prove to be the basis for mechanized UC security analyses for significantly more complex protocols and tasks.

We give new instantiations of the Fiat-Shamir transform using explicit, efficiently computable hash functions. We improve over prior work by reducing the security of these protocols to qualitatively simpler and weaker computational hardness assumptions. As a consequence of our framework, we obtain the following concrete results.

We show how to construct indistinguishability obfuscation (\bf iO) for RAM programs with bounded space, assuming \bf iO for circuits and one-way functions, both with subexponential security. That is, given a RAM program whose computation requires space $s(n)$ in the worst case for inputs of length at most $n$, we generate an obfuscated RAM program that, for inputs of size at most $n$, runs in roughly the same time as the original program, using space roughly $s(n)$. The obfuscation process is quasi-linear in the description length of the input program and $s(n)$. At the heart of our construction are succinct randomized encodings for RAM programs. We present two very different constructions of such encodings, each with its own unique properties. Beyond their use as a tool in obfuscation for RAM programs, we show that succinct randomized encodings are interesting objects in their own right. We demonstrate the power of succinct randomized encodings in applications such as publicly verifiable delegation, functional encryption for RAMs, and key-dependent security amplification.

The security of almost any real-world distributed system today depends on the participants having some "reasonably accurate" sense of current real time. Indeed, to name one example, the very authenticity of practically any communication on the Internet today hinges on the ability of the parties to accurately detect revocation of certificates, or expiration of passwords or shared keys.,,However, as recent attacks show, the standard protocols for determining time are subvertible, resulting in wide-spread security loss. Worse yet, we do not have security notions for network time protocols that (a) can be rigorously asserted, and (b) rigorously guarantee security of applications that require a sense of real time.,,We propose such notions, within the universally composable (UC) security framework. That is, we formulate ideal functionalities that capture a number of prevalent forms of time measurement within existing systems. We show how they can be realized by real-world protocols, and how they can be used to assert security of time-reliant applications — specifically, certificates with revocation and expiration times. This allows for relatively clear and modular treatment of the use of time consensus in security-sensitive systems.,,Our modeling and analysis are done within the existing UC framework, in spite of its asynchronous, event-driven nature. This allows incorporating the use of real time within the existing body of analytical work done in this framework. In particular it allows for rigorous incorporation of real time within cryptographic tools and primitives.

Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?

We construct the first fully succinct garbling scheme for RAM programs, assuming the existence of indistinguishability obfuscation for circuits and one-way functions. That is, the size, space requirements, and runtime of the garbled program are the same as those of the input program, up to poly-logarithmic factors and a polynomial in the security parameter. The scheme can be used to construct indistinguishability obfuscators for RAM programs with comparable efficiency, at the price of requiring sub-exponential security of the underlying primitives.

A function $f$ is extractable if it is possible to algorithmically “extract,” from any adversarial program that outputs a value $y$ in the image of $f$, a preimage of $y$. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a nonstandard knowledge assumption on certain functions. We make headway in the study of the existence of extractable one-way functions (EOWFs) along two directions. On the negative side, we show that if there exist indistinguishability obfuscators for circuits, then there do not exist EOWFs where extraction works for any adversarial program with auxiliary input of unbounded polynomial length. On the positive side, for adversarial programs with bounded auxiliary input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (such as subexponential hardness of learning with errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zero-knowledge arguments of knowledge, against verifiers in the same class of adversarial programs, from essentially the same assumptions.

We construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition---assuming only the existence of enhanced trapdoor permutations. The notion of security fits within a generalization of the “angel-based” framework of Prabhakaran and Sahai [STOC'04, ACM, New York, 2004, pp. 242--251] and implies superpolynomial-time simulation security. Security notions of this kind are currently known to be realizable only under strong and specific hardness assumptions. A key element in our construction is a commitment scheme that satisfies a new and strong notion of security. The notion, security against chosen-commitment attacks (CCA security), means that security holds even if the attacker has access to an extraction oracle that gives the adversary decommitment information to commitments of the adversary's choice. This notion is stronger than concurrent nonmalleability and is of independent interest. We construct CCA-secure commitments based on standard one-way functions, and with no trusted setup. To the best of our knowledge, this provides the first construction of a natural cryptographic primitive having adaptive hardness from standard hardness assumptions, using no trusted setup or public keys.

Order-preserving encryption (OPE) schemes, whose ciphertexts preserve the natural ordering of the plaintexts, allow efficient range query processing over outsourced encrypted databases without giving the server access to the decryption key. Such schemes have recently received increased interest in both the database and the cryptographic communities. In particular, modular order-preserving encryption (MOPE), due to Boldyreva et al., is a promising extension that increases the security of the basic OPE by introducing a secret modular offset to each data value prior to encrypting it. However, executing range queries via MOPE in a naive way allows the adversary to learn this offset, negating any potential security gains of this approach.

We show how to construct succinct Indistinguishability Obfuscation (IO) schemes for RAM programs. That is, given a RAM program whose computation requires space S and time T, we generate a RAM program with size and space requirements of ~O(S) and runtime ~O(T). The construction uses non-succinct IO (i.e., IO for circuits) and injective one way functions, both with sub-exponential security. A main component in our scheme is a succinct garbling scheme for RAM programs. Our garbling scheme has the same size, space and runtime parameters as above, and requires only polynomial security of the underlying primitives. This scheme has other qualitatively new applications such as publicly verifiable succinct non-interactive delegation of computation and succinct functional encryption.

Contrary to prior belief, we show that there exist commitment, zero-knowledge and general function evaluation protocols with universally composable security, in a model where all parties and all protocols have access to a single, global, random oracle and no other trusted setup. This model provides significantly stronger composable security guarantees than the traditional random oracle model of Bellare and Rogaway [CCS'93] or even the common reference string model. Indeed, these latter models provide no security guarantees in the presence of arbitrary protocols that use the {\em same} random oracle (or reference string or hash function).

A function f is extractable if it is possible to algorithmically "extract," from any adversarial program that outputs a value y in the image of f; a preimage of y. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions.

An important security concern for crypto-graphic protocols is the extent to which they adversely affect the security of the systems in which they run. In particular, can we rule out the possibility that introducing a new protocol to a system might, as a "side effect", break the security of unsuspecting protocols in that system? Universally Composable (UC) security rules out such adverse side effects. However, many functionalities of interest provably cannot be realized with UC security unless the protocol participants are willing to put some trust in external computational entities. We propose a notion of security that: (a) allows realizing practically any functionality by protocols in the plain model without putting trust in any external entity; (b) guarantees that secure protocols according to this notion have no adverse side-effects on existing protocols in the system -- as long as the security of these existing protocols is proven via the traditional methodology of black box reduction to a game-based cryptographic hardness assumption with bounded number of rounds. Our security notion builds on the angel-based security notion of Prabhakaran and Sahai. A key part in our analysis is to come up with a CCA-secure commitment scheme that (a) cannot be proven secure via a black box reduction to a game-based assumption, but (b) can be proven secure using a non-black-box reduction. To the best of our knowledge, this is the first time that the interplay between black-box provability and unprovability is used to demonstrate security properties of protocols.

Succinct non-interactive arguments of knowledge (SNARKs) enable verifying NP statements with complexity that is essentially independent of that required for classical NP verification. In particular, they provide strong solutions to the problem of verifiably delegating computation. We construct the first fully-succinct publicly-verifiable SNARK. To do that, we first show how to "bootstrap" any SNARK that requires expensive preprocessing to obtain a SNARK that does not, while preserving public verifiability. We then apply this transformation to known SNARKs with preprocessing. Moreover, the SNARK we construct only requires of the prover time and space that are essentially the same as that required for classical NP verification. Our transformation assumes only collision-resistant hashing; curiously, it does not rely on PCPs. We also show an analogous transformation for privately-verifiable SNARKs, assuming fully-homomorphic encryption.

The existence of succinct non-interactive arguments for NP (i.e., non-interactive computationally-sound proofs where the verifier's work is essentially independent of the complexity of the NP nondeterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model [Micali, FOCS '94], the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol [Di Crescenzo and Lipmaa, CiE '08].

The current move to Cloud Computing raises the need for verifiable delegation of computations, where a weak client delegates his computation to a powerful server, while maintaining the ability to verify that the result is correct. Although there are prior solutions to this problem, none of them is yet both general and practical for real-world use. We demonstrate a relatively efficient and general solution where the client delegates the computation to several servers, and is guaranteed to determine the correct answer as long as even a single server is honest. We show: A protocol for any efficiently computable function, with logarithmically many rounds, based on any collision-resistant hash family. The protocol is set in terms of Turing Machines but can be adapted to other computation models. An adaptation of the protocol for the X86 computation model and a prototype implementation, called Quin, for Windows executables. We describe the architecture of Quin and experiment with several parameters on live clouds. We show that the protocol is practical, can work with nowadays clouds, and is efficient both for the servers and for the client.

We construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition- assuming only the existence of enhanced trapdoor permutations. The notion of security fits within a generalization of the "angelbased" framework of Prabhakaran and Sahai (STOC'04) and implies super-polynomial time simulation security. Security notions of this kind are currently known to be realizable only under strong and specific hardness assumptions. A key element in our construction is a commitment scheme that satisfies a new and strong notion of security. The notion, security against chosen-commitment-attacks (CCA security), means that security holds even if the attacker has access to a extraction oracle that gives the adversary decommitment information to commitments of the adversary's choice. This notion is stronger than concurrent non-malleability and is of independent interest. We construct CCA-secure commitments based on standard one-way functions, and with no trusted set-up. To the best of our knowledge, this provides the first construction of a natural cryptographic primitive requiring adaptive hardness from standard hardness assumptions, using no trusted set-up or public keys.

In a proxy re-encryption (PRE) scheme, a proxy is given special information that allows it to translate a ciphertext under one key into a ciphertext of the same message under a different key. The proxy cannot, however, learn anything about the messages encrypted under either key. PRE schemes have many practical applications, including distributed storage, email, and DRM. Previously proposed re-encryption schemes achieved only semantic security; in contrast, applications often require security against chosen ciphertext attacks. We propose a definition of security against chosen ciphertext attacks for PRE schemes, and present a scheme that satisfies the definition. Our construction is efficient and based only on the Decisional Bilinear Diffie-Hellman assumption in the standard model. We also formally capture CCA security for PRE schemes via both a game-based definition and simulation-based definitions that guarantee universally composable security. We note that, simultaneously with our work, Green and Ateniese proposed a CCA-secure PRE, discussed herein.

Task-PIOA is a modeling framework for distributed systems with both probabilistic and nondeterministic behaviors. It is suitable for cryptographic applications because its task-based scheduling mechanism is less powerful than the traditional perfect-information scheduler. Moreover, one can speak of two types of complexity restrictions: time bounds on description of task-PIOAs and time bounds on length of schedules. This distinction, along with the flexibility of nondeterministic specifications, are interesting departures from existing formal frameworks for computational security. The current paper presents a new approximate implementation relation for task-PIOAs. This relation is transitive and is preserved under hiding of external actions. Also, it is shown to be preserved under concurrent composition, with any polynomial number of substitutions. Building upon this foundation, we present the notion of structures, which classifies communications into two categories: those with a distinguisher environment and those with an adversary. We then formulate secure emulation in the spirit of traditional simulation-based security, and a composition theorem follows as a corollary of the composition theorem for the new approximate implementation relation.

The common reference string (CRS) model equips all protocol participants with a common string that is sampled from a pre-specified distribution, say the uniform distribution. This model enables otherwise-impossible cryptographic goals such as removing interaction from protocols and guaranteeing composable security. However, knowing the precise distribution of the reference string seems crucial for all known protocols in this model, in the sense that current security analyses fail when the actual distribution of the reference string is allowed to differ from the specified one even by a small amount. This fact rules out many potential implementations of the CRS model, such as measurements of physical phenomena (like sunspots), or alternatively using random sources that might be adversarially influenced. We study the possibility of obtaining universally composable (UC) security in a relaxed variant of the CRS model, where the reference string it taken from an adversarially specified distribution that's unknown to the protocol. On the positive side, we demonstrate that UC general secure computation is obtainable even when the reference string is taken from an arbitrary, adversarially chosen distribution, as long as (a) this distribution has some minimal min-entropy, (b) it has not too long a description, (c) it is efficiently samplable, and (d) the sampling algorithm is known to the adversary (and simulator). On the negative side, we show that if any one of these four conditions is removed then genera! UC secure computation becomes essentially impossible.

We propose simple and efficient CCA‐secure public‐key encryption schemes (i.e., schemes secure against adaptive chosen‐ciphertext attacks) based on any identity‐based encryption (IBE) scheme. Our constructions have ramifications of both theoretical and practical interest. First, our schemes give a new paradigm for achieving CCA‐security; this paradigm avoids “proofs of well‐formedness” that have been shown to underlie previous constructions. Second, instantiating our construction using known IBE constructions we obtain CCA‐secure encryption schemes whose performance is competitive with the most efficient CCA‐secure schemes to date. Our techniques extend naturally to give an efficient method for securing IBE schemes (even hierarchical ones) against adaptive chosen‐ciphertext attacks. Coupled with previous work, this gives the first efficient constructions of CCA‐secure IBE schemes.

A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally composable (UC) protocols provide this guarantee in a strong sense: A protocol remains secure even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, UC protocols for carrying out general tasks are known to exist only if a majority of the participants are honest, or in the common reference string (CRS) model where all parties are assumed to have access to a common string that is drawn from some pre-defined distribution. Furthermore, carrying out many interesting tasks in a UC manner and without honest majority or set-up assumptions is impossible, even if ideally authenticated communication is provided. A natural question is thus whether there exist more relaxed set-up assumptions than the CRS model that still allow for UC protocols. We answer this question in the affirmative: we propose alternative and relaxed set-up assumptions and show that they suffice for reproducing the general feasibility results for UC protocols in the CRS model. These alternative assumptions have the flavor of a "public-key infrastructure": parties have registered public keys, no single registration authority needs to be fully trusted, and no single piece of information has to be globally trusted and available. In addition, unlike known protocols in the CRS model, the proposed protocols guarantee some basic level of security even if the set-up assumption is violated.

We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called "cryptographic hash functions".The main result of this article is a negative one: There exist signature and encryption schemes that are secure in the Random Oracle Model, but for which any implementation of the random oracle results in insecure schemes. In the process of devising the above schemes, we consider possible definitions for the notion of a "good implementation" of a random oracle, pointing out limitations and challenges.

We describe Just Fast Keying (JFK), a new key-exchange protocol, primarily designed for use in the IP security architecture. It is simple, efficient, and secure; we sketch a proof of the latter property. JFK also has a number of novel engineering parameters that permit a variety of tradeoffs, most notably the ability to balance the need for perfect forward secrecy against susceptibility to denial-of-service attacks.

We describe JFK, a new key exchange protocol, primarily designed for use in the IP Security Architecture. It is simple, efficient, and secure; we sketch a proof of the latter property. JFK also has a number of novel engineering parameters that permit a variety of trade-offs, most notably the ability to balance the need for perfect forward secrecy against susceptibility to denial-of-service attacks.

We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and make general intractability assumptions.

We show that any concurrent zero-knowledge protocol for a nontrivial language (i.e., for a language outside ${\cal BPP}$), whose security is proven via black-box simulation, must use at least $\tilde\Omega(\log n)$ rounds of interaction. This result achieves a substantial improvement over previous lower bounds and is the first bound to rule out the possibility of constant-round concurrent zero-knowledge when proven via black-box simulation. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in ${\cal NP}$ (which is established via black-box simulation).

We propose a novel paradigm for defining security of cryptographic protocols, called universally composable security. The salient property of universally composable definitions of security is that they guarantee security even when a secure protocol is composed of an arbitrary set of protocols, or more generally when the protocol is used as a component of an arbitrary system. This is an essential property for maintaining security of cryptographic protocols in complex and unpredictable environments such as the Internet. In particular, universally composable definitions guarantee security even when an unbounded number of protocol instances are executed concurrently in an adversarially controlled manner, they guarantee non-malleability with respect to arbitrary protocols, and more. We show how to formulate universally composable definitions of security for practically any cryptographic task. Furthermore, we demonstrate that practically any such definition can be realized using known techniques, as long as only a minority of the participants are corrupted. We then proceed to formulate universally composable definitions of a wide array of cryptographic tasks, including authenticated and secure communication, key-exchange, public-key encryption, signature, commitment, oblivious transfer, zero knowledge and more. We also make initial steps towards studying the realizability of the proposed definitions in various settings.

Motivated by the application of private statistical analysis of large databases, we consider the problem of selective private function evaluation (SPFE). In this problem, a client inter-acts with one or more servers holding copies of a database z = zt,...,z, in order to compute f(z~t,...,z~,,,) , for some function f and indices i = it,...,i, ~ chosen by the client. Ideally, the client must learn nothing more about the database than f(zit,..., zi,,~), and the servers should learn nothing. Generic solutions for this problem, based on standard techniques for secure function evaluation, incur communi-cation complexity that is at least linear in n, making them prohibitive for large databases even when f is relatively sim-ple and m is small. We present various approaches for con-structing sublinear-communication $PFE protocols, both for the general problem and for special cases of interest. Our so-lutions not only offer sublinear communication complexity, but are also practical in many scenarios. 1.

We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside $\BPP$), whose security is proven via black-box simulation, must use at least \tildeΩ(log n) rounds of interaction. This result substantially improves over previous lower bounds, and is the first bound to rule out the possibility of constant-round black-box concurrent zero-knowledge. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in ~$\NP$.

Multicast stream authentication and signing is an important and challenging problem. Applications include the continuous authentication of radio and TV Internet broadcasts, and authenticated data distribution by satellite. The main challenges are fourfold. First, authenticity must be guaranteed even when only the sender of the data is trusted. Second, the scheme needs to scale to potentially millions of receivers. Third, streamed media distribution can have high packet loss. Finally the system needs to be efficient to support fast packet rates. We propose two efficient schemes, TESLA and EMSS, for secure lossy multicast streams. TESLA (Timed Efficient Stream Loss-tolerant Authentication), offers sender authentication, strong loss robustness, high scalability and minimal overhead at the cost of loose initial time synchronization and slightly delayed authentication. EMSS (Efficient Multi-chained Stream Signature), provides nonrepudiation of origin, high loss resistance, and low overhead, at the cost of slightly delayed verification.

We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge.In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape.All known examples of zero-knowledge proofs and arguments are trivially breakable in this setting.Moreover, by definition, all zero-knowledge proofs of knowledge are breakable in this setting.Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct: • Resettable Zero-Knowledge proof-systems for NP with non-constant number of rounds.* Five-round Resettable Witness-Indistinguishable proofsystems for NP. e Four-round Resettabie Zero-Knowledge arguments for NP in the public key model: where verifiers have fixed, public keys associated with them.In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications.Firstly, rZK protocols are closed under parallel and concurrent execution and thus are guaranteed to be secure when implemented in fully asynchronous networks, even if an adversary schedules the arrival of every message sent so as to foil security.Secondly, rZK protocols enlarge the range of physical ways in which provers of ZK protocols can be securely implemented, including devices which cannot reliably toss coins on line, nor keep state *A subset of this work is included in patent application [21].

Multicast communication is becoming the basis for a growing number of applications. It is therefore critical to provide sound security mechanisms for multicast communication. Yet, existing security protocols for multicast offer only partial solutions. We first present a taxonomy of multicast scenarios on the Internet and point out relevant security concerns. Next we address two major security problems of multicast communication: source authentication, and key revocation. Maintaining authenticity in multicast protocols is a much more complex problem than for unicast; in particular, known solutions are prohibitively inefficient in many cases. We present a solution that is reasonable for a range of scenarios. This approach can be regarded as a 'midpoint' between traditional message authentication codes and digital signatures. We also present an improved solution to the key revocation problem.

Article Free Access Share on Secure computation with honest-looking parties (extended abstract): what if nobody is truly honest? Authors: Ran Canetti IBM T.J. Watson Research Center IBM T.J. Watson Research CenterView Profile , Rafail Ostrovsky Bell Communications Research, MCC-1C365B, 445 South Street, Morristown, New Jersey Bell Communications Research, MCC-1C365B, 445 South Street, Morristown, New JerseyView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999Pages 255–264https://doi.org/10.1145/301250.301313Published:01 May 1999Publication History 15citation383DownloadsMetricsTotal Citations15Total Downloads383Last 12 Months19Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensified when the overall requested bandwidth exceeds the capacity and not all requests can be served. Furthermore, acceptance/rejection decisions regarding connections have to be made online, without knowledge of future requests. We show that the ability to preempt (i.e., abort) connections while in service in order to schedule "more valuable" connections substantially improves the throughput of some networks. We present bandwidth allocation strategies that use preemption and show that they achieve constant competitiveness with respect to the throughput, given that any single call requests at most a constant fraction of the bandwidth. Our results should be contrasted with recent works showing that nonpreemptive strategies have at most inverse logarithmic competitiveness.

We prcscnt a general framework for constructing and analyzing authentication protocols in realistic models of communication networks.This framework provides a sound formalization for the authentication problem and suggests simple and attractive design principles for general authentication and key exchange protocols.The key element in our appronch io a modular treatment of the authentication problem in cryptographic protocols; thii applies to the definition of accurity, to the design of the protocols, and to their analysis.In particulnr, following this modular approach, we show how to systematically transform solutions that work in a model of idaalizcd authenticated communications into solutions that are secure in the realistic setting of communication channels controlled by an active adversary.Using these principles we construct and prove the security of simple and practical authentication and key-exchange protocols.In particular, we provide a security analysis of aomo well-known key exchange protocols (e.g.authenticated Dlfllc-Hcllman key exchange), and of some of the techniques underlying the design of several authentication protocols that are currently being deployed on a large scale for the Intornot Protocol and other applications.

Article The random oracle methodology, revisited (preliminary version) Share on Authors: Ran Canetti IBM Watson, P.O. Box 704, Yorktown Heights, NY IBM Watson, P.O. Box 704, Yorktown Heights, NYView Profile , Oded Goldreich Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel Department of Computer Science, Weizmann Institute of Science, Rehovot, IsraelView Profile , Shai Halevi IBM Watson, P.O. Box 704, Yorktown Heights, NY IBM Watson, P.O. Box 704, Yorktown Heights, NYView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 209–218https://doi.org/10.1145/276698.276741Online:23 May 1998Publication History 403citation694DownloadsMetricsTotal Citations403Total Downloads694Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Probabilistic hash functions that hide all partial information on their input were recently introduced. This new cryptographic primitive can be regarded as a function that offers "perfect one-wayness", in the following sense: Having access to the function value on some input is equivalent to having access only to an oracle that answers "yes" if the correct input is queried, and answers "no" otherwise. Constructions of this primitive (originally called oracle hashing and here re-named perfectly one-way functions) were given based on certain strong variants of the Diffie-Hellman assumption. In this work we present several constructions of perfectly one-way functions; some constructions are based on claw-free permutation, and others are based on any oneway permutation. One of our constructions is simple and efficient to the point of being attractive from a practical point of view.

We study on-line scheduling in overloaded systems. Requests for jobs arrive one by one as time proceeds; the serving agents have limited capacity and not all requests can be served. Still, we want to serve the "best" set of requests according to some criterion. In this situation, the ability to preempt (i.e., abort) jobs in service in order to make room for better jobs that would otherwise be rejected has proven to be of great help in some scenarios. We show that, surprisingly, in many other scenarios this is not the case. In a simple, generic model, we prove a polylogarithmic lower bound on the competitiveness of randomized and preemptive on-line scheduling algorithms. Our bound applies to several recently studied problems. In fact, in certain scenarios our bound is quite close to the competitiveness achieved by known deterministic, nonpreemptive algorithms.

We study the problem of maintaining authenticated communication over untrusted communication channels, in a scenario where the communicating parties may be occasionally and repeatedly broken into for limited periods of time.Once a party is broken into, its cryptographic keys are exposed and perhaps modified.We describe a mechanism that allows a party whose security has keen compromised to regain its ability to communicate in an authenticated way.The contribution of this paper is twofold.First we present a mathematical model for analyzing this scenario, and exhibit various properties and parameters of this model.Next we describe a practically-appealing protocol which enables parties to maintain authenticated communication in the presence of such a powerful adversary.For this protocol we use a variation of the proactive distributed signature schemes which were recently described by Herzberg et al.Although these schemes are designed for a model where authenticated communication and broadcast primitives are available, we show how they can be modified to work in our model, where no such primitives are available a-priori.We also present a new proactive distributed signature scheme with improved round and communication complexities.

We investigate the relations between the fault tolemnce (or resilience) and the mndornnea requirements of multiparty protocols.Fault-tolerance is measured in terms of the maximum number of colluding faulty players, t, that a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honeat players).Randomness is measured in terms of the total number of random bits needed by the players in order to execute the protocol.Previously, the upper bound on the amount of randomncm needed for securely computing any non-trivial function ~was polynomial both in n, the total number of parties, and the circuit-size C(f).This was the state of knowledge even for the special case t = 1 (i.e., when there is at most one malicious player).In this paper, we show that for any linear-size circuit, and for any value t < n/2, O(poly(t) .log n) randomness is srtflicient.More generally, we show that for any function j with circuit-size C(~), we need only O (poiy(t) .log n + polg(t) .~) randomness in order to withstrmd any coalition of size at most t.Moreover, in our prot~ CO1 only t + 1 players flip coins and the rest of the players are deterministic.Our results generalize to the case of adaptive adversaries as well.

Pseudorandom function families are a powerful cryptographic primitive, yielding, in particular simple solutions for the main problems in private key cryptography. Their existence based on general assumptions (namely the existence of one-way functions) has been established. The authors investigate new ways of designing pseudorandom function families. The goal is to find constructions that are both efficient and secure, and thus eventually to bring the benefits of pseudorandom functions to practice. The basic building blocks in the design are certain limited versions of pseudorandom function families, called finite length input pseudorandom function families, for which very efficient realizations exist impractical cryptography. Thus rather than starting from one-way functions, they propose constructions of "full-fledged" pseudorandom function families from these limited ones. In particular they propose the cascade construction, and provide a concrete security analysis which relates the strength of the cascade to that of the underlying finite pseudorandom function family in a precise and quantitative way.

Current secure multiparty protocols have the following deficiency. The public transcript of the communication can be used as an involuntary commitment of the parties to their inputs and outputs. Thus parties can be later coerced by some authority to reveal their private data. Previous work that has pointed this interesting problem out contained only partial treatment. The authors present the first general treatment of the coercion problem in secure computation. They first present a general definition of protocols that provide resilience to coercion. Their definition constitutes a natural extension of the general paradigm used for defining secure multiparty protocols. They next show that if trapdoor permutations exist then any function can be incoercibly computed (i.e., computed by a protocol that provides resilience to coercion) in the presence of computationally bounded adversaries and only public communication channels. This holds as long as less than half the parties are coerced (or corrupted). In particular, theirs are the first incoercible protocols without physical security assumptions. Also, the protocols constitute an alternative solution to the recently solved adaptive security problem. Their techniques are quite surprising and include non-standard use of deniable encryptions.

A fundamental problem in designing secure multi-party protocols is how to deal with adaptive adversaries (i.e., adversaries that may choose the corrupted parties during the course of the computation), in a setting where the channels are insecure and secure communication is achieved by cryptographic primitives based on the computational limitations of the adversary.

Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensified when the overall requested bandwidth exceeds the capacity and not all requests can be served. Furthermore, acceptance/rejection decisions regarding connections have to be made online, without knowledge of future requests. We show that the ability to preempt (i.e., abort) connections while in service in order to schedule "more valuable" connections substantially improves the throughput of some networks. We present bandwidth allocation strategies that use preemption and show that they achieve constant competitiveness with respect to the throughput, given that any single call requests at most a constant fraction of the bandwidth. Our results should be contrasted with recent works showing that non-preemptive strategies have at most inverse logarithmic competitiveness. An extended summary of this work appears in the proceedings ...

We study on-line scheduling in overloaded systems.Requests for jobs arrive one by one as time proceeds; the serving agents have limited capacity and not all requests can be served, Still, we want to serve the 'best' set of requests according to some criterion.In this situation, the ability to preempt (i.e., abort) jobs in service in order to make room for better jobs that would otherwise be rejected has proven to be of great help in some scenarios.We show that, surprisingly, in many other scenarios this is not the case.In a simple, generic model, we prove a polylogarithmic lower bound on the competitiveness of randomized and preemptive on-line scheduling algorithms.Our bound applies to several recently studied problems.In fact, in certain scenarios our bound is quite close to the competitiveness achieved by known deterministic, non-preemptive algorithms.

We initiate a study of security in asynchronous networks.We consider a completely asynchronous network where every two parties are connected via a private channel, and some of the parties may be faulty.We start by defining secure computation in this model.Our definition adapts the underlying principles of defining security (i.e.

It is known that, in both asynchronous and synchronous networks, no Byzantine Agreement (BA) protocol for n players exists if d e of the players are faulty (in other words, no BA protocol is d e-resilient). The only known asynchronous (d e \\Gamma 1)-resilient BA protocol runs in expected exponential time, and the best resilience achieved by an asynchronous protocol with polynomial complexity is (d 4 e \\Gamma 1). The question whether there exists an asynchronous (d BA protocol with polynomial complexity remained open.

A quantitative investigation of the power of randomness in the context of communication complexity is initiated. The authors prove general lower bounds on the length of the random input of parties computing a function f, depending on the number of bits communicated and the deterministic communication complexity of f. Four standard models for communication complexity are considered: the random input of the parties may be shared or local, and the communication may be one-way or two-way. The bounds are shown to be tight for all the models, for all values of the deterministic communication complexity, and for all possible quantities of bits exchanged. It is shown that it is possible to reduce the number of random bits required by any protocol, without increasing the number of bits exchanged (up to a limit depending on the advantage achieved by the protocol).>