Abstract Bitcoin is one of the most prominent examples of a distributed cryptographic protocol that is extensively used in reality. Nonetheless, existing security proofs are property-based, and as such they do not support composition. In this work, we put forth a universally composable treatment of the Bitcoin protocol. We specify the goal that Bitcoin aims to achieve as an instance of a parameterizable ledger functionality and present a UC abstraction of the Bitcoin blockchain protocol. Our ideal functionality is weaker than the first proposed candidate by Kiayias, Zhou, and Zikas [EUROCRYPT’16], but unlike the latter suggestion, which is arguably not implementable by the UC Bitcoin protocol, we prove that the one proposed here is securely UC-realized by the protocol assuming access to a global clock, to model time-based executions, a random oracle, to model hash functions, and an idealized network, to model message dissemination. We further show how known property-based approaches can be cast as special instances of our treatment and how their underlying assumptions can be cast in UC as part of the setup functionalities and without restricting the environment or the adversary.

Proofs in simulation-based frameworks have the greatest rigor when they are machine checked. But the level of details in these proofs surpasses what the formal-methods community can handle with existing tools. Existing formal results consider streamlined versions of simulation-based frameworks to cope with this complexity. Hence, a central question is how to abstract details from composability results and enable their formal verification.In this paper, we focus on the modeling of system communication in composable security statements. Existing formal models consider fixed communication patterns to reduce the complexity of their proofs. However, as we will show, this can affect the reusability of security statements. We propose an abstract approach to modeling system communication in Constructive Cryptography that avoids this problem. Our approach is suitable for mechanized verification and we use CryptHOL, a framework for developing mechanized cryptography proofs, to implement it in the Isabelle/HOL theorem prover. As a case study, we formalize the construction of a secure channel using Diffie-Hellman key exchange and a one-time-pad.

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.

Computer-aided cryptography increases the rigour of cryptographic proofs by mechanizing their verification. Existing tools focus mainly on game-based proofs, and efforts to formalize composable frameworks such as Universal Composability have met with limited success. In this paper, we formalize an instance of Constructive Cryptography, a generic theory allowing for clean, composable cryptographic security statements. Namely, we extend CryptHOL, a framework for game-based proofs, with an abstract model of Random Systems and provide proof rules for their equality and composition. We formalize security as a special kind of system construction in which a complex system is built from simpler ones. As a simple case study, we formalize the construction of an information-theoretically secure channel from a key, a random function, and an insecure channel.

Cryptographic security is usually defined as a guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that bad case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of a secure cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. A new formalism for stating such gracefully degrading security guarantees is introduced and applied to analyze the examples of password-based message authentication and password-based encryption. While a natural per-message guarantee is achieved for authentication, the situation of password-based encryption is more delicate: a per-session confidentiality guarantee only holds against attackers for which the distribution of password-guessing effort over the sessions is known in advance. In contrast, for more general attackers without such a restriction, a strong, composable notion of security cannot be achieved.

In the theory of distributed systems and cryptography one considers a setting with n parties, (often) connected via authenticated bilateral channels, who want to achieve a certain goal even if some fraction of the parties is dishonest. A classical goal of this type is to construct a broadcast channel. A broadcast channel guarantees that all honest recipients get the same value v (consistency) and, if the sender is honest, that v is the sender's input (validity). Lamport et al. showed that it is possible to construct broadcast if and only if the fraction of cheaters is less than a third. A natural question, first raised by Lamport, is whether there are weaker, still useful primitives achievable from authenticated channels. He proposed weak broadcast, where the validity condition must hold only if all parties are honest, and showed that it can be achieved with an unbounded number of protocol rounds, while broadcast cannot, suggesting that weak broadcast is in a certain sense weaker than broadcast. The purpose of this paper is to deepen the investigation of the separation between broadcast and authenticated channels. This is achieved by proving the following results. First, we prove a stronger impossibility result for 3-party broadcast. Even if two of the parties can broadcast, one can not achieve broadcast for the third party. Second, we prove a strong separation between authenticated channels and broadcast by exhibiting a new primitive, called XOR-cast, which satisfies two conditions: (1) XOR-cast is strongly unachievable (even with small error probability) from authenticated channels (which is not true for weak broadcast), and (2) broadcast is strongly unachievable from XOR-cast (and authenticated channels). This demonstrates that the hierarchy of primitives has a more complex structure than previously known. Third, we prove a strong separation between weak broadcast and broadcast which is not implied by Lamport's results. The proofs of these results requires the generalization of known techniques for impossibility proofs.

