In this paper we analyze the cheating detection and cheater identification problems for the secret sharing schemes based on the Chinese remainder theorem (CRT), more exactly for Mignotte [1] and Asmuth-Bloom [2] schemes. We prove that the majority of the solutions for Shamir’s scheme [3] can be translated to these schemes and, moreover, there are some interesting specific solutions.

Formal analysis of security protocols based on symbolic models has been very successful in finding flaws in published protocols and proving protocols secure, using automated tools. An important question is whether this kind of formal analysis implies security guarantees in the strong sense of modern cryptography. Initiated by the seminal work of Abadi and Rogaway, this question has been investigated and numerous positive results showing this so-called computational soundness of formal analysis have been obtained. However, for the case of active adversaries and protocols that use symmetric encryption computational soundness has remained a challenge. In this paper, we show the first general computational soundness result for key exchange protocols with symmetric encryption, along the lines of a paper by Canetti and Herzog on protocols with public-key encryption. More specifically, we develop a symbolic, automatically checkable criterion, based on observational equivalence, and show that a key exchange protocol that satisfies this criterion realizes a key exchange functionality in the sense of universal composability. Our results hold under standard cryptographic assumptions.

We explicitly describe and analyse \textit{blind} hierachical identity-based encryption (\textit{blind} HIBE) schemes, which are natural generalizations of blind IBE schemes \cite{gh07}. We then uses the blind HIBE schemes to construct: (1) An identity-based blind signature scheme secure in the standard model, under the computational Diffie-Hellman (CDH) assumption, and with much shorter signature size and lesser communication cost, compared to existing proposals. (2) A new mechanism supporting a user to buy digital information over the Internet without revealing what he/she has bought, while protecting the providers from cheating users.

For most basic cryptographic tasks, such as public key encryption, digital signatures, authentication, key exchange, and many other more sophisticated tasks, ideal functionalities have been formulated in the simulation-based security approach, along with their realizations. Surprisingly, however, no such functionality exists for symmetric encryption, except for a more abstract Dolev-Yao style functionality. In this paper, we fill this gap. We propose two functionalities for symmetric encryption, an unauthenticated and an authenticated version, and show that they can be implemented based on standard cryptographic assumptions for symmetric encryption schemes, namely IND-CCA security and authenticated encryption, respectively. We also illustrate the usefulness of our functionalities in applications, both in simulation-based and game-based security settings.

This document consists of a collection of attacks upon RFID protocols and is meant to serve as a quick and easy reference. This document will be updated as new attacks are found. Currently the only attacks on protocols shown are the authors' original attacks with references to similar attacks on other protocols. The main security properties considered are authentication, untraceability, and - for stateful protocols - desynchronization resistance.

Simulation-based security notions for cryptographic protocols are regarded as highly desirable, primarily because they admit strong composability and, consequently, a modular design. In this paper, we give a simulation-based security definition for two-round authenticated message exchange and show that a concrete protocol, 2AMEX-1, satisfies our security property, that is, we provide an ideal functionality for two-round authenticated message exchange and show that 2AMEX-1 realizes it securely. To model the involved public-key infrastructure adequately, we use a joint-state approach.

We consider what constitutes {\em identities\/} in cryptography. Typical examples include your name and your social-security number, or your fingerprint/iris-scan, or your address, or your (non-revoked) public-key coming from some trusted public-key infrastructure. In many situations, however, {\bf where you are} defines your identity. For example, we know the role of a bank-teller behind a bullet-proof bank window not because she shows us her credentials but by merely knowing her location. In this paper, we initiate the study of cryptographic protocols where the identity (or other credentials and inputs) of a party are derived from its \emph{geographic location}. We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the Vanilla (or standard) model, the above task (i.e., of secure positioning) is impossible to achieve. In light of the above impossibility result, we then turn to the Bounded Retrieval Model (a variant of the Bounded Storage Model) and formalize and construct information theoretically secure protocols for two fundamental tasks: \begin{itemize} \item Secure Positioning; and \item Position Based Key Exchange. \end{itemize} We then show that these tasks are in fact {\em universal\/} in this setting -- we show how we can use them to realize Secure Multi-Party Computation. Our main contribution in this paper is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results by showing that the bounded-retrieval framework is, in fact, one of the ``right" frameworks (there may be others) to study the foundations of position-based cryptography.

Undeniable signatures were proposed to limit the verification property of ordinary digital signatures. In fact, the verification of such signatures cannot be attained without the help of the signer, via the confirmation/denial protocols. Later, the concept was refined to give the possibility of converting a \emph{selected} signature into an ordinary one, or publishing a \emph{universal} receipt that turns all undeniable signatures publicly verifiable. In this paper, we present the first generic construction for convertible undeniable signatures from certain weakly secure cryptosystems and any secure digital signature scheme. Next, we give two specific approaches for building convertible undeniable signatures from a large class of pairing-based signatures. These methods find a nice and practical instantiation with known encryption and signature schemes. For instance, we achieve the most efficient undeniable signatures with regard to the signature length and cost, the underlying assumption and the security model. We believe these constructions could be an interesting starting point to develop more efficient schemes or give better security analyses of the existing ones.

Recently, Chen et al. and Juang et al. each proposed one and two e-cash payment systems respectively. They claimed that their schemes are secure. However, in this paper, we will present the shortcomings of their schemes and then propose a novel one from pairings. After security analysis and comparison, we conclude that our scheme not only is more secure but also possesses more functions that a secure electronic cash system should encompass than all of the proposed protocols.

It is well-known that protocols that satisfy a security property when executed in isolation do not necessarily satisfy the same security property when they are executed in an environment containing other protocols. We demonstrate this fact on a family of recently proposed RFID protocols by Lee, Batina, and Verbauwhede. We invalidate the authentication and untraceability claims made for several of the family's protocols. We also present man-in-the-middle attacks on untraceability in all of the protocols in the family. Similar attacks can be carried out on some other protocols in the literature, as well. We briefly indicate how to repair the protocols.

Physical Unclonable Functions (PUFs) are physical objects that are unique, practically unclonable and that behave like a random function when subjected to a challenge. Their use has been proposed for authentication tokens and anti-counterfeiting. A Controlled PUF (CPUF) consists of a PUF and a control layer that restricts a user's access to the PUF input and output. CPUFs can be used for secure key storage, authentication, certified execution of programs, and certified measurements. In this paper we modify a number of protocols involving CPUFs in order to improve their security. Our modifications mainly consist of encrypting a larger portion of the message traffic, and additional restrictions on the CPUF accessibility. We simplify the description of CPUF protocols by using flowchart notation. Furthermore we explicitly show how the helper data for the PUFs is handled.

Adaptive oblivious transfer (adaptive OT) schemes have wide applications such as oblivious database searches, secure multiparty computation and etc. It is a two-party protocol which simulates an ideal world such that the sender sends $M_1, \cdots, M_n$ to the trusted third party (TTP) first, and then the receiver receives $M_{\sigma_i}$ from TTP adaptively for $i=1,2,\cdots k$. In the standard model, however, the fully simulatable schemes known so far had to rely on dynamic assumptions such as $q$-strong DH assumption, $q$-PDDH assumption and $q$-hidden LRSW assumption. This paper shows two fully simulatable adaptive OT schemes which do not rely on dynamic assumptions in the standard model. Our first scheme holds under the DDH assumption and our second scheme holds under the Paillier's decisional $N$th residuosity assumption, respectively.

In this paper, we focus on the specific problems of Private Matching, Set Disjointness and Cardinality Set Intersection in information theoretic settings. Specifically, we give perfectly secure protocols for the above problems in n party settings, tolerating a computational ly unbounded semi-honest adversary, who can passively corrupt at most t < n/2 parties. To the best of our knowledge, these are the first such information theoretically secure protocols in a multi-party setting for all three problems. Previous solutions for Distributed Private Matching and Cardinality Set Intersection were cryptographical ly secure and the previous Set Disjointness solution, though information theoretically secure, is in a two party setting. We also propose a new model for Distributed Private matching which is relevant in a multi-party setting.

We study the problem of authenticating the content and creation time of documents generated by an organization and retained in archival storage. Recent regulations (e.g., the Sarbanes-Oxley act and the Securities and Exchange Commission rule) mandate secure retention of important business records for several years. We provide a mechanism to authenticate bulk repositories of archived documents. In our approach, a space efficient local data structure encapsulates a full document repository in a short (e.g., 32-byte) digest. Periodically registered with a trusted party, these commitments enable compact proofs of both document creation time and content integrity. The data structure, an append-only persistent authenticated dictionary, allows for efficient proofs of existence and non-existence, improving on state-of-the-art techniques. We give a rigorous security analysis of our solution and confirm through an experimental evaluation with the Enron email corpus its feasibility in practice.

