Contains fulltext : 308843.pdf (Publisher’s version ) (Open Access)

Abstract Blind signatures are a decades-old privacy enhancing technology. It is not always clearly understood that blind signatures actually possess two separate properties: the intuitive understanding that the message to be signed is hidden from the signer, and the fact that the resulting signature is unlinkable (meaning that the signer cannot later tell in which session it created a particular signature). The question is: how exactly should these properties be defined, and can they be defined in a natural way such that they are mutually independent yet together imply blindness? In this paper we study this question, present formal definitions for message indistinguishability and signature unlinkability (and a few more related ones), and study their relationships. We show that these two properties are indeed mutually independent. Unfortunately their union is not equivalent to blindness in what appear to be only pathological cases.

Abstract Attribute-based encryption (ABE) cryptographically implements fine-grained access control on data. As such, data can be stored by an entity that is not necessarily trusted to enforce access control, or an entity that is not even trusted to have access to the plaintext data at all. Instead, access control can be externally enforced by a trusted entity. Additionally, some multi-authority variants of ABE—which do not have a central authority—can effectively and securely implement access control in multiple-domain settings. Furthermore, ABE is the only cryptographic approach to fine-grained access control that does not require an online trusted third party during access requests, and thus provides better availability properties. The actual realization of these theoretical advantages in practice depends on whether current state-of-the-art ABE schemes support the necessary core properties. Much progress has been made in the last two decades in pairing-based ABE schemes, owing to their versatility and efficiency. In fact, it is possible to support most core properties under strong security guarantees, while incurring acceptable storage and computational costs. It is therefore a good time to ask ourselves whether pairing-based ABE has reached its full practical potential. To answer this question, we provide a comprehensive systematized overview of various existing pairing-based ABE schemes and their core properties. We also investigate the relationship between these core properties and real-world access control requirements. We show that a few challenges remain, that must be overcome for ABE to reach its full potential as a mechanism to implement efficient and secure access control in practice.

Privacy-preserving techniques for processing sets of information have attracted the research community’s attention in recent years due to society’s increasing dependency on the availability of data at any time. One of the fundamental problems in set operations is known asPrivate Set Intersection(PSI). The problem requires two parties to compute the intersection between their sets while preserving correctness and privacy. Although several efficient two-party PSI protocols already exist, protocols for PSI in the multi-party setting (MPSI) currently scale poorly with a growing number of parties, even though this applies to many real-life scenarios. This paper fills this gap by proposing two multi-party protocols based on Bloom filters and threshold homomorphic PKEs, which are secure in the semi-honest model. The first protocol is a multi-party PSI, whereas the second provides a more subtle functionality -thresholdmulti-party PSI (T-MPSI) - which outputs items of the server that appear in at least some number of other private sets. The protocols are inspired by the Davidson-Cid protocol based on Bloom filters. We compare our MPSI protocol against Kolesnikovet al., which is among the fastest known MPSI protocols. Our MPSI protocol performs better than Kolesnikovet al.in terms of run time, given that the sets are small and there is a large number of parties. Our T-MPSI protocol performs better than other existing works: the computational and communication complexities are linear in the number of elements in the largest set given a fixed number of colluding parties. We conclude that our MPSI and T-MPSI protocols are practical solutions suitable for emerging use-case scenarios with many parties, where previous solutions did not scale well.

In the private matching problem, a client and a server each hold a set of n input elements. The client wants to privately compute the intersection of these two sets: he learns which elements he has in common with the server (and nothing more), while the server gains no information at all. In certain applications it would be useful to have a fuzzy private matching protocol that reports a match even if two elements are only similar instead of equal. We consider this fuzzy private matching problem, in a semi-honest environment. First we show that the original solution proposed by Freedman et al. is incorrect. Subsequently we present two fuzzy private matching protocols. The first, simple, protocol has a large bit message complexity. The second protocol improves this, but here the client incurs a $O(n)$ factor time complexity.

Unsolicited bulk email (aka. spam ) is a major problem on the Internet. To counter spam, several techniques, ranging from spam filters to mail protocol extensions like hashcash , have been proposed. In this paper we investigate the effectiveness of several spam filtering techniques and technologies. Our analysis was performed by simulating email traffic under different conditions. We show that genetic algorithm based spam filters perform best at server level and naïve Bayesian filters are the most appropriate for filtering at user level.

We introduce a search problem called “mutual search” where k agents, arbitrarily distributed over n sites, are required to locate one another by posing queries of the form “Anybody at site i ?”. We ask for the least number of queries that is necessary and sufficient. For the case of two agents using deterministic protocols, we obtain the following worst-case results: In an oblivious setting (where all pre-planned queries are executed), there is no savings: n -1 queries are required and are sufficient. In a nonoblivious setting, we can exploit the paradigm of “no news is also news” to obtain significant savings: in the synchronous case 0.586 n queries are required; in the asynchronous case 0.896 n queries suffice and a fortiori 0.536 n queries are required; for o(√n) agents using a synchronous deterministic protocol less than n queries suffice; there is a simple randomized protocol for two agents with worst-case expected 0.5 n queries and all radomized protocols require at least 0.25 n worst-case expected queries. The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.

We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies. In most models for routing, for almost all labeled graphs, $\Theta (n^2)$ bits are necessary and sufficient for shortest path routing. By "almost all graphs" we mean the Kolmogorov random graphs which constitute a fraction of 1 - 1/n c of all graphs on n nodes, where c > 0 is an arbitrary fixed constant. There is a model for which the average case lower bound rises to $\Omega(n^2 \log n )$ and another model where the average case upper bound drops to $O(n \log^2 n)$. This clearly exposes the sensitivity of such bounds to the model under consideration. If paths have to be short, but need not be shortest (if the stretch factor may be larger than 1), then much less space is needed on average, even in the more demanding models. Full-information routing requires $\Theta (n^3)$ bits on average. For worst-case static networks we prove an $\Omega(n^2 \log n )$ lower bound for shortest path routing and all stretch factors < 2 in some networks where free relabeling is not allowed.

The optimal space used to represent routing schemes in communication networks is established, both for worst-case static networks and on the average for all static networks. Several factors may influence the cost of representing a routing scheme for a particular network. It is therefore unavoidable that we first describe several reasonable models in which to measure this cost. Failure to do so in the past has obfuscated previous results. We show that, in most models, for almost all graphs \\Theta(n 2 ) bits are necessary and sufficient for shortest path routing. By `almost all graphs' we mean the Kolmogorov random graphs which constitute a fraction of 1 \\Gamma 1=n c of all graphs on n nodes, where c 3 is an arbitrary fixed constant. In contrast, there is a model that rises the average case lower bound to \\Omega\\Gamma n 2 log n) and another model where the average case upper bound drops to O(n log 2 n). This clearly exposes the sensitivity of such bounds to the model under consi...

In the long-lived renaming problem --- a generalization of the classical one-time renaming problem --- n processors with unique names ranging over a source name space f0; : : : ; S \\Gamma 1g repeatedly acquire and release unique names from a (smaller) destination name space f0; : : : ; D \\Gamma 1g. It is assumed that at most k out of n processors concurrently request or hold names. An efficient renaming protocol provides a useful front-end for protocols whose time complexity depends on the size of the name space containing the participating processes. We consider long-lived renaming in the context of asynchronous, shared-memory multiprocessing systems that provide only read and write operations. A renaming protocol is fast iff the time complexity of acquiring and releasing a name is polynomial in k and independent of n and S. We present a wait-free, read/write protocol for long-lived renaming that achieves a destination name space of size O(k 2 ) with time complexity O(k 3 ). If ...