Commitment schemes that admit zero-knowledge proofs for relations among committed values are known as commit-and-prove functionalities or notarized envelopes. An important role in this context play equality proofs among commitments. They appear in various contexts of multi-party computation, circuit satisfiability or inclusion proofs. Using commit- and-prove functionalities admitting equality, we investigate blackbox constructions of commit-and-prove functionalities admitting more complex relations. Typically, these constructions have to create commitments to additional values to achieve a certain level of soundness. An important efficiency measure is the number of such additional commitments. We prove that, for the natural and quite general class of 3-round public-coin zero-knowledge protocols, implementing the inequality relation, or any of the relations NAND, NOR, or XOR, essentially requires at least 2n additional commitments in order to achieve a soundness of 2-n. A folklore protocol shows that this bound is tight for inequality.

Consider two independent games of chance, G and H, which can be won with probability at most β and γ, respectively. Then it can be shown that the game consisting of winning both G and H can be won with probability at most βγ. If the bounds on the winning probability are only due to the computational hardness of the problems and the computational complexity constraints of the game solver algorithm, then the analogous statement is not trivial but indeed holds in an approximate sense under certain conditions. This paper provides a general information-theoretic treatment of this result, showing that it is an abstract statement that is independent of complexity-theoretic considerations and exhibiting explicitly the requirement that a given game instance must be clonable. The core of the proof is a lemma on multi-argument conditional probability distributions. The amplification statement can be generalized to an arbitrary number of independent games, making the winning probability exponentially small in the number of such games.

We consider the general setting where users need to provide a secret code c to a verifying entity V in order to obtain access to a resource. More generally, the right to access the resource could, for example, be granted if one knows one of two codes ci and C2. For privacy reasons, a party P may want to hide which of the two codes it knows and only prove that it knows at least one of them. For example, if the knowledge of a code corresponds to membership in a certain society, one may want to hide which society one belongs to. In cryptography, such a proof is called a witness-hiding proof of knowledge. How can P prove such a statement to V? This paper is concerned with witness-hiding proofs of knowledge using simple mechanical tools. Specifically, we consider cable (or bicycle) locks, where the codes of the locks correspond to the secret codes. The above example of proving knowledge of either ci or c2 in a witness-hiding fashion can be achieved simply as follows. When given the two locks closed and unlinked (by V), P presents the configuration of the two locks interlocked, which can be generated if and only if P knows at least one of the codes. In the most general case with n codes c1, ..., Cn, the access right is characterized by a so-called knowledge structure Γ ⊆ P({1, ..., n}), a subset of the power set of {1, ..., n}. Access is granted if a user knows the codes corresponding to any of the subsets of Γ. We present lock-based protocols for witness-hiding proofs of knowledge for any such monotone knowledge structure, and investigate the efficiency (i.e., in particular, the number of lock configurations that P must present) in several settings such as the availability of solid rings or the availability of multiple locks for a given code. The topic of this paper is similar in spirit to other works, such as the picture hanging puzzles by Demaine et al., which explore connections between topology and real-world applications, where the motivation arises also, or even primarily, from mathematical curiosity.

Complex information-processing systems, for example, quantum circuits, cryptographic protocols, or multi-player games, are naturally described as networks composed of more basic information-processing systems. A modular analysis of such systems requires a mathematical model of systems that is closed under composition, i.e., a network of these objects is again an object of the same type. We propose such a model and call the corresponding systems causal boxes. Causal boxes capture superpositions of causal structures, e.g., messages sent by a causal box A can be in a superposition of different orders or in a superposition of being sent to box B and box C. Furthermore, causal boxes can model systems whose behavior depends on time. By instantiating the abstract cryptography framework with causal boxes, we obtain the first composable security framework that can handle arbitrary quantum protocols and relativistic protocols.