The complexity of a secret sharing scheme is defined as the ratio between the maximum length of the shares and the length of the secret. The optimization of this parameter for general access structures is an important and very difficult open problem in secret sharing. We explore in this paper the connections of this open problem with matroids and polymatroids. Matroid ports were introduced by Lehman in 1964. A forbidden minor characterization of matroid ports was given by Seymour in 1976. These results are previous to the invention of secret sharing by Shamir in 1979. Important connections between ideal secret sharing schemes and matroids were discovered by Brickell and Davenport in 1991. Their results can be restated as follows: every ideal secret sharing scheme defines a matroid, and its access structure is a port of that matroid. In spite of this, the results by Lehman and Seymour and other subsequent results on matroid ports have not been noticed until now by the researchers interested in secret sharing. Lower bounds on the optimal complexity of access structures can be found by taking into account that the joint Shannon entropies of a set of random variables define a polymatroid. We introduce a new parameter, which is denoted by $\kappa$, to represent the best lower bound that can be obtained by this method. We prove that every bound that is obtained by this technique for an access structure applies to its dual structure as well. By using the aforementioned result by Seymour we obtain two new characterizations of matroid ports. The first one refers to the existence of a certain combinatorial configuration in the access structure, while the second one involves the values of the parameter $\kappa$ that is introduced in this paper. Both are related to bounds on the optimal complexity. As a consequence, we generalize the result by Brickell and Davenport by proving that, if the length of every share in a secret sharing scheme is less than 3/2 times the length of the secret, then its access structure is a matroid port. This generalizes and explains a phenomenon that was observed in several families of access structures. Finally, we present a construction of linear secret sharing schemes for the ports of the Vamos matroid and the non-Desargues matroid, which do not admit any ideal secret sharing scheme. We obtain in this way upper bounds on their optimal complexity. These new bounds are a contribution on the search of examples of access structures whose optimal complexity lies between 1 and 3/2.

Diagnostic and classification algorithms play an important role in data analysis, with applications in areas such as health care, fault diagnostics, or benchmarking. Branching programs (BP) is a popular representation model for describing the underlying classification/diagnostics algorithms. Typical application scenarios involve a client who provides data and a service provider (server) whose diagnostic program is run on client's data. Both parties need to keep their inputs private. We present new, more efficient privacy-protecting protocols for remote evaluation of such classification/diagnostic programs. In addition to efficiency improvements, we generalize previous solutions -- we securely evaluate private linear branching programs (LBP), a useful generalization of BP that we introduce. We show practicality of our solutions: we apply our protocols to the privacy-preserving classification of medical ElectroCardioGram (ECG) signals and present implementation results. Finally, we discover and fix a subtle security weakness of the most recent remote diagnostic proposal, which allowed malicious clients to learn partial information about the program.

We treat the security of group key exchange (GKE) in the universal composability (UC) framework. Analyzing GKE protocols in the UC framework naturally addresses attacks by malicious insiders. We define an ideal functionality for GKE that captures contributiveness in addition to other desired security goals. We show that an efficient two-round protocol securely realizes the proposed functionality in the random oracle model. As a result, we obtain the most efficient UC-secure contributory GKE protocol known.

