Catálogo de publicaciones - libros

Anonymous channels are necessary for a multitude of privacy-protecting protocols. Onion routing is probably the best known way to achieve anonymity in practice. However, the cryptographic aspects of onion routing have not been sufficiently explored: no satisfactory definitions of security have been given, and existing constructions have only had ad-hoc security analysis for the most part. We provide a formal definition of onion-routing in the universally composable framework, and also discover a simpler definition (similar to CCA2 security for encryption) that implies security in the UC framework. We then exhibit an efficient and easy to implement construction of an onion routing scheme satisfying this definition.

A simple and efficient shuffling scheme containing two protocols is proposed. Firstly, a prototype, Protocol-1 is designed, which is based on the assumption that the shuffling party cannot find a linear relation of the shuffled messages in polynomial time. As application of Protocol-1 is limited, it is then optimised to Protocol-2, which does not need the assumption. Both protocols are simpler and more efficient than any other shuffling scheme with unlimited permutation. Moreover, they achieve provable correctness and ZK privacy.

We identify and fill some gaps with regard to consistency (the extent to which false positives are produced) for public-key encryption with keyword search (PEKS). We define computational and statistical relaxations of the existing notion of perfect consistency, show that the scheme of [7] is computationally consistent, and provide a new scheme that is statistically consistent. We also provide a transform of an anonymous IBE scheme to a secure PEKS scheme that, unlike the previous one, guarantees consistency. Finally we suggest three extensions of the basic notions considered here, namely anonymous HIBE, public-key encryption with temporary keyword search, and identity-based encryption with keyword search.

In this paper, we consider the problem of private searching on streaming data. We show that in this model we can efficiently implement searching for documents under a secret criteria (such as presence or absence of a hidden combination of hidden keywords) under various cryptographic assumptions. Our results can be viewed in a variety of ways: as a generalization of the notion of a Private Information Retrieval (to the more general queries and to a streaming environment as well as to public-key program obfuscation); as positive results on privacy-preserving datamining; and as a delegation of hidden program computation to other machines.

In many important applications, a collection of mutually distrustful parties must perform private computation over multisets. Each party’s input to the function is his private input multiset. In order to protect these private sets, the players perform privacy-preserving computation; that is, no party learns more information about other parties’ private input sets than what can be deduced from the result. In this paper, we propose efficient techniques for privacy-preserving operations on multisets. By building a framework of multiset operations, employing the mathematical properties of polynomials, we design efficient, secure, and composable methods to enable privacy-preserving computation of the union, intersection, and element reduction operations. We apply these techniques to a wide range of practical problems, achieving more efficient results than those of previous work.

We describe two new public key broadcast encryption systems for stateless receivers. Both systems are fully secure against any number of colluders. In our first construction both ciphertexts and private keys are of constant size (only two group elements), for any subset of receivers. The public key size in this system is linear in the total number of receivers. Our second system is a generalization of the first that provides a tradeoff between ciphertext size and public key size. For example, we achieve a collusion resistant broadcast system for n users where both ciphertexts and public keys are of size $O(\sqrt{N})$ for any subset of receivers. We discuss several applications of these systems.

Broadcast encryption schemes allow a message sender to broadcast an encrypted data so that only legitimate receivers decrypt it. Because of the intrinsic nature of one-to-many communication in broadcasting, transmission length may be of major concern. Several broadcast encryption schemes with good transmission overhead have been proposed. But, these broadcast encryption schemes are not practical since they are greatly sacrificing performance of other efficiency parameters to achieve good performance in transmission length. In this paper we study a generic transformation method which transforms any broadcast encryption scheme to one suited to desired application environments while preserving security. Our transformation reduces computation overhead and/or user storage by slightly increasing transmission overhead of a given broadcast encryption scheme. We provide two transformed instances. The first instance is comparable to the results of the “stratified subset difference (SSD)” technique by Goodrich et al. and firstly achieves $\mathcal{O}(log n)$ storage, $\mathcal{O}(log n)$ computation, and $\mathcal{O}(\frac{log n}{log log n}r)$ transmission, at the same time, where n is the number of users and r is the number of revoked users. The second instance outperforms the “one-way chain based broadcast encryption” of Jho et al., which is the best known scheme achieving less than r transmission length with reasonable communication and storage overhead.

Forgery and counterfeiting are emerging as serious security risks in low-cost pervasive computing devices. These devices lack the computational, storage, power, and communication resources necessary for most cryptographic authentication schemes. Surprisingly, low-cost pervasive devices like Radio Frequency Identification (RFID) tags share similar capabilities with another weak computing device: people. These similarities motivate the adoption of techniques from human-computer security to the pervasive computing setting. This paper analyzes a particular human-to-computer authentication protocol designed by Hopper and Blum (HB), and shows it to be practical for low-cost pervasive devices. We offer an improved, concrete proof of security for the HB protocol against passive adversaries. This paper also offers a new, augmented version of the HB protocol, named HB^ + , that is secure against active adversaries. The HB^ +  protocol is a novel, symmetric authentication protocol with a simple, low-cost implementation. We prove the security of the HB^ +  protocol against active adversaries based on the hardness of the Learning Parity with Noise (LPN) problem.

We propose a way to establish peer-to-peer authenticated communications over an insecure channel by using an extra channel which can authenticate very short strings, e.g. 15 bits.We call this SAS-based authentication as for authentication based on Short Authenticated Strings. The extra channel uses a weak notion of authentication in which strings cannot be forged nor modified, but whose delivery can be maliciously stalled, canceled, or replayed. Our protocol is optimal and relies on an extractable or equivocable commitment scheme. This approach offers an alternative (or complement) to public-key infrastructures, since we no longer need any central authority, and to password-based authenticated key exchange, since we no longer need to establish a confidential password. It can be used to establish secure associations in ad-hoc networks. Applications could be the authentication of a public key (e.g. for SSH or PGP) by users over the telephone, the user-aided pairing of wireless (e.g. Bluetooth) devices, or the restore of secure associations in a disaster case, namely when one remote peer had his long-term keys corrupted.

Error correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, we study the connections between codes, matroids and a special class of secret sharing schemes, namely multiplicative linear secret sharing schemes. Such schemes are known to enable multi-party computation protocols secure against general (non-threshold) adversaries. Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. We prove a property of strongly multiplicative LSSSs that could be useful in solving this problem. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, we show that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, we wonder whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be re-stated in terms of representability of identically self-dual matroids by self-dual codes. We introduce a new concept, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. We prove that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.