In the theory of distributed systems and in cryptography one considers a set of n parties which wish to securely perform a certain computation, even if some of the parties are dishonest. Broadcast, one of the most fundamental and widely used such primitives, allows one (possibly cheating) party to distribute a value m consistently to the other parties, in a context where only bilateral (authenticated) channels between parties are available. A well-known result [LSP82] states that this is possible if and only if strictly less than a third of the parties are dishonest. Broadcast guarantees a very strong form of consistency. This paper investigates generalizations of the broadcast setting in two directions: weaker forms of consistency guarantees are considered, and other resources than merely bilateral channels are assumed to be available. The ultimate goal of this line of work is to arrive at a complete classification of consistency specifications [Mau04]. As a concrete result in this direction we present a complete classification of three-party specifications with a binary input and binary outputs.

In this paper we provide a generalization of weak oblivious transfer through the constructive cryptography framework. This generalization requires the global order of the inputs and outputs from and to two parties called Alice and Bob to be completely defined, a subtlety which has been overlooked by previous work on the subject. We provide evidence that the order of inputs and outputs in weak oblivious transfer matters. In particular, it may influence the kind and strength of symmetry results which can be obtained about such resources.

Shared randomness is an important resource in cryptography. It is well-known that in the information-theoretic setting there is no protocol that allows two parties who do not trust each other to obtain a uniformly distributed shared bit string solely by exchanging messages such that a dishonest party can not influence the result. On the other hand, in the situation where the two parties already share a random bit string and want to use it in order to construct a longer random bit string, it is only known to be impossible when the protocols are restricted in the number of messages to be exchanged. In this paper we prove that it is also impossible when arbitrarily many messages are allowed.

Let$N$be a random variable distributed according to some appropriate distribution over the set of products of two primes, such that factoring$N$is believed to be hard. The RSA assumption states that, given an$a$chosen uniformly at random from$ {\mathbb {Z}}_{N}$and an$e \in {\mathbb {N}} \setminus \{1\}$such that$\gcd (e, \phi (N)) = 1$, it is computationally hard to find an$x\in {\mathbb {Z}} _{N}$such that$x^{e} - a \equiv 0 \pmod N$. When complexity-theoretic (relative) lower bounds for certain cryptographic problems in a general model of computation seem to elude discovery, a common practice in cryptography is to give proofs of computational security in meaningful restricted models of computation. An example of such a restricted model that is interesting in cryptography is the generic group model that has been used for proving lower bounds for the discrete logarithm problem and other related problems. A generic model captures that an algorithm does not exploit the bit representation of the elements other than for testing equality. In this paper, we prove that the problem of factoring$N$can be efficiently reduced to solving the RSA problem on$ {\mathbb {Z}}_{N}$in the generic ring model of computation, where an algorithm can perform ring operations, inverse ring operations, and test equality. This provides evidence toward the soundness of the RSA encryption and digital signature scheme, in particular showing that under the factoring assumption, they are not vulnerable to certain kinds of cryptanalytic attacks.

Functional encryption (FE) is a powerful generalization of various types of encryption. We investigate how FE can be used by a trusted authority to enforce access-control policies to data stored in an untrusted repository. Intuitively, if (functionally) encrypted data items are put in a publicly-readable repository, the effect of the encryption should be that every user has access to exactly (and only) those functions of the data items for which he has previously received the corresponding decryption key. That is, in an ideal-world view, the key authority can flexibly manage read access of users to the repository. This appears to be exactly what FE is supposed to achieve, and most natural applications of FE can be understood as specific uses of such a repository with access control. However, quite surprisingly, it is unclear whether known security definitions actually achieve this goal and hence whether known FE schemes can be used in such an application. In fact, there seems to be agreement in the cryptographic community that identifying the right security definitions for FE remains open. To resolve this problem, we treat FE in the constructive cryptography framework and propose a new conventional security definition, called composable functional encryption security (CFE-security), which exactly matches the described ideal-world interpretation. This definition (and hence the described application) is shown to be unachievable in the standard model but achievable in the random oracle model. Moreover, somewhat weaker definitions, which are achievable in the standard model, can be obtained by certain operational restrictions of the ideal-world repository, making explicit how schemes satisfying such a definition can (and cannot) meaningfully be used. Finally, adequate security definitions for generalizations of FE (such as multi-input, randomized functions, malicious cipher text generation, etc.) can be obtained by straight-forward operational extensions of the repository and extracting the corresponding security definitions. This leads towards a unified treatment of the security of FE.