LaMacchia, Lauter and Mityagin recently presented a strong security definition for authenticated key agreement strengthening the well-known Canetti-Krawczyk definition. They also described a protocol, called NAXOS, that enjoys a simple security proof in the new model. Compared to MQV and HMQV, NAXOS is less efficient and cannot be readily modified to obtain a one-pass protocol. On the other hand MQV does not have a security proof, and the HMQV security proof is extremely complicated. This paper proposes a new authenticated key agreement protocol, called CMQV (`Combined' MQV), which incorporates design principles from MQV, HMQV and NAXOS. The new protocol achieves the efficiency of HMQV and admits a natural one-pass variant. Moreover, we present a simple and intuitive proof that CMQV is secure in the LaMacchia-Lauter-Mityagin model.

A key exchange protocol allows a set of parties to agree upon a secret session key over a public network. Two-party key exchange (2PKE) protocols have been rigorously analyzed under various models considering different adversarial actions. However, the analysis of group key exchange (GKE) protocols has not been as extensive as that of 2PKE protocols. Particularly, the security attribute of key compromise impersonation (KCI) resilience has so far been ignored for the case of GKE protocols. We first model the security of GKE protocols addressing KCI attacks by both outsider and insider adversaries. We then show that a few existing protocols are not secure even against outsider KCI attacks. The attacks on these protocols demonstrate the necessity of considering KCI resilience for GKE protocols. Finally, we give a new proof of security for an existing GKE protocol under the revised model assuming random oracles.

In order to save bandwidth and thus battery power, sensor network measurements are sometimes aggregated en-route while being reported back to the querying server. Authentication of the measurements then becomes a challenge if message integrity is important for the application. At ESAS 2007, the End-by-Hop protocol for securing in-network aggregation for sensor nodes was presented. The solution was claimed to be secure and efficient and to provide the possibility of trading off bandwidth against computation time on the server. In this paper, we disprove these claims. We describe several attacks against the proposed solution and point out shortcomings in the original complexity analysis. In particular, we show that the proposed solution is inferior to a naive solution without in-network aggregation both in security and in efficiency.

In this paper, we propose two authenticated key exchange (AKE) protocols, SMEN and SMEN&#8722;, which have efficient online computation and tight security proof in the extended Canetti-Krawczyk (eCK) model. SMEN takes 1.25 exponentiations in online computation, close to that (1.17 exponentiations) of the most efficient AKEs MQV and its variants HMQV and CMQV. SMEN has a security reduction as tight as that of NAXOS, which is the first AKE having a tight security reduction in the eCK model. As a comparison, MQV does not have a security proof; both HMQV and CMQV have a highly non-tight security reduction, and HMQV needs a non-standard assumption; NAXOS takes 2.17 exponentiations in online computation; NETS, a NAXOS variant, takes two online exponentiations in online computation. SMEN simultaneously achieves online efficiency and a tight security proof at a cost of 0.17 more exponentiations in offline computation and the restriction that one party is not allowed to establish a key with itself. SMEN&#8722; takes 1.29 exponentiations in online computation, but SMEN&#8722; does not use the static private key to compute the ephemeral public key (as does in SMEN, NAXOS, CMQV, and NETS), and hence reduces the risk of leaking the static private key.

This paper discusses the practical implementation of a novel security tool termed SIMPL system, which was introduced in [1]. SIMPL systems can be regarded as a public key version of physical unclonable functions (PUFs). Like the latter, a SIMPL system S is physically unique and nonreproducible, and implements an individual function FS. In opposition to a PUF, however, a SIMPL system S possesses a publicly known numerical description, which allows its digital simulation and prediction. At the same time, any such simulation must work at a detectably lower speed than the real-time behavior of S. As argued in [1], SIMPL systems have certain practicality and security advantages in comparison to PUFs, certificates of authenticity, physically obfuscated keys, and also to standard mathematical cryptotechniques. In [1], definitions, protocols, and optical implementations of SIMPL systems were presented. This manuscript focuses on concrete electrical, integrated realizations of SIMPL systems, and proposes two potential candidates: SIMPL systems derived from special SRAM-architectures (socalled “skew designs” of SRAM cells), and implementations based on Cellular Non-Linear Networks (CNNs).

In the papers Stronger Security of Authenticated Key Exchange [LLM07, LLM06], a new security model for key exchange protocols is proposed. The new model is suggested to be at least as strong as previous models for key exchange protocols. In particular, the model includes a new notion of an Ephemeral Key Reveal adversary query, which is claimed in [LLM06, Oka07, Ust08] to be at least as strong as existing definitions of the Session-state Reveal query. We show that for some protocols, Session-state Reveal is strictly stronger than Ephemeral Key Reveal. In particular, we show that the NAXOS protocol from [LLM07, LLM06] does not meet its security requirements if the Session-state Reveal query is allowed in the security model.

Zhou et al proposed a quantum encryption scheme based on quantum computation in 2006. Each qubit of the ciphertext is constrained to two pairs of conjugate states. So its implementation is feasible with the existing technology. But it is inefficient since it entails six key bits to encrypt one message bit, and the resulting ciphertext for one message bit consists of three qubits. In addition, its security can not be directly reduced to the well-known BB84 protocol. In this paper, we revisit it using the technique developed in BB84 protocol. The new scheme entails only two key bits to encrypt one message bit. The resulting ciphertext is just composed of two qubits. It saves about a half cost without the loss of security. Moreover, the encryption scheme is probabilistic rather than deterministic.

Zeng and Keitel proposed an arbitrated quantum signature scheme In 2002. Recently, Curty and Lütkenhaus pointed out that the protocol is not operationally specified. In a reply, Zeng gave more details of the scheme. The author also claimed that the scheme is suitable for unknown messages. In this letter, we remark that the invented scenario in the original scheme is artificial. This is because its security entirely depends on the presence of a trustworthy arbitrator. Moreover, the claim that the original scheme is suitable for unknown messages is not sound.

A broadcast protocol allows a sender to distribute a message through a point-to-point network to a set of parties, such that (i) all parties receive the same message, even if the sender is corrupted, and (ii) this is the sender's message, if he is honest. Broadcast protocols satisfying these properties are known to exist if and only if $t<n/3$, where $n$ denotes the total number of parties, and $t$ denotes the maximal number of corruptions. When a setup allowing signatures is available to the parties, then such protocols exist even for $t<n$. Broadcast is the probably most fundamental primitive in distributed cryptography, and is used in almost any cryptographic (multi-party) protocol. However, a broadcast protocol ``only'' satisfying the above properties might be insecure when being used in the context of another protocol. In order to be safely usable within other protocols, a broadcast protocol must satisfy a simulation-based security notion, which is secure under composition. In this work, we show that most broadcast protocols in the literature do not satisfy a (natural) simulation-based security notion. We do not know of any broadcast protocol which could be securely invoked in a multi-party computation protocol in the secure-channels model. The problem is that existing protocols for broadcast do not preserve the secrecy of the message while being broadcasted, and in particular allow the adversary to corrupt the sender (and change the message), depending on the message being broadcasted. For example, when every party should broadcast a random bit, the adversary could corrupt those parties that want to broadcast 0, and make them broadcast 1. More concretely, we show that simulatable broadcast in a model with secure channels is possible if and only if $t<n/3$, respectively $t \le n/2$ when a signature setup is available. The positive results are proven by constructing secure broadcast protocols.

Secure Join-operator computation in distributed relational databases is one of important problems in the field of secure multiparty computation with valuable applications. We propose a gerneral construction for 2-party Join computation based-on anonymous IBE scheme and its user private-keys blind generation techniques. The construction is GUC(Generalized Universally Composable) secure in standard model. For this goal a new notion of non-malleable zero-knowledge proofs of knowledge and its efficient general construction is also presented.

Crisp Commitment schemes are very useful building blocks in the design of high-level cryptographic protocols. They are used as a mean of flipping fair coins between two players and others. In this paper an attempt has been made to give a generalized framework for Crisp Commitment schemes is called an Ordinary Crisp Commitment Scheme (OCCS). The Hiding and Binding properties of OCCS are well defined. We also review some the existing of different Crisp Commitment schemes and we show how it is follow our presenting framework.

Motivated by the challenging task of designing ``secure'' vote storage mechanisms, we study information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. We propose a mechanism for storing a set of at most $K$ elements from a large universe of size $N$ on write-once memories in a manner that does not reveal the insertion order of the elements. We consider a standard model for write-once memories, in which the memory is initialized to the all $0$'s state, and the only operation allowed is flipping bits from $0$ to $1$. Whereas previously known constructions were either inefficient (required $\Theta(K^2)$ memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements. We also demonstrate a connection between secure vote storage mechanisms and one of the classical distributed computing problems: conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.

A. Kent proposed a quantum bit string commitment protocol in 2003. Not using the standard two conjugate states $|0\rangle$, $|1\rangle $, $|+\rangle $ and $|-\rangle $, the protocol uses $\psi_0=|0\rangle$ and $\psi_1=\sin \theta|0\rangle+\cos \theta |1\rangle $, where $\theta\neq 0$. In this paper, we show that the protocol can not guarantee security to the receiver. $(1-\frac{\sin^2 \theta}{2})n $ bits are definitely exposed to the receiver, where $n$ is the length of the committed string.

Cloud Computing has been envisioned as the next-generation architecture of IT Enterprise. In contrast to traditional solutions, where the IT services are under proper physical, logical and personnel controls, Cloud Computing moves the application software and databases to the large data centers, where the management of the data and services may not be fully trustworthy. This unique attribute, however, poses many new security challenges which have not been well understood. In this article, we focus on cloud data storage security, which has always been an important aspect of quality of service. To ensure the correctness of users' data in the cloud, we propose an effective and flexible distributed scheme with two salient features, opposing to its predecessors. By utilizing the homomorphic token with distributed verification of erasure-coded data, our scheme achieves the integration of storage correctness insurance and data error localization, i.e., the identification of misbehaving server(s). Unlike most prior works, the new scheme further supports secure and efficient dynamic operations on data blocks, including: data update, delete and append. Extensive security and performance analysis shows that the proposed scheme is highly efficient and resilient against Byzantine failure, malicious data modification attack, and even server colluding attacks.

RFID can be used for a variety of applications, e.g., to conveniently pay for public transportation. However, achieving security and privacy of payment is challenging due to the extreme resource restrictions of RFID tags. In this paper, we propose PSP -- a secure, RFID-based protocol for privacy-preserving payment. Similar to traditional electronic cash, the user of a tag can pay access to a metro using his tag and so called {coins} of a virtual currency. With PSP, tags do not need to store valid coins, but generate them on the fly. Using Bloom filters, readers can verify the validity of generated coins offline. PSP guarantees privacy such that neither the metro nor an adversary can reveal the identity of a user or link subsequent payments. PSP is secure against {invention} and {overspending} of coins, and can reveal the identity of users trying to {doublespend} coins. Still, PSP is lightweight: it requires only a hash-function and few bytes of non-volatile memory on the tag.

Combining and analyzing data collected at multiple locations is critical for a wide variety of applications, such as detecting and diagnosing malicious attacks or computing an accurate estimate of the popularity of Web sites. However, legitimate concerns about privacy often inhibit participation in collaborative data-analysis systems. In this paper, we design, implement, and evaluate a practical solution for privacy-preserving collaboration among a large number of participants. Scalability is achieved through a ``semi-centralized'' architecture that divides responsibility between a proxy that obliviously blinds the client inputs and a database that identifies the (blinded) keywords that have values satisfying some evaluation function. Our solution leverages a novel cryptographic protocol that provably protects the privacy of both the participants and the keywords. For example, if web servers collaborate to detect source IP addresses responsible for denial-of-service attacks, our protocol would not reveal the traffic mix of the Web servers or the identity of the ``good'' IP addresses. We implemented a prototype of our design, including an amortized oblivious transfer protocol that substantially improves the efficiency of client-proxy interactions. Our experiments show that the performance of our system scales linearly with computing resources, making it easy to improve performance by adding more cores or machines. For collaborative diagnosis of denial-of-service attacks, our system can handle millions of suspect IP addresses per hour when the proxy and the database each run on two quad-core machines.

Program hardening for secure execution in remote untrusted environment is an important yet elusive goal of security, with numerous attempts and efforts of the research community to produce secure solutions. Obfuscation is the prevailing practical technique employed to tackle this issue. Unfortunately, no provably secure obfuscation techniques currently exist. Moreover, Barak et. al., showed that not all programs can be obfuscated. Theoretical research exhibits provably secure albeit inefficient constructions, e.g. using tools from encrypted domain. We present a rigorous approach to software execution in remote environment based on a new white box primitive, the White Box Remote Program Execution (WBRPE), whose security specifications include confidentiality and integrity of both the local and the remote hosts. WBRPE can be used for many applications, e.g. grid computing, digital rights management, mobile agents. We then present a construction of a specific program such that if there exists a secure WBRPE for that program, then there is a secure WBRPE for any program, reducing its security to the underlying WBRPE primitive. The security of WBRPE construction is established by reduction among two white box primitives and it introduces new techniques of programs manipulation.

Recently, Tsai and Hsiang et al. each proposed a multi-server authentication protocol. They claimed their protocols are secure and can withstand various attacks. However, after our analysis, we found some security loopholes in each protocol. We will first show the attacks on their schemes and then present ours. After the security analysis, we conclude that our scheme is the most secure one among all of the proposed protocols in multi-server environments nowadays.

Entity recognition does not ask whether the message is from some entity X, just whether a message is from the same entity as a previous message. This turns turns out to be very useful for low-end devices. Motivated by an attack against a protocol presented at SAC 2003, the current paper proposes a new protocol -- the ``Jane Doe Protocol'' --, and provides a formal proof of its concrete security. The protocol neither employs asymmetric cryptography, nor a trusted third party, nor any key pre-distribution. It is suitable for light-weight cryptographic devices such as sensor network motes and RFID tags.

We introduce HAIL (High-Availability and Integrity Layer), a distributed cryptographic system that permits a set of servers to prove to a client that a stored file is intact and retrievable. HAIL strengthens, formally unifies, and streamlines distinct approaches from the cryptographic and distributed-systems communities. Proofs in HAIL are efficiently computable by servers and highly compact---typically tens or hundreds of bytes, irrespective of file size. HAIL cryptographically verifies and reactively reallocates file shares. It is robust against an active, mobile adversary, i.e., one that may progressively corrupt the full set of servers. We propose a strong, formal adversarial model for HAIL, and rigorous analysis and parameter choices. We show how HAIL improves on the security and efficiency of existing tools, like Proofs of Retrievability (PORs) deployed on individual servers. We also report on a prototype implementation.

A new protocol for 1-2 (String) Oblivious Transfer is proposed. The Protocol uses 5 rounds of message exchange.

Designing efficient cryptographic protocols tolerating adaptive adversaries, who are able to corrupt parties on the fly as the computation proceeds, has been an elusive task. Indeed, thus far no \emph{efficient} protocols achieve adaptive security for general multi-party computation, or even for many specific two-party tasks such as oblivious transfer (OT). In fact, it is difficult and expensive to achieve adaptive security even for the task of \emph{secure communication}, which is arguably the most basic task in cryptography. In this paper we make progress in this area. First, we introduce a new notion called \emph{semi-adaptive} security which is slightly stronger than static security but \emph{significantly weaker than fully adaptive security}. The main difference between adaptive and semi-adaptive security is that, for semi-adaptive security, the simulator is not required to handle the case where \emph{both} parties start out honest and one becomes corrupted later on during the protocol execution. As such, semi-adaptive security is much easier to achieve than fully adaptive security. We then give a simple, generic protocol compiler which transforms any semi-adaptively secure protocol into a fully adaptively secure one. The compilation effectively decomposes the problem of adaptive security into two (simpler) problems which can be tackled separately: the problem of semi-adaptive security and the problem of realizing a weaker variant of secure channels. We solve the latter problem by means of a new primitive that we call {\em somewhat non-committing encryption} resulting in significant efficiency improvements over the standard method for realizing (fully) secure channels using (fully) non-committing encryption. Somewhat non-committing encryption has two parameters: an equivocality parameter $\ell$ (measuring the number of ways that a ciphertext can be ``opened'') and the message sizes $k$. Our implementation is very efficient for small values $\ell$, \emph{even} when $k$ is large. This translates into a very efficient compilation of many semi-adaptively secure protocols (in particular, for a task with small input/output domains such as bit-OT) into a fully adaptively secure protocol. Finally, we showcase our methodology by applying it to the recent Oblivious Transfer protocol by Peikert \etal\ [Crypto 2008], which is only secure against static corruptions, to obtain the first efficient, adaptively secure and composable OT protocol. In particular, to transfer an $n$-bit message, we use a constant number of rounds and $O(n)$ public key operations.

In this paper, we construct a strongly unforgeable ID-based signature scheme without random oracles. The signature size of our scheme is smaller than that of other schemes based on varieties of the Diffie-Hellman problem or the discrete logarithm problem. The security of the scheme relies on the difficulty to solve three problems related to the Diffie-Hellman problem and a one-way isomorphism.

A new 4-pass Key-Agreement-Protocol is presented. The security of the protocol mainly relies on the existence of a (polynomial-time computable) One-Way-Function and the supposed hardness of solving a specific system of equations

Secret handshake allows two members in the same group to authenticate each other secretly. In previous works of secret handshake schemes, two types of anonymities against the group authority (GA) of a group G are discussed: 1)Even GA cannot identify members, namely nobody can identify them (No-Traceability), 2)Only GA can identify members (Traceability). In this paper, first the necessity of tracing of the identification is shown. Second, we classify abilities of GA into the ability of identifying players and that of issuing the certificate to members. We introduce two anonymities Co-Traceability and Strong Detector Resistance. When a more strict anonymity is required ever for GA, the case 2) is unfavorable for members. Then, we introduce Co-Traceability where even if A has GAs ability of identifying members or issuing the certificate, A cannot trace members identification. However, if a scheme satisfies Co-Traceability, GA may be able to judge whether handshake players belong to the own group. Then, we introduce Strong Detector Resistance where even if an adversary A has GAs ability of identifying members, A cannot make judgments whether a handshaking player belongs to G. Additionally, we propose a secret handshake scheme which satisfies previous security requirements and our proposed anonymity requirements by using group signature scheme with message recovery.

In~\cite{gscm}, GSCM mode of operation for authenticated encryption was presented. GSCM is based on the Galois/Counter Mode (GCM). GSCM is an enhancement of GCM, which is characterized by its high throughput and low memory consumption in network applications. In this paper, we propose some enhancements to GSCM and compare it with the different implementations of GCM. We present stability, performance, memory and security analyses of different implementations of GSCM and GCM.

Dutta and Mukhopadhyay have recently proposed some very efficient self-healing key distribution schemes with revocation. The parameters of these schemes contradict some results (lower bounds) presented by Blundo et al. In this paper different attacks against the schemes of Dutta and Mukhopadhyay are explained: one of them can be easily avoided with a slight modification in the schemes, but the other one is really serious.

Two-party Secure Function Evaluation (SFE) is a very useful cryptographic tool which allows two parties to evaluate a function known to both parties on their private (secret) inputs. Some applications with sophisticated privacy needs require the function to be known only to one party and kept private (hidden) from the other one. However, existing solutions for SFE of private functions (PF-SFE) deploy Universal Circuits (UC) and are still very inefficient in practice. In this paper we bridge the gap between SFE and PF-SFE with SFE of what we call {\em semi-private functions} (SPF-SFE), i.e., one function out of a given class of functions is evaluated without revealing which one. We present a general framework for SPF-SFE allowing a fine-grained trade-off and tuning between SFE and PF-SFE covering both extremes. In our framework, semi-private functions can be composed from several privately programmable blocks (PPB) which can be programmed with one function out of a class of functions. The framework allows efficient and secure embedding of constants into the resulting circuit to improve performance. To demonstrate practicability of the framework we have implemented a compiler for SPF-SFE based on the Fairplay SFE framework. SPF-SFE is sufficient for many practically relevant privacy-preserving applications, such as privacy-preserving credit checking which can be implemented using our framework and compiler as described in the paper.

Efficient non-interactive zero-knowledge proofs are a powerful tool for solving many cryptographic problems. We apply the recent Groth-Sahai (GS) proof system for pairing product equations (Eurocrypt 2008) to two related cryptographic problems: compact e-cash (Eurocrypt 2005) and simulatable verifiable random functions (CRYPTO 2007). We present the first efficient compact e-cash scheme that does not rely on a random oracle in its security proof. To this end we construct efficient GS proofs for signature possession, pseudo randomness and set membership. The GS proofs for pseudorandom functions give rise to a much cleaner and substantially faster construction of simulatable verifiable random functions (sVRF) under a weaker number theoretic assumption. We obtain the first efficient fully simulatable sVRF with a polynomial sized output domain (in the security parameter).

In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their private inputs. The computation should be carried out in a secure way, meaning that no coalition of corrupted parties should be able to learn more than specified or somehow cause the result to be ``incorrect''. Typically, corrupted parties are either assumed to be semi-honest (meaning that they follow the protocol specification) or malicious (meaning that they may deviate arbitrarily from the protocol). However, in many settings, the assumption regarding semi-honest behavior does not suffice and security in the presence of malicious adversaries is excessive and expensive to achieve. In this paper, we introduce the notion of {\em covert adversaries}, which we believe faithfully models the adversarial behavior in many commercial, political, and social settings. Covert adversaries have the property that they may deviate arbitrarily from the protocol specification in an attempt to cheat, but do not wish to be ``caught'' doing so. We provide a definition of security for covert adversaries and show that it is possible to obtain highly efficient protocols that are secure against such adversaries. We stress that in our definition, we quantify over all (possibly malicious) adversaries and do not assume that the adversary behaves in any particular way. Rather, we guarantee that if an adversary deviates from the protocol in a way that would enable it to ``cheat'' (meaning that it can achieve something that is impossible in an ideal model where a trusted party is used to compute the function), then the honest parties are guaranteed to detect this cheating with good probability. We argue that this level of security is sufficient in many settings.

In this paper we show that using standard smartcards it is possible to construct truly practical secure protocols for a variety of tasks. Our protocols achieve full \emph{simulation-based security} in the presence of \emph{malicious adversaries}, and can be run on very large inputs. We present protocols for secure set intersection, oblivious database search and more. We have also implemented our set intersection protocol in order to show that it is truly practical: on sets of size 30,000 elements takes 20 seconds for one party and 30 minutes for the other. This demonstrates that in settings where physical smartcards can be sent between parties (as in the case of private data mining tasks between security and governmental agencies), it is possible to use secure protocols with proven simulation-based security.

In this paper we propose a conversion from signature schemes connected to coding theory into blind signature schemes. We give formal security reductions to combinatorial problems not connected to number theory. This is the first blind signature scheme which can not be broken by quantum computers via cryptanalyzing the underlying signature scheme employing Shor’s algorithms. We thus present a step towards diversifying computational assumptions on which blind signatures can be based. We achieve blind signatures by a different concept of blinding: Instead of blinding the message, we blind the public key, such that generating a (blind) signature for the blinded key requires the interaction of the holder of the original secret key. To verify the blind signature, the connection between the original and the blinded key is proven by a static ZK proof. The major ingredient for our conversion is the PKP protocol by Shamir.

We show attacks on several cryptographic schemes that have recently been proposed for achieving various security goals in sensor networks. Roughly speaking, these schemes all use "perturbation polynomials" to add "noise" to polynomial-based systems that offer information-theoretic security, in an attempt to increase the resilience threshold while maintaining efficiency. We show that the heuristic security arguments given for these modified schemes do not hold, and that they can be completely broken once we allow even a slight extension of the parameters beyond those achieved by the underlying information-theoretic schemes. Our attacks apply to the key predistribution scheme of Zhang et al. (MobiHoc~2007), the access-control schemes of Subramanian et al. (PerCom~2007), and the authentication schemes of Zhang et~al. (INFOCOM~2008).

Enhanced Privacy ID (EPID) is a cryptographic scheme that enables the remote authentication of a hardware device while preserving the privacy of the device. EPID can be seen as a direct anonymous attestation scheme with enhanced revocation capabilities. In EPID, a device can be revoked if the private key embedded in the hardware device has been extracted and published widely so that the revocation manager finds the corrupted private key. In addition, the revocation manager can revoke a device based on the signatures the device has signed, if the private key of the device is not known. In this paper, we introduce a new security notion of EPID including the formal definitions of anonymity and unforgeability with revocation. We also give a construction of an EPID scheme from bilinear pairing. Our EPID scheme is efficient and provably secure in the random oracle model under the strong Diffie-Hellman assumption and the decisional Diffie-Hellman assumption.

An attribute based encryption scheme capable of handling multiple authorities was recently proposed by Chase. The scheme is built upon a single-authority attribute based encryption scheme presented earlier by Sahai and Waters. Chase’s construction uses a trusted central authority that is inherently capable of decrypting arbitrary ciphertexts created within the system. We present a multi-authority attribute based encryption scheme in which only the set of recipients defined by the encrypting party can decrypt a corresponding ciphertext. The central authority is viewed as “honest-but-curious”: on the one hand it honestly follows the protocol, and on the other hand it is curious to decrypt arbitrary ciphertexts thus violating the intent of the encrypting party. The proposed scheme, which like its predecessors relies on the Bilinear Diffie-Hellman assumption, has a complexity comparable to that of Chase’s scheme. We prove that our scheme is secure in the selective ID model and can tolerate an honest-but-curious central authority.

A proof of retrievability (POR) is a compact proof by a file system (prover) to a client (verifier) that a target file $F$ is intact, in the sense that the client can fully recover it. As PORs incur lower communication complexity than transmission of $F$ itself, they are an attractive building block for high-assurance remote storage systems. In this paper, we propose a theoretical framework for the design of PORs. Our framework improves the previously proposed POR constructions of Juels-Kaliski and Shacham-Waters, and also sheds light on the conceptual limitations of previous theoretical models for PORs. It supports a fully Byzantine adversarial model, carrying only the restriction—fundamental to all PORs—that the adversary’s error rate $\epsilon$ be bounded when the client seeks to extract $F$. Our techniques support efficient protocols across the full possible range of $\epsilon$, up to $\epsilon$ non-negligibly close to 1. We propose a new variant on the Juels-Kaliski protocol and describe a prototype implementation. We demonstrate practical encoding even for files $F$ whose size exceeds that of client main memory.

The notion of Zero Knowledge Proofs (of knowledge) [ZKP] is central to cryptography; it provides a set of security properties that proved indispensable in concrete protocol design. These properties are defined for any given input and also for any auxiliary verifier private state, as they are aimed at any use of the protocol as a subroutine in a bigger application. Many times, however, moving the theoretical notion to practical designs has been quite problematic. This is due to the fact that the most efficient protocols fail to provide the above ZKP properties {\em for all} possible inputs and verifier states. This situation has created various problems to protocol designers who have often either introduced imperfect protocols with mistakes or with lack of security arguments, or they have been forced to use much less efficient protocols in order to achieve the required properties. In this work we address this issue by introducing the notion of ``protocol portability,'' a property that identifies input and verifier state distributions under which a protocol becomes a ZKP when called as a subroutine in a sequential execution of a larger application. We then concentrate on the very efficient and heavily employed ``Generalized Schnorr Proofs'' (GSP) and identify the portability of such protocols. We also point to previous protocol weaknesses and errors that have been made in numerous applications throughout the years, due to employment of GSP instances while lacking the notion of portability (primarily in the case of unknown order groups). This demonstrates that cryptographic application designers who care about efficiency need to consider our notion carefully. We provide a compact specification language for GSP protocols that protocol designers can employ. Our specification language is consistent with the ad-hoc notation that is currently widely used and it offers automatic derivation of the proof protocol while dictating its portability (i.e., the proper initial state and inputs) and its security guarantees. Thus, our language specifications can be used modularly in designs and proofs. This assures that the protocol implementation can indeed be used as a subroutine that is ZKP in its context. Finally, as a second alternative to designers wishing to use GSPs, we present a modification of GSP protocols that is unconditionally portable (i.e., ZKP) and is still quite efficient. Our constructions are the first such protocols proven secure in the standard model (while the previously known efficient constructions relied on the Random Oracle model).

In this paper we construct efficient secure protocols for \emph{set intersection} and \emph{pattern matching}. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that are based on polynomials. In addition to the above, we also use secure pseudorandom function evaluation in order to achieve secure pattern matching. In this case, we utilize specific properties of the Naor-Reingold pseudorandom function in order to achieve high efficiency. Our results are presented in two adversary models. Our protocol for secure pattern matching and one of our protocols for set intersection achieve security against \emph{malicious adversaries} under a relaxed definition where one corruption case is simulatable and for the other only privacy (formalized through indistinguishability) is guaranteed. We also present a protocol for set intersection that is fully simulatable in the model of covert adversaries. Loosely speaking, this means that a malicious adversary can cheat, but will then be caught with good probability.

With increased use of passive RFID tags, the need for secure lightweight identification protocols arose. HB+ is one such protocol, which was proven secure in the detection-based model, but shown breakable by man-in-the-middle attacks. Trusted-HB is a variant of HB+, specifically designed to resist man-in-the-middle attacks. In this paper, we discuss several weaknesses of Trusted-HB, show that the formal security proof provided by its designers is incorrect, and demonstrate how to break it in realistic scenarios.

Proofs of Retrievability (PoR), introduced by Juels and Kaliski, allow the client to store a file $F$ on an untrusted server, and later run an efficient audit protocol in which the server proves that it (still) possesses the client's data. Constructions of PoR schemes attempt to minimize the client and server storage, the communication complexity of an audit, and even the number of file-blocks accessed by the server during the audit. In this work, we identify several different variants of the problem (such as bounded-use vs. unbounded-use, knowledge-soundness vs. information-soundness), and giving nearly optimal PoR schemes for each of these variants. Our constructions either improve (and generalize) the prior PoR constructions, or give the first known PoR schemes with the required properties. In particular, we \begin{itemize} \item Formally prove the security of an (optimized) variant of the bounded-use scheme of Juels and Kaliski~\cite{JuelsK07}, without making any simplifying assumptions on the behavior of the adversary. \item Build the first unbounded-use PoR scheme where the communication complexity is linear in the security parameter and which does not rely on Random Oracles, resolving an open question of Shacham and Waters~\cite{ShachamW08}. \item Build the first bounded-use scheme with {\em information-theoretic} security. \end{itemize} The main insight of our work comes from a simple connection between PoR schemes and the notion of {\em hardness amplification}, extensively studied in complexity theory. In particular, our improvements come from first abstracting a purely information-theoretic notion of {\em PoR codes}, and then building nearly optimal PoR codes using state-of-the-art tools from coding and complexity theory.

Key insulation (KI) and Intrusion resilience (IR) are methods to protect a user's key against exposure by utilizing periodic communications with an auxiliary helper. But existing work assumes a secure channel between user and helper. If we want to realize KI or IR in practice we must realize this secure channel. This paper looks at the question of how to do this when the communication is over what we are more likely to have in practice, namely a public channel such as the Internet or a wireless network. We explain why this problem is not trivial, introduce models and definitions that capture the desired security in a public channel setting, and provide a complete (and surprising) answer to the question of when KI and IR are possible over a public channel. The information we provide is important to guide practitioners with regard to the usage of KI and IR and also to guide future research in this area.

In this paper we study key exchange protocols in a model where the key exchange takes place between devices with limited displays that can be compared by a human user. If the devices display the same value then the human user is convinced that the key exchange terminated successfully and securely, and if they do not then the user knows that it came under attack. The main result of this paper is a rigorous proof that the numeric comparison mode for device pairing in Bluetooth version 2.1 is secure, under appropriate assumptions regarding the cryptographic functions used. Our proof is in the standard model and in particular does not model any of the functions as random oracles. In order to prove our main result, we present formal definitions for key exchange in this model and show our definition to be equivalent to a simpler definition. This is a useful result of independent interest that facilitates an easier security analysis of protocols in this model.

Recently, Tsai and Liao et al. each proposed a multi-server authentication protocol. They claimed their protocols are secure and can withstand various attacks. But we found some security loopholes in each protocol. We will show the attacks on their schemes.

The success of electronic authentication systems, be it e-ID card systems or Internet authentication systems such as CardSpace, highly depends on the provided level of user-privacy. Thereby, an important requirement is an efficient means for revocation of the authentication credentials. In this paper we consider the problem of revocation for certificate-based privacy-protecting authentication systems. To date, the most efficient solutions for revocation for such systems are based on cryptographic accumulators. Here, an accumulate of all currently valid certificates is published regularly and each user holds a {\em witness} enabling her to prove the validity of her (anonymous) credential while retaining anonymity. Unfortunately, the users' witnesses must be updated at least each time a credential is revoked. For the know solutions, these updates are computationally very expensive for users and/or certificate issuers which is very problematic as revocation is a frequent event as practice shows. In this paper, we propose a new dynamic accumulator scheme based on bilinear maps and show how to apply it to the problem of revocation of anonymous credentials. In the resulting scheme, proving a credential's validity and updating witnesses both come at (virtually) no cost for credential owners and verifiers. In particular, updating a witness requires the issuer to do only one multiplication per addition or revocation of a credential and can also be delegated to untrusted entities from which a user could just retrieve the updated witness. We believe that thereby we provide the first authentication system offering privacy protection suitable for implementation with electronic tokens such as eID cards or drivers' licenses.

At Indocrypt 2005, Viet et al., [22] have proposed an anonymous password-authenticated key exchange (PAKE) protocol and its threshold construction both of which are designed for client's password-based authentication and anonymity against a passive server, who does not deviate the protocol. In this paper, we first point out that their threshold construction is completely insecure against off-line dictionary attacks. For the threshold t > 1, we propose a secure threshold anonymous PAKE (for short, TAP) protocol with the number of clients n upper-bounded, such that n \leq 2 \sqrt{N-1} -1, where N is a dictionary size of passwords. We rigorously prove that the TAP protocol has semantic security of session keys in the random oracle model by showing the reduction to the computational Diffie-Hellman problem. In addition, the TAP protocol provides unconditional anonymity against a passive server. For the threshold t=1, we propose an efficient anonymous PAKE protocol that significantly improves efficiency in terms of computation costs and communication bandwidth compared to the original (not threshold) anonymous PAKE protocol [22].

Secure Evaluation of Private Functions (PF-SFE) allows two parties to compute a private function which is known by one party only on private data of both. It is known that PF-SFE can be reduced to Secure Function Evaluation (SFE) of a Universal Circuit (UC). Previous UC constructions only simulated circuits with gates of $d=2$ inputs while gates with $d>2$ inputs were decomposed into many gates with $2$ inputs which is inefficient for large $d$ as the size of UC heavily depends on the number of gates. We present generalized UC constructions to efficiently simulate any circuit with gates of $d \ge 2$ inputs having efficient circuit representation. Our constructions are non-trivial generalizations of previously known UC constructions. As application we show how to securely evaluate private functions such as neural networks (NN) which are increasingly used in commercial applications. Our provably secure PF-SFE protocol needs only one round in the semi-honest model (or even no online communication at all using non-interactive oblivious transfer) and evaluates a generalized UC that entirely hides the structure of the private NN. This enables applications like privacy-preserving data classification based on private NNs without trusted third party while simultaneously protecting user's data and NN owner's intellectual property.

Collusion-free protocols prevent subliminal communication (i.e., covert channels) between parties running the protocol. In the standard communication model (and assuming the existence of one-way functions), protocols satisfying any reasonable degree of privacy cannot be collusion-free. To circumvent this impossibility result, Alwen et al. recently suggested the mediated model where all communication passes through a mediator; the goal is to design protocols where collusion-freeness is guaranteed as long as the mediator is honest, while standard security guarantees continue to hold if the mediator is dishonest. In this model, they gave constructions of collusion-free protocols for commitments and zero-knowledge proofs in the two-party setting. We strengthen the definition of Alwen et al. in several ways, and resolve the key open questions in this area by showing a collusion-free protocol (in the mediated model) for computing any multi-party functionality.

Oblivious transfer is one of the most important cryptographic primitives, both for theoretical and practical reasons and several protocols were proposed during the years. We provide the first oblivious transfer protocol which is simultaneously optimal on the following list of parameters: Security: it has universal composition. Trust in setup assumptions: only one of the parties needs to trust the setup and some setup is needed for UC security. Trust in computational assumptions: only one of the parties needs to trust a computational assumption. Round complexity: it uses only two rounds. Communication complexity: it communicates O(1) group elements to transfer one out of two group elements. The Big-O notation hides 32, meaning that the communication is probably not optimal, but is essentially optimal in that the overhead is at least constant. Our construction is based on pairings, and we assume the presence of a key registration authority.

It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are non-constant-round. Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is a open problem. This paper focuses on the problem and give a positive answer by presenting two constructions of constant-round (black-box) zero-knowledge proofs of knowledge for the HC (Hamiltonian Cycle) problem. By the recent result of Katz, our second construction which relies on the existence of claw-free functions has optimal round complexity (5-round) assuming the polynomial hierarchy does not collapse.

It is well known that universally composable multiparty computation cannot, in general, be achieved in the standard model without setup assumptions when the adversary can corrupt an arbitrary number of players. One way to get around this problem is by having a \emph{trusted third party} generate some global setup such as a \emph{common reference string (CRS)} or a \emph{public key infrastructure (PKI)}. The recent work of Katz shows that we may instead rely on physical assumptions, and in particular \emph{tamper-proof hardware tokens}. In this paper, we consider a similar but \emph{strictly weaker} physical assumption. We assume that a player (Alice) can \emph{partially isolate} another player (Bob) for a brief portion of the computation and prevent Bob from communicating more than some limited number of bits with the environment. For example, isolation might be achieved by asking Bob to put his functionality on a tamper-proof hardware token and assuming that Alice can prevent this token from communicating to the outside world. Alternatively, Alice may interact with Bob directly but in a special office which she administers and where there are no high-bandwidth communication channels to the outside world. We show that, under \emph{standard} cryptographic assumptions, such physical setup can be used to UC-realize any two party and multiparty computation in the presence of an active and \emph{adaptive} adversary corrupting any number of players. We also consider an alternative scenario, in which there are some trusted third parties but no single such party is trusted by all of the players. This compromise allows us to significantly limit the use of the physical set-up and hence might be preferred in practice.

Currently, there are a lot of authenticated key exchange (AKE) protocols in literature. However, the security proofs of this kind of protocols have been established to be a non-trivial task. The main issue is that without static private key it is difficult for simulator to fully support the SessionKeyReveal and EphemeralKeyReveal queries. Some proposals which have been proven secure either just hold in relatively weak models which do not fully support above-mentioned two queries or make use of the stronger gap assumption. In this paper, using a new technique named twin Diffie-Hellman problem proposed by Cash, Kiltz and Shoup, we present a new AKE protocol based on the computational Diffie-Hellman (CDH) assumption, which is more standard than gap Diffie-Hellman (GDH) assumption. Moreover, our scheme is shown to be secure in strong security definition, the enhanced Canetti-Krawczyk (eCK) model introduced by LaMacchia, Lauter and Mityagin, which better supports the adversaries' queries than previous models.

Sphinx is a cryptographic message format used to relay anonymized messages within a mix network. It is more compact than any comparable scheme, and supports a full set of security features: indistinguishable replies, hiding the path length and relay position, as well as providing unlinkability for each leg of the message's journey over the network. We prove the full cryptographic security of Sphinx in the random oracle model, and we describe how it can be used as an efficient drop-in replacement in deployed remailer systems.

In this paper, we describe two attacks on IEEE 802.11 based wireless LANs. The first attack is an improved key recovery attack on WEP, which reduces the average number of packets an attacker has to intercept to recover the secret key. The second attack is (according to our knowledge) the first practical attack on WPA secured wireless networks, besides launching a dictionary attack when a weak pre shared key (PSK) is used. The attack works if the network is using TKIP to encrypt the traffic. An attacker, who has about 12-15 minutes access to the network is then able to decrypt an ARP request or response and send 7 packets with custom content to network.

A recent research trend, motivated by the massive deployment of RFID technology, looks at cryptographic protocols for securing communication between entities in which al least one of the parties has very limited computing capabilities. In this paper we focus our attention on SASI, a new Ultra-Lightweight RFID Authentication Protocol, designed for providing Strong Authentication and Strong Integrity. The protocol, suitable for passive Tags with limited computational power and storage, involves simple bitwise operations like $and$, $or$, exclusive $or$, modular addition, and cyclic shift operations. It is efficient, fits the hardware constraints, and can be seen as an example of the above research trend. We start by showing some weaknesses in the protocol and, then, we describe how such weaknesses, through a sequence of simple steps, can be used to compute in an efficient way all secret data used for the authentication process. More precisely, we describe three attacks: - A de-synchronisation attack, through which an adversary can break the synchronisation between the RFID Reader and the Tag. - An identity disclosure attack, through which an adversary can compute the identity of the Tag. - A full disclosure attack, which enables an adversary to retrieve all secret data stored in the Tag. Then we present some experimental results we have obtained by running several tests on an implementation of the protocol, in order to evaluate the performance of the proposed attacks. The results confirm that the attacks are effective and efficient.

We study the complexity of securely evaluating arithmetic circuits over finite rings. This question is motivated by natural secure computation tasks. Focusing mainly on the case of {\em two-party} protocols with security against {\em malicious} parties, our main goals are to: (1) only make black-box calls to the ring operations and standard cryptographic primitives, and (2) minimize the number of such black-box calls as well as the communication overhead. We present several solutions which differ in their efficiency, generality, and underlying intractability assumptions. These include: \begin{itemize} \item An {\em unconditionally secure} protocol in the OT-hybrid model which makes a black-box use of an arbitrary ring $R$, but where the number of ring operations grows linearly with (an upper bound on) $\log|R|$. \item Computationally secure protocols in the OT-hybrid model which make a black-box use of an underlying ring, and in which the numberof ring operations does not grow with the ring size. The protocols rely on variants of previous intractability assumptions related to linear codes. In the most efficient instance of these protocols, applied to a suitable class of fields, the (amortized) communication cost is a constant number of field elements per multiplication gate and the computational cost is dominated by $O(\log k)$ field operations per gate, where$k$ is a security parameter. These results extend a previous approach of Naor and Pinkas for secure polynomial evaluation ({\em SIAM J.\ Comput.}, 35(5), 2006). \item A protocol for the rings $\mathbb{Z}_m=\mathbb{Z}/m\mathbb{Z}$ which only makes a black-box use of a homomorphic encryption scheme. When $m$ is prime, the (amortized) number of calls to the encryption scheme for each gate of the circuit is constant. \end{itemize} All of our protocols are in fact {\em UC-secure} in the OT-hybrid model and can be generalized to {\em multiparty} computation with an arbitrary number of malicious parties.

We are interested in this problem: a verifier, with a small and reliable storage, wants to periodically check whether a remote server is keeping a large file $\mathbf{x}$. A dishonest server, by adapting the challenges and responses, tries to discard partial information of $\mathbf{x}$ and yet evades detection. Besides the security requirements, there are considerations on communication, storage size and computation time. Juels et al. \cite{Pors} gave a security model for {\em Proof of Retrievability} ({\POR}) system. The model imposes a requirement that the original ${\bf x}$ can be recovered from multiple challenges-responses. Such requirement is not necessary in our problem. Hence, we propose an alternative security model for {\em Remote Integrity Check} ({\RIC}). We study a few schemes and analyze their efficiency and security. In particular, we prove the security of a proposed scheme {\simplePIR}. This scheme can be deployed as a {\POR} system and it also serves as an example of an effective {\POR} system whose ``extraction'' is not verifiable. We also propose a combination of the RSA-based scheme by Filho et al. \cite{DDPs} and the ECC-based authenticator by Naor et al. \cite{complex_memcheck}, which achieves good asymptotic performance. This scheme is not a {\POR} system and seems to be a secure {\RIC}. In-so-far, all schemes that have been proven secure can also be adopted as {\POR} systems. This brings out the question of whether there are fundamental differences between the two models. To highlight the differences, we introduce a notion, {\em trap-door compression}, that captures a property on compressibility.

We present Scratch, Click & Vote voting scheme, which is a modification of the Punchscan and ThreeBallot systems. The scheme is end-to-end veryfiable and allows for voting over the Internet. Security against malicious hardware and software used by a voter %TT is due to the fact that a voter's computer does not get any knowledge about the voter's choice. Moreover, it can change successfully a voter's ballot only with a small probability. As a side result, we present a modification of the ThreeBallot that eliminates Strauss'-like attacks on this scheme.

Recently, Eschenauer and Gligor [EG02] proposed a model (the EG-model) for random key pre-distribution in distributed sensor networks (DSN) that allows sensors to establish private shared keys. In this model, each sensor is randomly assigned a set of keys, called a key-ring, from a secret key-pool. Two nodes can communicate securely by using a shared key (direct key) or via a chain of shared keys (key-path). The authors show how the key-ring size can be chosen so that nodes are guaranteed to be linked either by direct keys or by key-paths. Security of this system is proven for an eavesdropping (passive) adversary. In this paper we assume the same key pre-distribution set-up but consider a semi-honest adversary. Semi-honest adversaries are privacy adversaries that have access to a fraction of the keys in the key pool, the compromised keys, but are otherwise passive, in the sense that they do not cause nodes to deviate from protocol executions (to remain undetectable). Since they can decrypt messages secured by key-paths with compromised keys, the security guarantees of the EG model break down. We revisit the security of key establishment in the presence of such adversaries and make a number of contributions. First, we show that it is possible to choose the size of the key-rings so that any two nodes can exchange a private key securely in the presence of a semi-honest adversary. Second, we give a protocol that achieves this guarantee and prove its security. Third, we introduce a new efficiency parameter for the EG-model that allows the protocol designer to trade-off the communication required for key establishment with the key-ring size. Finally, we propose a concrete key establishment protocol (based on the DSR protocol) that guarantees security in the presence of a semi-honest adversary.

Zero-knowledge set is a primitive introduced by Micali, Rabin, and Kilian (FOCS 2003) which enables a prover to commit a set to a verifier, without revealing even the size of the set. Later the prover can give zero-knowledge proofs to convince the verifier of membership/non-membership of elements in/not in the committed set. We present a new primitive called {\em Statistically Hiding Sets} (SHS), similar to zero-knowledge sets, but providing an information theoretic hiding guarantee, rather than one based on efficient simulation. This is comparable to relaxing zero-knowledge proofs to {\em witness independent proofs}. More precisely, we continue to use the simulation paradigm for our definition, but do not require the simulator (nor the distinguisher) to be efficient. We present a new scheme for statistically hiding sets, which does not fit into the ``Merkle-tree/mercurial-commitment'' paradigm that has been used for {\em all} zero-knowledge set constructions so far. This not only provides efficiency gains compared to the best schemes in that paradigm, but also lets us provide {\em statistical} hiding; previous approaches required the prover to maintain growing amounts of state with each new proof for this. Our construction is based on an algebraic tool called {\em trapdoor DDH groups} (\tdg), introduced recently by Dent and Galbraith (ANTS 2006). Ours is perhaps the first non-trivial application of this tool. However the specific hardness assumptions we associate with \tdg are different, and of a strong nature --- strong RSA and a knowledge-of-exponent assumption. Our new knowledge-of-exponent assumption may be of independent interest. We prove this assumption in the generic group model.

Information aggregation is an important operation in wireless sensor networks executed for the purpose of monitoring and reporting of the environmental data. Due to the performance constraints of sensor nodes the in-network form of the aggregation is especially attractive since it allows to save expensive resources during the frequent network queries. Easy accessibility of networks and nodes and almost no physical protection against corruptions arise high challenges on the security of the aggregation process. Especially, protection against attacks aiming to falsify the aggregated result is considered to be of prime importance. In this paper we propose a novel security model for the aggregation process based on the well-established cryptographic techniques, focusing on the scenario with the single aggregator node. In order to show soundness and feasibility of our definitions we describe a generic practical approach that achieves security against node corruptions during the aggregation process in a provable cryptographic way based solely on the symmetric cryptographic primitives. To the best of our knowledge this is the first paper which aims to combine the paradigm of provable security in the cryptographic sense with the task of information aggregation in WSNs.

Although cryptographic protocols are typically analyzed in isolation, they are used in combinations. If a protocol was analyzed alone and shown to meet some security goals, will it still meet those goals when executed together with a second protocol? While not every choice of a second protocol can preserve the goals, there are syntactic criteria for the second protocol that ensure they will be preserved. Our main result strengthens previously known criteria. Our method has three main elements. First, a language L(\Pi) in classical logic describes executions of each protocol \Pi, and expresses its security goals. Strand spaces provide the models for L(\Pi). Second, the strand space ``authentication test'' principles suggest our syntactic criterion for security goals to be preserved. Third, certain homomorphisms among models for L(\Pi) preserve the truth of formulas of the syntactic form that security goals take. This provides a way to extract -- from a counterexample to a goal that uses both protocols -- a counterexample using only the first protocol. This essentially model-theoretic technique studies a syntactically defined set of formulas using the homomorphisms among their models. It appears to be novel for protocol analysis.

Secure multiparty computation (MPC) allows a set of parties to securely evaluate any agreed function of their inputs, even when up to $t$ of the $n$ parties are faulty. Protocols for synchronous networks (where every sent message is assumed to arrive within a constant time) tolerate up to $t<n/2$ faulty parties, whereas in the more realistic asynchronous setting (with no \emph{a priory} information on maximal message delay) only security against $t<n/3$ is possible. We present the first protocol that achieves security against $t<n/2$ without assuming a fully synchronous network. Actually our protocol guarantees security against any faulty minority in an \emph{almost asynchronous} network, i.e. in a network with one single round of synchronous broadcast (followed by a fully asynchronous communication). Furthermore our protocol takes inputs of all parties (in a fully asynchronous network only inputs of $n-t$ parties can be guaranteed), and so achieves everything that is possible in synchronous networks (but impossible in fully asynchronous networks) at the price of just one synchronous broadcast round. As tools for our protocol we introduce the notions of \emph{almost non-interactive verifiable secret-sharing} and \emph{almost non-interactive zero-knowledge proof of knowledge}, which are of independent interest as they can serve as efficient replacements for fully non-interactive verifiable secret-sharing and fully non-interactive zero-knowledge proof of knowledge.

In Shamir's $(k,n)$-threshold secret sharing scheme (threshold scheme), a heavy computational cost is required to make $n$ shares and recover the secret. As a solution to this problem, several fast threshold schemes have been proposed. This paper proposes a new (k,n)$-threshold scheme. For the purpose to realize high performance, the proposed scheme uses just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret. We prove that the proposed scheme is a {\it perfect} secret sharing scheme, every combination of $k$ or more participants can recover the secret, but every group of less than $k$ participants cannot obtain any information about the secret. Moreover, we show that the proposed scheme is an {\it ideal} secret sharing scheme similar to Shamir's scheme, which is a {\it perfect} scheme such that every bit-size of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's. Furthermore, from the aspect of both computational cost and storage usage, we also introduce how to extend the proposed scheme to a new $(k,L,n)$-threshold {\it ramp} scheme similar to the existing {\it ramp} scheme based on Shamir's scheme.

A new class of attacks against authentication and authenticated key establishment protocols is described, which we call parsing ambiguity attacks. If appropriate precautions are not deployed, these attacks apply to a very wide range of such protocols, including those specified in a number of international standards. Three example attacks are described in detail, and possible generalisations are also outlined. Finally, possible countermeasures are given, as are recommendations for modifications to the relevant standards.

We consider enhancing a sealed-bid single-item auction with \emph{privacy} concerns, our assumption being that bidders primarily care about monetary payoff and secondarily worry about exposing information about their type to other players and learning information about other players' types. To treat privacy explicitly within the game theoretic context, we put forward a novel \emph{hybrid utility} model that considers both fiscal and privacy components in the players' payoffs. We show how to use rational cryptography to approximately implement a given \emph{ex interim} individually strictly rational equilibrium of such an auction (or any game with a winner) without a trusted mediator through a cryptographic protocol that uses only point-to-point authenticated channels between the players. By ``ex interim individually strictly rational'' we mean that, given its type and before making its move, each player has a strictly positive expected utility, i.e., it becomes the winner of the auction with positive probability. By ``approximately implement'' we mean that, under cryptographic assumptions, running the protocol is a computational Nash equilibrium with a payoff profile negligibly close to the original equilibrium. In addition the protocol has the stronger property that no collusion, of any size, can obtain more by deviating in the implementation than by deviating in the ideal mediated setting which the mechanism was designed in. Also, despite the non-symmetric payoffs profile, the protocol always correctly terminates.

Byzantine agreement is typically considered with respect to either a fully synchronous network or a fully asynchronous one. In the synchronous case, either $t+1$ deterministic rounds are necessary in order to achieve Byzantine agreement or at least some expected large constant number of rounds. In this paper we examine the question of how many initial synchronous rounds are required for Byzantine agreement if we allow to switch to asynchronous operation afterwards. Let $n=h+t$ be the number of parties where $h$ are honest and $t$ are corrupted. As the main result we show that, in the model with a public-key infrastructure and signatures, $d+O(1)$ deterministic synchronous rounds are sufficient where $d$ is the minimal integer such that $n-d>3(t-d)$. This improves over the $t+1$ necessary deterministic rounds for almost all cases, and over the exact expected number of rounds in the non-deterministic case for many cases.

S. J. Choi and H. Y. Youn proposed a key pre-distribution scheme for Wireless Sensor Networks based on LU decomposition of symmetric matrix, and later many researchers did works based on this scheme. Nevertheless, we find a mathematical relationship of L and U matrixes decomposed from symmetric matrix, by using which we can calculate one matrix from another regardless of their product -- the key matrix K. This relationship would profoundly harm the secure implementation of this decomposition scheme in the real world. In this paper, we first present and prove the mathematical theorem. Next we give samples to illustrate how to break the networks by using this theorem. Finally, we state the conclusion and some directions for improving the security of the key pre-distribution scheme.

We polish a recent cryptocomputing method of Ishai and Paskin from TCC 2007. More precisely, we show that every function can be cryptocomputed in communication, linear in the product of client's input length and the length of the branching program, and computation, linear in the size of the branching program that computes it. The method is based on the existence of a communication-efficient $(2,1)$-CPIR protocol. We give several nontrivial applications, including: (a) improvement on the communication of Lipmaa's CPIR protocol, (b) a CPIR protocol with log-squared communication and sublinear server-computation by giving a secure function evaluation protocol for Boolean functions with similar performance, (c) a protocol for PIR-writing with low amortized complexity, (d) a selective private function evaluation (SPFE) protocol. We detail one application of SPFE that makes it possible to compute how similar is client's input to an element in server's database, without revealing any information to the server. For SPFE, we design a $4$-message extension of the basic protocol that is efficient for a large class of functionalities.

Recently, M. Hölbl et al. and I. E. Liao et al. each proposed an user authentication protocol. Both claimed that their schemes can withstand password guessing attack. However, T. Xiang et al. pointed out I. E. Liao et al.'s protocol suffers three kinds of attacks, including password guessing attacks. We present an improvement protocol to get rid of password guessing attacks. In this paper, we first point out the security loopholes of M. Hölbl et al.'s protocol and review T. Xiang et al.'s cryptanalysis on I. E. Liao et al.'s protocol. Then, we present the improvements on M. Hölbl et al.'s protocol and I. E. Liao et al.'s protocol, respectively.

Erasing old data and keys is an important tool in cryptographic protocol design. It is useful in many settings, including proactive security, adaptive security, forward security, and intrusion resilience. Protocols for all these settings typically assume the ability to perfectly erase information. Unfortunately, as amply demonstrated in the systems literature, perfect erasures are hard to implement in practice. We propose a model of partial erasures where erasure instructions leave almost all the data erased intact, thus giving the honest players only a limited capability for disposing of old data. Nonetheless, we provide a general compiler that transforms any secure protocol using perfect erasures into one that maintains the same security properties when only partial erasures are available. The key idea is a new redundant representation of secret data which can still be computed on, and yet is rendered useless when partially erased. We prove that any such a compiler must incur a cost in additional storage, and that our compiler is near optimal in terms of its storage overhead.

A constant-round interactive argument is introduced to show existence of a Hamiltonian cycle in a directed graph. Graph is represented with a characteristic polynomial, top coefficient of a verification polynomial is tested to fit the cycle, soundness follows from Schwartz-Zippel lemma.

Although advances in SHA-1 cryptanalysis have been made since the 2005 announcement of a $2^{63}$ attack by Wang et al., the details of the attack have not yet been vetted; this note does just that. Working from Adi Shamir's 2005 CRYPTO rump session presentation of Wang et al.'s work, this note corroborates and presents the differential path and associated conditions for the two-block attack. Although the error analysis for the advanced condition correction technique is not verified, a method is given which yields a two-block collision attack on SHA-1 requiring an estimated $2^{62}$ SHA-1 computations if the original error analysis by Wang et al. is correct.

In this paper, a block-cipher, Integrated Encryption System (IES), to be implemented in bit-level is presented that requires a 252-bit secret key. In IES, there exist at most sixteen rounds to be implemented in cascaded manner. RPSP, TE, RPPO, RPMS, RSBM, RSBP are the six independent block-ciphering protocols, that are integrated to formulate IES. A round is constituted by implementing one of the protocols on the output produced in the preceding round. The process of encryption is an interactive activity, in which the encryption authority is given enough scope of flexibility regarding choice of protocols in any round. However no protocol can be used in more than three rounds. Formation of key is a run-time activity, which gets built with the interactive encryption process proceeds. Results of implementation of all six protocols in cascaded manner have been observed and analyzed. On achieving a satisfactory level of performance in this cascaded implementation, IES and its schematic and operational characteristics have been proposed.

A protocol is introduced to show knowledge of a codeword of Goppa code and Goppa polynomial. Protocol does not disclosure any useful information about the codeword and polynomial coefficients. A related protocol is introduced to show Hamming weight of an error is below a threshold. Protocol does not disclosure codeword and weight of the error. Verifier only uses commitments to codeword components and coefficients while testing validity of statements. Both protocols are honest verifier zero knowledge.

A protocol is introduced to show $K$ copies of a pattern string are embedded is a host string. Commitments to both strings, and to offsets of copies of the pattern in the host is input of Verifier. Protocol does not leak useful information about strings, and is zero knowledge.

It is shown how to use commutative encryption to share a secret. Suppose Alice wants to share a secret with Bob such that Bob cannot decrypt the secret unless a group of trustees agree. It is assumed that Alice, Bob and the trustees communicate over insecure channels. This paper presents a scheme that uses modular exponentiation and does not require key exchange. The security of the scheme rest of the difficulty of the discrete logarithm problem.

A protocol is introduced to show an upper bound for rank of a square matrix

In this paper, we present a new authenticated key exchange(AKE) protocol, called NETS, and prove its security in the extended Canetti-Krawczyk model under the random oracle assumption and the gap Diffie-Hellman(GDH) assumption. Our protocol enjoys a simple and tight security reduction compared to those of HMQV and CMQV without using the Forking Lemma. Each session of the NETS protocol requires only three exponentiations per party, which is comparable to the efficiency of MQV, HMQV and CMQV.

In this paper, we present a new authenticated key exchange(AKE) protocol and prove its security under the random oracle assumption and the computational Diffie-Hellman(CDH) assumption. In the extended Canetti-Krawczyk model, there has been no known AKE protocol based on the CDH assumption. Our protocol, called NAXOS+, is obtained by slightly modifying the NAXOS protocol proposed by LaMacchia, Lauter and Mityagin. We establish a formal security proof of NAXOS+ in the extended Canetti-Krawczyk model using as a main tool the trapdoor test presented by Cash, Kiltz and Shoup.

Cheng and Comley demonstrated type flaw attacks against the key establishment mechanism 12 standardized in ISO/IEC 11770-2:1996. They also proposed enhancements to fix the security flaws in the mechanism. We show that the enhanced version proposed by Cheng and Comley is still vulnerable to type flaw attacks. As well we show that the key establishment mechanism 13 in the above standard is vulnerable to a type flaw attack.

A sensor network key distribution scheme for hierarchical sensor networks was recently proposed by Cheng and Agrawal. A feature of their scheme is that pairwise keys exist between any pair of high-level nodes (which are called cluster heads) and between any (low-level) sensor node and the nearest cluster head. We present two attacks on their scheme. The first attack can be applied for certain parameter sets. If it is applicable, then this attack can result in the compromise of most if not all of the sensor node keys after a small number of cluster heads are compromised. The second attack can always be applied, though it is weaker.

Distance-bounding protocols have been proposed by Brands and Chaum in 1993 in order to detect \emph{relay attacks}, also known as \emph{mafia fraud}. Although the idea has been introduced fifteen years ago, only recently distance-bounding protocols attracted the attention of the researchers. Several new protocols have been proposed the last five years. In this paper, a new secure distance-bounding protocol is presented. It is self-contained and composable with other protocols for example for authentication or key-negotiation. It allows periodically execution and achieves better use of the communication channels by exchanging authenticated nonces. The proposed protocol becomes suitable for wider class of devices, since the resource requirements to the prover are relaxed.

Key agreement is a fundamental security functionality by which pairs of nodes agree on shared keys to be used for protecting their pairwise communications. In this work we study key-agreement schemes that are well-suited for the mobile network environment. Specifically, we describe schemes with the following haracteristics: -- Non-interactive: any two nodes can compute a unique shared secret key without interaction; -- Identity-based: to compute the shared secret key, each node only needs its own secret key and the identity of its peer; -- Hierarchical: the scheme is decentralized through a hierarchy where intermediate nodes in the hierarchy can derive the secret keys for each of its children without any limitations or prior knowledge on the number of such children or their identities; -- Resilient: the scheme is fully resilient against compromise of {\em any number of leaves} in the hierarchy, and of a threshold number of nodes in each of the upper levels of the hierarchy. Several schemes in the literature have three of these four properties, but the schemes in this work are the first to possess all four. This makes them well-suited for environments such as MANETs and tactical networks which are very dynamic, have significant bandwidth and energy constraints, and where many nodes are vulnerable to compromise. We provide rigorous analysis of the proposed schemes and discuss implementations aspects.