Most cryptographic security proofs require showing that two systems are indistinguishable. A central tool in such proofs is that of a game, where winning the game means provoking a certain condition, and it is shown that the two systems considered cannot be distinguished unless this condition is provoked. Upper bounding the probability of winning such a game, i.e., provoking this condition, for an arbitrary strategy is usually hard, except in the special case where the best strategy for winning such a game is known to be non-adaptive. A sufficient criterion for ensuring the optimality of non-adaptive strategies is that of conditional equivalence to a system, a notion introduced in [1]. In this paper, we show that this criterion is not necessary to ensure the optimality of non-adaptive strategies by giving two results of independent interest: 1) the optimality of non-adaptive strategies is not preserved under parallel composition; 2) in contrast, conditional equivalence is preserved under parallel composition.

Existing work on "rational cryptographic protocols" treats each party (or coalition of parties) running the protocol as a selfish agent trying to maximize its utility. In this work we propose a fundamentally different approach that is better suited to modeling a protocol under attack from an external entity. Specifically, we consider a two-party game between an protocol designer and an external attacker. The goal of the attacker is to break security properties such as correctness or privacy, possibly by corrupting protocol participants; the goal of the protocol designer is to prevent the attacker from succeeding. We lay the theoretical groundwork for a study of cryptographic protocol design in this setting by providing a methodology for defining the problem within the traditional simulation paradigm. Our framework provides ways of reasoning about important cryptographic concepts (e.g., adaptive corruptions or attacks on communication resources) not handled by previous game-theoretic treatments of cryptography. We also prove composition theorems that-for the first time-provide a sound way to design rational protocols assuming "ideal communication resources" (such as broadcast or authenticated channels) and then instantiate these resources using standard cryptographic tools. Finally, we investigate the problem of secure function evaluation in our framework, where the attacker has to pay for each party it corrupts. Our results demonstrate how knowledge of the attacker's incentives can be used to circumvent known impossibility results in this setting.

An ideal coin tossing resource for two parties outputs the same random bit to both parties. We introduce the notion of an unfair coin tossing resource by relaxing both the fairness and the non-influenceability guarantees that an ideal coin toss would provide. The presence of this non-ideal behavior is necessary in order to understand what coin tossing protocols really achieve in the setting of two distrustful parties, since it is known that such an ideal coin tossing resource cannot be constructed whenever a majority of players is dishonest.

The one-time pad, the mother of all encryption schemes, is well known to be information-theoretically secure, in contrast to most encryption schemes used in practice, which are at most computationally secure. In this paper, we focus on another, completely different aspect in which the one-time pad is superior to normal encryption, and which surfaces only when the receiver (not only the eavesdropper) is considered potentially dishonest, as can be the case in a larger protocol context in which encryption is used as a sub-protocol. For example, such a dishonest receiver (who is, say, coerced by the eavesdropper) can in normal encryption verifiably leak the message to the eavesdropper by revealing the secret key. While this leakage feature can provably not be avoided completely, it is more limited if the one-time pad is used. We use the constructive cryptography framework to make these statements precise.

Information-theoretic message authentication is traditionally defined as the task of authenticating a message, transmitted over an insecure channel, using a secret key shared between sender and receiver. Previous results have investigated the trade-offs between key size, message size, and the adversary's cheating probability. In this paper we propose a new approach to information-theoretic authentication, without a secret key, but assuming that a short message (much shorter than the actual message) can be transmitted authentically, for example by speaker identification over the phone. By using such a scheme recursively one can authenticate arbitrarily long messages if one can authenticate a very short message whose length only depends on the desired cheating probability, and if it is guaranteed as a mild form of synchronization that every message arrives before the next one is sent. This result has also implications for key-based authentication. If the short message is itself authenticated with a key-based scheme, this combined scheme yields an optimal key-based authentication scheme for arbitrarily long messages, provably beating the best traditional authentication code, i.e., the best scheme that transmits a single key-dependent message over an insecure channel. The required key size is independent of the message length, which is impossible to achieve for traditional authentication codes. The proposed schemes are not only of theoretical interest but may well have practical applications in contexts where information-theoretic security is required, for example in quantum cryptography.

A random system is the mathematical object capturing the notion of a (probabilistic) interactive system that replies to every input Xi(i = 1, 2, ...) with an output Yi. A distinguisher D for two systems S and T can adaptively generate inputs, receives the corresponding outputs, and after some number q of inputs guesses which system it is talking to, S or T. Two systems are indistinguishable if for all distinguishers (in a certain class) the distinguishing advantage is very small. Indistinguishability proofs are of great importance because many security proofs in cryptography amount to the proof that two appropriately defined systems (sometimes called a real and an ideal system) are indistinguishable. In this paper we provide a general technique for proving the indistinguishability of two systems making use of the concept of conditional equivalence of systems.

Various protocols in the cryptography and distributed systems literature assume some notion of time: One major (but not the only) example are “synchronous” models which assume that a protocol is executed in a well-defined sequence of rounds with round switches that occur (almost) simultaneously at the parties. In many of the considered models, the notion of time is either implicit, or it is closely interweaved with other mechanics of the model such that formally proving even simple statements becomes a tedious task. In this work, we develop an abstract formal model that captures exactly how the availability of clocks with “weak” synchrony guarantees can benefit parties; in particular, we show how — and at what cost — the “synchrony” of clocks can be improved. Proofs in this model are simple and the statements transfer to all models that satisfy the abstraction. The main contribution of this paper is not the actual statements we prove (which mostly verify folklore beliefs), but the formal model that follows the construction paradigm of abstract cryptography and allows to state these proofs in a simple yet rigorous manner. Indeed, the paper is a step towards a treatment of synchronous cryptographic protocols in this constructive sense.

Common randomness is an important resource in many areas such as game theory and cryptography. We discuss the general problem of common randomness amplification between two distrustful parties connected by a communication channel and sharing some initial randomness. In this setting, both parties wish to agree on a common value distributed according to a target distribution by using their initial amount of common randomness and exchanging messages. Our results show that no protocol which is secure in a composable sense can significantly amplify the entropy initially shared by the parties.

A communication channel from an honest sender A to an honest receiver B can be described as a system with three interfaces labeled A, B, and E (the adversary), respectively, where the security properties of the channel are characterized by the capabilities provided at the E-interface.

Most protocols for distributed, fault-tolerant computation, or multi-party computation (MPC), provide security guarantees in an all-or-nothing fashion. In contrast, a hybrid-secure protocol provides different security guarantees depending on the set of corrupted parties and the computational power of the adversary, without being aware of the actual adversarial setting. Thus, hybrid-secure MPC protocols allow for graceful degradation of security.

In the bounded-storage model (BSM) for information-theoretic secure encryption and key agreement, one makes use of a random string whose length is greater than the assumed bound on the adversary Eve's storage capacity. The legitimate parties, Alice and Bob, execute a protocol, over an authenticated channel accessible to Eve, to generate a secret key about which Eve has essentially no information even if she has infinite computing power. The string is either assumed to be accessible to all parties or communicated publicly from Alice to Bob. While in the BSM one often assumes that Alice and Bob initially share a short secret key, and the goal of the protocol is to generate a much longer key, in this communication, we consider the bare BSM without any initially shared secret key. It is proved that in the bare BSM, secret key agreement is impossible unless Alice and Bob have themselves very high storage capacity, namely, . This proves the optimality of a scheme proposed by Cachin and Maurer.

The 26 papers and six items of correspondence in this special issue focus on information theoretic security. The papers and items of correspondence are summarized here.

We address the question whether quantum memory is more powerful than classical memory. In particular, we consider a setting where information about a random n-bit string X is stored in s classical or quantum bits, for s

We introduce a new class of realistic sources of randomness and give concrete procedures for deterministic extraction of almost uniform random bits from these sources. Moreover, we show how randomness can be extracted from general Markov sources. This extends the types of sources for which explicit deterministic randomness extractors are known.

We introduce the concept of selectable knowledge, which models the information stored in an arbitrary (e.g., quantum mechanical) device. We then analyze a situation where an entity A holds selectable knowledge about some random variable X and quantify the information A has about the output H(X) of a randomly chosen function H applied to X. This generalizes the setting of privacy amplification by universal hashing. In particular, our result can be used to prove that privacy amplification remains secure even if the enemy possesses quantum instead of classical information.

In traditional database security research, the database is usually assumed to be trustworthy. Under this assumption, the goal is to achieve security against external attacks (e.g. from hackers) and possibly also against users trying to obtain information beyond their privileges, for instance by some type of statistical inference. However, for many database applications such as health information systems there exist conflicting interests of the database owner and the users or organizations interacting with the database, and also between the users. Therefore the database cannot necessarily be assumed to be fully trusted.In this extended abstract we address the problem of defining and achieving security in a context where the database is not fully trusted, i.e., when the users must be protected against a potentially malicious database. Moreover, we address the problem of the secure aggregation of databases owned by mutually mistrusting organisations, for example by competing companies.

Digital evidence, such as digital signatures, is of crucial importance in the emerging digitally operating economy because it is easy to transmit, archive, search, and verify. Nevertheless, the initial promise of the usefulness of digital signatures was too optimistic. This calls for a systematic treatment of digital evidence. The paper provides a foundation for reasoning about digital evidence systems and legislation, thereby identifying the roles and limitations of digital evidence, in the apparently simple scenario where it should prove that an entity, A, agreed to a digital contract, d. Our approach is in sharp contrast to the current general views documented in the technical literature and in digital signature legislation. We propose an entirely new view of the concepts of certification, time stamping, revocation, and other trusted services, potentially leading to new, sounder business models for trusted services. Some of the, perhaps provocative, implications of our view are that certificates are generally irrelevant as evidence in a dispute, that it is generally irrelevant when a signature was generated, that a commitment to be liable for digital evidence cannot meaningfully be revoked, and that there is no need for mutually trusted authorities like certification authorities. We also propose a new type of digital evidence called digital declarations, based on a digital recording of a willful act indicating agreement to a document or contract.

This is the first part of a three-part paper on secret-key agreement secure against active adversaries. In all three parts, we address the question whether two parties, knowing some correlated pieces of information X and Y, respectively, can generate a string S about which an adversary, knowing some information Z and having read and write access to the communication channel used by the legitimate partners, is almost completely ignorant. Whether such key agreement is possible, and if yes at which rate, is an inherent property of the joint probability distribution P/sub XYZ/. In this part, we first prove a number of general impossibility results. We then consider the important special case where the legitimate partners as well as the adversary have access to the outcomes of many independent repetitions of a fixed tripartite random experiment. In this case, the result characterizing the possibility of secret-key agreement secure against active adversaries is of all-or-nothing nature: either a secret key can be generated at the same rate as in the (well-studied) passive-adversary case, or such secret-key agreement is completely impossible. The exact condition characterizing the two cases is presented.

For pt.I see ibid., vol.49, no.4, p.822-31(2003). In the first part, we showed that when two parties, willing to generate a secret key, but connected only by a completely insecure communication channel, have access to independent repetitions of some random experiment, then the possibility of secret-key agreement depends on a certain property, called simulatability, of the probability distribution modeling the parties' initial knowledge. More generally, the simulatability condition is important in the context of identification and authentication among parties sharing some correlated but not necessarily identical partially secret keys. Unfortunately, this condition is a priori not very useful since it is not clear how to decide efficiently whether it is satisfied or not for a given distribution P/sub XYZ/. We introduce a new formalism, based on a mechanical model for representing the involved quantities, that allows for dealing with discrete joint distributions of random variables and their manipulations by noisy channels. We show that this representation leads to a simple and efficient characterization of the possibility of secret-key agreement secure against active adversaries.

For pt. II see ibid., vol.49, no.4, p.832-38 (2003). Here, we consider the special case where the legitimate partners already share a mutual string which might, however, be partially known to the adversary. The problem of generating a secret key in this case has been well studied in the passive-adversary model - for instance, in the context of quantum key agreement - under the name of privacy amplification. We consider the same problem with respect to an active adversary and propose two protocols, one based on universal hashing and one based on extractors, allowing for privacy amplification secure against an adversary whose knowledge about the initial partially secret string is limited to one third of the length of this string. Our results are based on novel techniques for authentication secure even against adversaries knowing a substantial amount of the "secret" key.

In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t-bit string R is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. If s < t, the adversary can store only partial information about R. The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n-bit one-time pad X with n jKj about which the adversary has essentially no information, thus at rst glance apparently contradicting Shannon's bound on the key size of a perfect cipher.

This paper considers unconditionally secure protocols for reliable broadcast among a set of n players, some of which may be corrupted by an active (Byzantine) adversary.In the standard model with a complete, synchronous network of pairwise authentic communication channels among the players, broadcast is achievable if and only if the number of corrupted players is less than n/3.We show that, by extending this model only by the existence of a broadcast channel among three players, global broadcast is achievable if and only if the number of corrupted players is less than n/2.Moreover, for this an even weaker primitive than broadcast among three players is sufficient.All protocols are efficient.

Public-key certification is of crucial importance for advancing the global information infrastructure, yet it suffers from certain ambiguities and lack of understanding and precision. This paper suggests a few steps toward basing public-key certification and public-key infrastructures on firmer theoretical key. In particular, we investigate the notion of binding a public to an entity. We propose a calculus for deriving conclusions from a given entity Alice's (for instance, a judge's) view consisting of evidence and inference rules valid in Alice's world. The evidence consists of statements made by public keys (e.g., certificates, authorizations, or recommendations), statements made physically toward Alice by other entities, and trust assumptions. Conclusions are about who says a statement, who owns or is committed to a public key, and who transfers a right or authorization to another entity, and are derived by applying the inference rules.

By interpreting message authentication as a hypothesis testing problem, this paper provides a generalized treatment of information-theoretic lower bounds on an opponent's probability of cheating in one-way message authentication. We consider the authentication of an arbitrary sequence of messages, using the same secret key shared between sender and receiver. The adversary tries to deceive the receiver by forging one of the messages in the sequence. The classical two types of cheating are considered, impersonation and substitution attacks, and lower bounds on the cheating probability for any authentication system are derived for three types of goals the adversary might wish to achieve. These goals are: (1) that the fraudulent message should be accepted by the receiver, or, in addition, (2) that the adversary wishes to know or (3) wants to even choose the value of the plaintext message obtained by the legitimate receiver after decoding with the secret key.

Both uniform and nonuniform results concerning the security of the Diffie--Hellman key-exchange protocol are proved. First, it is shown that in a cyclic group G of order |G|=\prod{p_i^{e_i}}$, where all the multiple prime factors of |G| are polynomial in log|G|, there exists an algorithm that reduces the computation of discrete logarithms in G to breaking the Diffie--Hellman protocol in G and has complexity $\sqrt{\max\{\nu(p_i)\}}\cdot(\log|G|)^{O(1)}$, where $\nu(p)$ stands for the minimum of the set of largest prime factors of all the numbers d in the interval $[p-2\sqrt{p}+1,p+2\sqrt{p}+1]$. Under the unproven but plausible assumption that $\nu(p)$ is polynomial in log p, this reduction implies that the Diffie--Hellman problem and the discrete logarithm problem are polynomial-time equivalent in G. Second, it is proved that the Diffie--Hellman problem and the discrete logarithm problem are equivalent in a uniform sense for groups whose orders belong to certain classes: there exists a polynomial-time reduction algorithm that works for all those groups. Moreover, it is shown that breaking the Diffie--Hellman protocol for a small but nonnegligible fraction of the instances is equally difficult as breaking it for all instances. Finally, efficient constructions of groups are described for which the algorithm reducing the discrete logarithm problem to the Diffie--Hellman problem is efficiently constructible.

This paper is concerned with secret-key agreement by public discussion. Assume that two parties Alice and Bob and an adversary Eve have access to independent realizations of random variables X, Y, and Z, respectively, with joint distribution P/sub XYZ/. The secret-key rate S(X;Y/spl par/Z) has been defined as the maximal rate at which Alice and Bob can generate a secret key by communication over an insecure, but authenticated channel such that Eve's information about this key is arbitrarily small. We define a new conditional mutual information measure, the intrinsic conditional mutual information between S and Y when given Z, denoted by I(X;Y/spl darr/Z), which is an upper bound on S(X;Y/spl par/Z). The special scenarios are analyzed where X, Y, and Z are generated by sending a binary random variable R, for example a signal broadcast by a satellite, over independent channels, or two scenarios in which Z is generated by sending X and Y over erasure channels. In the first two scenarios it can be shown that the secret-key rate is strictly positive if and only if I(X;Y/spl darr/Z) is strictly positive. For the third scenario, a new protocol is presented which allows secret-key agreement even when all the previously known protocols fail.

The classical results in unconditional multi-party computation among a set of n players state that less than n/2 passive or Iess than n/3 active adversaries can be tolerated; assuming a broadcast channel the threshold for active adversaries is ta/2.Strictly generalizing these results we specify the set of potential y misbehaving players as an arbitrary set of subsets of the player set.We prove the necessary and sufficient conditions for the existence of secure multi-party protocols in terms of the potentially misbehaving player sets.For every function there exists a protocol secure against a set of potential passive collusions if and only if no two of these collusions add up to the full player set.The same condition applies for active adversaries when assuming a broadcast chzmnel.Without broadcast channels, for every function there exists a protocol secure against a set of potential active adverse player sets if and only if no three of these sets add up to the full player set.The complexities of the protocols not using a broadcast channel are polynomial, that of the protocol with broadcast is only slightly higher.

Anonymity of the participants is an important requirement for some applications in electronic commerce, in particular for payment systems. Because anonymity could be in conflict with law enforcement, for instance in cases of blackmailing or money laundering, it has been proposed to design systems i n which a trustee or a set of trustees can selectively revoke the anonymity of the participants involved in a suspicious transaction. From an operational point of view, it can be an important requirement that such trustees are neither involved in payment transactions nor in the opening of an account, but only in case of a justified suspicion. In this paper we present an efficient anonymous digital payment systems satisfying this requirement. The described basic protocol for anonymity revocation can be used in on-line or off-line payment systems.

A calculus of channel security properties is presented which allows the analysis and comparison of protocols for establishing secure channels in a distributed open system at a high level of abstraction. A channel is characterized by its direction, its time of availability and its security propertie s. Cryptographic primitives as well as trust relations are interpreted as transformations for channel security properties, and a cryptographic protocol can be viewed as a sequence of such transformations. A protocol thus allows to transform a set of secure channels established during an initial setup phase, together with a set of insecure channels available during operation of the system, into the set of secure channels specified by the security requirements. The necessary and sufficient requirements for establishing a secure channel between two entities A and B are characterized in terms of secure channels to be made available during the initial setup phase and in terms of the minimal trust A and B must have into other entities or into trusted third parties.

This paper, provides a general treatment of privacy amplification by public discussion, a concept introduced by Bennett, Brassard, and Robert for a special scenario. Privacy amplification is a process that allows two parties to distil a secret key from a common random variable about which an eavesdropper has partial information. The two parties generally know nothing about the eavesdropper's information except that it satisfies a certain constraint. The results have applications to unconditionally secure secret-key agreement protocols and quantum cryptography, and they yield results on wiretap and broadcast channels for a considerably strengthened definition of secrecy capacity.

The problem of generating a shared secret key S by two parties knowing dependent random variables X and Y, respectively, but not sharing a secret key initially, is considered. An enemy who knows the random variable Z, jointly distributed with X and Y according to some probability distribution P/sub XYZ/, can also receive all messages exchanged by the two parties over a public channel. The goal of a protocol is that the enemy obtains at most a negligible amount of information about S. Upper bounds on H(S) as a function of P/sub XYZ/ are presented. Lower bounds on the rate H(S)/N (as N to infinity ) are derived for the case in which X=(X/sub 1/, . . ., X/sub N/), Y=(Y/sub 1/, . . ., Y/sub N/) and Z=(Z/sub 1/, . . ., Z/sub N/) result from N independent executions of a random experiment generating X/sub i/, Y/sub i/ and Z/sub i/ for i=1, . . ., N. It is shown that such a secret key agreement is possible for a scenario in which all three parties receive the output of a binary symmetric source over independent binary symmetric channels, even when the enemy's channel is superior to the other two channels.>

Several protocols are presented that allow two parties Alice and Bob not sharing any secret information initially (except possibly a short key to be used for authentication) to generate a long shared secret key such that even an enemy Eve with unlimited computing power is unable to obtain a non-negligible amount of information (in Shannon's sense) about this key. Two different models are considered. In a first model we assume that Alice can send information to Bob over a noisy main channel but that Eve is able to receive the same information over a parallel independent noisy channel from Alice to Eve. In a second, more general model we assume that Alice, Bob and Eve receive the output of a random source (e.g., a satellite broadcasting random bits) over three independent individual channels. The condition that the channels be independent can be replaced by the condition that they be independent only to a known, arbitrarily small degree. We demonstrate that even when Eve's channel is sup...