In this paper, we study the problem of storing and searching in datasets of variable-length strings, a core primitive in key-value stores, (graph) DBs, and search engines. However, enabling such search capabilities in ORAM scenarios, where data are stored on an honest-but-curious server, remains challenging. We address this problem by proposing a practical design that combines Ring ORAM (Ren et al., 2015) to hide access patterns to outsourced data, with a Patricia trie (Ferragina and Grossi, 1999; Ferragina et al., 2025) for space-efficient search over variable-length strings. The resulting scheme supports search over variable-length string datasets in an ORAM scenario, while retaining efficient storage and access both on the client and the server. We evaluated our scheme on datasets having size up to 273 GB, showing that it supports complex string queries, with only 2 Ring ORAM accesses on the server, incurring a client-server communication cost below 3 MiB, a client memory footprin t of at most 200 MB, and negligible client computation time per query. Although we assume bounded-length strings, the bound is high enough to handle most practical use cases.

Threshold secret sharing enables distributing a message to n parties such that no subset of fewer than t parties can learn the message, whereas any subset of at least t parties can recover the message. Despite being a fundamental primitive, secret sharing still suffers from one significant drawback, where its message reconstruction algorithm is computationally expensive for large privacy thresholds t. In this paper, we aim to address this significant drawback.

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+Ω(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend only on the query inputs and not on the contents of memory. We prove an $Ω(\log m / \log (sw/n\log m))$ static cell probe complexity lower bound for non-adaptive data structures that solve the fundamental dictionary problem where $s$ denotes the space of the data structure in the number of cells and $w$ is the cell size in bits. Our lower bounds hold for all word sizes including the bit probe model ($w = 1$) and are matched by the upper bounds of Boninger et al. [FSTTCS'17]. Our results imply a sharp dichotomy between dictionary data structures with one round of adaptive and at least two rounds of adaptivity. We show that $O(1)$, or $O(\log^{1-ε}(m))$, overhead dictionary constructions are only achievable with at least two rounds of adaptivity. In particular, we show that many $O(1)$ dictionary constructions with two rounds of adaptivity such as cuckoo hashing are optimal in terms of adaptivity. On the other hand, non-adaptive dictionaries must use significantly more overhead. Finally, our results also imply static lower bounds for the non-adaptive predecessor problem. Our static lower bounds peak higher than the previous, best known lower bounds of $Ω(\log m / \log w)$ for the dynamic predecessor problem by Boninger et al. [FSTTCS'17] and Ramamoorthy and Rao [CCC'18] in the natural setting of linear space $s = Θ(n)$ where each point can fit in a single cell $w = Θ(\log m)$. Furthermore, our results are stronger as they apply to the static setting unlike the previous lower bounds that only applied in the dynamic setting.

We study the problem of differentially private (DP) mechanisms for representing sets of size $k$ from a large universe. Our first construction creates $(\epsilon,\delta)$-DP representations with error probability of $1/(e^\epsilon + 1)$ using space at most $1.05 k \epsilon \cdot \log(e)$ bits where the time to construct a representation is $O(k \log(1/\delta))$ while decoding time is $O(\log(1/\delta))$. We also present a second algorithm for pure $\epsilon$-DP representations with the same error using space at most $k \epsilon \cdot \log(e)$ bits, but requiring large decoding times. Our algorithms match the lower bounds on privacy-utility trade-offs (including constants but ignoring $\delta$ factors) and we also present a new space lower bound matching our constructions up to small constant factors. To obtain our results, we design a new approach embedding sets into random linear systems deviating from most prior approaches that inject noise into non-private solutions.

We study encrypted storage schemes where a client outsources data to an untrusted third-party server (such as a cloud storage provider) while maintaining the ability to privately query and dynamically update the data. We focus on encrypted multi-maps (EMMs), a structured encryption (STE) scheme that stores pairs of label and value tuples. EMMs allow queries on labels and return the associated value tuple. As responses are variable-length, EMMs are subject to volume leakage attacks introduced by Kellaris et al. [CCS'16]. To prevent these attacks, volume-hiding EMMs were introduced by Kamara and Moataz [Eurocrypt'19] that hide the label volumes (i.e., the value tuple lengths). As our main contribution, we present the first fully dynamic volume-hiding EMMs that are both asymptotically and concretely efficient. Furthermore, they are simultaneously forward and backward private which are the de-facto standard security notions for dynamic STE schemes. Additionally, we implement our schemes to showcase their concrete efficiency. Our experimental evaluations show that our constructions are able to add dynamicity with minimal to no additional cost compared to the prior best static volume-hiding schemes of Patel et al. [CCS'19].

As part of the responses to the ongoing crypto wars, the notion of Anamorphic Encryption was put forth. The notion allows private communication in spite of a dictator who is engaged in an extreme form of surveillance and or censorship, where it asks for all private keys and knows and may even dictate all messages. The original work pointed out efficient ways to use two known schemes in the anamorphic mode, bypassing the draconian censorship and hiding information from the all-powerful dictator. A question left open was whether these examples are outlier results or whether anamorphic mode is pervasive in existing systems. Here we answer the above question: we develop new techniques, expand the notion, and show that the notion of Anamorphic Cryptography is, in fact, very much prevalent. We first refine the notion of Anamorphic Encryption with respect to the nature of covert communication. Specifically, we distinguish Single-Receiver Encryption for many to one communication, and Multiple-Receiver Encryption for many to many communication within the group of conspiring users. We then show that Anamorphic Encryption can be embedded in the randomness used in the encryption, and we give families of constructions that can be applied to numerous ciphers. In total the families cover classical encryption schemes, some of which in actual use. Among our examples is an anamorphic channel with much higher capacity than the regular channel. In sum, the work shows the very large extent of the potential futility of control and censorship over the use of strong encryption by the dictator (typical for and even stronger than governments engaging in the ongoing crypto-wars): While such limitations obviously hurt utility which encryption typically brings to safety in computing systems, they essentially, are not helping the dictator. While the actual implications of what we show here and what it means in practice require further policy and legal analyses and perspectives, the technical aspects regarding the issues are clearly showing the futility of the war against Cryptography.

We present lower bounds for the static cryptographic data structure problem of single-server private information retrieval (PIR). PIR considers the setting where a server holds a database of n entries and a client wishes to privately retrieve the i-th entry without revealing the index i to the server. In our work, we focus on PIR with preprocessing where an r-bit hint may be computed in a preprocessing stage and stored by the server to be used to perform private queries in expected time t. As our main result, we prove that for any single-server, computationally secure PIR with preprocessing, it must be that tr = Ω(n log n) when r = Ω(log n). If r = O(log n), then we show that t = Ω(n). Our lower bound holds even when the scheme errs with probability 1/n2 and the adversary's distinguishing advantage is 1/n. Our work improves upon the tr = Ω(n) lower bound of Beimel, Ishai and Malkin [JoC'04]. For information-theoretic security, we present a stronger lower bound of t + r = Ω(n) and show a matching construction. Both our lower bounds apply for public-key doubly-efficient PIRs of Boyle, Ishai, Pass and Wootters [TCC'17]. Additionally, our lower bound for information-theoretic security also applies for offline-online PIRs as defined by Corrigan-Gibbs and Kogan [Eurocrypt'20], where the hint is private and only viewed by the client. We prove our lower bounds in a variant of the cell probe model where only accesses to the database are charged cost and computation and accesses to the hint are free. Our main technical contribution is a novel use of the cell sampling technique (also known as the incompressibility technique) used to obtain lower bounds on data structures. In previous works, this technique only leveraged the correctness guarantees to prove lower bounds even when used for cryptographic primitives. Our work combines the cell sampling technique with the privacy guarantees of PIR to construct a powerful, polynomial-time adversary that is critical to proving our higher lower bounds.

Performing searches over encrypted data is a very current and active area. Several efficient solutions have been provided for the single-writer scenario in which all sensitive data originate with one party (the Data Owner ) that encrypts and uploads the data to a public repository. Subsequently, the Data Owner accesses the encrypted data through a Query Processor , which has direct access to the public encrypted repository. Motivated by the recent trend in pervasive data collection, we depart from this model and consider a multi-writer scenario in which the data originate with several and mutually untrusted parties, the Data Sources . In this new scenario, the Data Owner provides public parameters so that each Data Source can add encrypted items to the public encrypted stream; moreover, the Data Owner keeps some related secret information needed to generate tokens so that different Query Sources can decrypt different subsets of the encrypted stream, as specified by corresponding access policies. We propose security model for this problem that we call Secure Selective Stream ( SSS ) and give a secure construction for it based on hard problems in Pairing-Based Cryptography. The cryptographic core of our construction is a new primitive, Amortized Orthogonality Encryption , that is crucial for the efficiency of the proposed implementation for SSS .

Package management systems play an essential role in pursuing systems dependability by ensuring that software is correctly installed and kept up-to-date according to vendor-defined installation policies. Circumventing such policies could make the system unhealthy and insecure and can constitute a serious security threat. In many application scenarios, e.g., distribution of commercial software, the confidentiality of the software must be guaranteed against non-authorized players. In some cases, the installation policy itself is considered a sensitive information, e.g., when it reveals required hardware in military contexts. In this paper we address the problem of strongly enforcing software dependencies in package management systems, to prevent that a malicious user forces the system to install any package despite its requirements are not completely fulfilled. The enforcement is strong in the sense that the encrypted software package cannot be even decrypted if the dependencies are not satisfied. Once a new package is decrypted and installed, our protocol non-interactively updates the key material on the target device. This key update will allow the decryption of further packages that depend on the newly installed one. We further present “policy-hiding” variants of our protocol. Finally we provide an experimental evaluation of the system performance.

Volume leakage has recently been identified as a major threat to the security of cryptographic cloud-based data structures by Kellaris \em et al. [CCS'16] (see also the attacks in Grubbs \em et al. [CCS'18] and Lacharité \em et al. [S&P'18]). In this work, we focus on volume-hiding implementations of \em encrypted multi-maps as first considered by Kamara and Moataz [Eurocrypt'19]. Encrypted multi-maps consist of outsourcing the storage of a multi-map to an untrusted server, such as a cloud storage system, while maintaining the ability to perform private queries. Volume-hiding encrypted multi-maps ensure that the number of responses (volume) for any query remains hidden from the adversarial server. As a result, volume-hiding schemes can prevent leakage attacks that leverage the adversary's knowledge of the number of query responses to compromise privacy. We present both conceptual and algorithmic contributions towards volume-hiding encrypted multi-maps. We introduce the first formal definition of volume-hiding leakage functions. In terms of design, we present the first volume-hiding encrypted multi-map dprfMM whose storage and query complexity are both asymptotically optimal. Furthermore, we experimentally show that our construction is practically efficient. Our server storage is smaller than the best previous construction while we improve query complexity by a factor of 10-16x. In addition, we introduce the notion of differentially private volume-hiding leakage functions which strikes a better, tunable balance between privacy and efficiency. To accompany our new notion, we present a differentially private volume-hiding encrypted multi-map dpMM whose query complexity is the volume of the queried key plus an additional logarithmic factor. This is a significant improvement compared to all previous volume-hiding schemes whose query overhead was the maximum volume of any key. In natural settings, our construction improves the average query overhead by a factor of 150-240x over the previous best volume-hiding construction even when considering small privacy budget of ε=0.2.

Oblivious RAM (ORAM) and private information retrieval (PIR) are classic cryptographic primitives used to hide the access pattern to data whose storage has been outsourced to an untrusted server. Unfortunately, both primitives require considerable overhead compared to plaintext access. For large-scale storage infrastructure with highly frequent access requests, the degradation in response time and the exorbitant increase in resource costs incurred by either ORAM or PIR prevent their usage. In an ideal scenario, a privacy-preserving storage protocols with small overhead would be implemented for these heavily trafficked storage systems to avoid negatively impacting either performance and/or costs. In this work, we study the problem of the best \em storage access privacy that is achievable with only \em small overhead over plaintext access. To answer this question, we consider \em differential privacy access which is a generalization of the \em oblivious access security notion that are considered by ORAM and PIR. Quite surprisingly, we present strong evidence that constant overhead storage schemes may only be achieved with privacy budgets of ε = Ømega(łog n)$. We present asymptotically optimal constructions for differentially private variants of both ORAM and PIR with privacy budgets ε = Θ(łog n)$ with only $O(1)$ overhead. In addition, we consider a more complex storage primitive called key-value storage in which data is indexed by keys from a large universe (as opposed to consecutive integers in ORAM and PIR). We present a differentially private key-value storage scheme with ε = Θ(łog n)$ and $O(łogłog n)$ overhead. This construction uses a new oblivious, two-choice hashing scheme that may be of independent interest.

Private information retrieval (PIR) is a fundamental tool for preserving query privacy when accessing outsourced data. All previous PIR constructions have significant costs preventing widespread use. In this work, we present private stateful information retrieval (PSIR), an extension of PIR, allowing clients to be stateful and maintain information between multiple queries. Our design of the PSIR primitive maintains three important properties of PIR: multiple clients may simultaneously query without complex concurrency primitives, query privacy should be maintained if the server colludes with other clients, and new clients should be able to enroll into the system by exclusively interacting with the server. We present a PSIR framework that reduces an online query to performing one single-server PIR on a sub-linear number of database records. All other operations beyond the single-server PIR consist of cryptographic hashes or plaintext operations. In practice, the dominating costs of resources occur due to the public-key operations involved with PIR. By reducing the input database to PIR, we are able to limit expensive computation and avoid transmitting large ciphertexts. We show that various instantiations of PSIR reduce server CPU by up to 10x and online network costs by up to 10x over the previous best PIR construction.

We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead O(log N log log N) for database of N blocks and for any block size B = Ω(log N) while requiring client memory of only a constant number of memory blocks. Our scheme can be instantiated in the "balls and bins" model in which Goldreich and Ostrovsky [JACM 96] showed an Ω(log N) lower bound for ORAM communication. Our construction follows the hierarchical approach to ORAM design and relies on two main building blocks of independent interest: a new oblivious hash table construction with improved amortized O(log N + poly(log log λ)) communication overhead for security parameter λ and N = poly(λ), assuming its input is randomly shuffled; and a complementary new oblivious random multi-array shuffle construction, which shuffles N blocks of data with communication O(N log log λ + N log N/log λ) when the input has a certain level of entropy. We combine these two primitives to improve the shuffle time in our hierarchical ORAM construction by avoiding heavy oblivious shuffles and leveraging entropy remaining in the merged levels from previous shuffles. As a result, the amortized shuffle cost is asymptotically the same as the lookup complexity in our construction.

We consider Oblivious Shuffling and K-Oblivious Shuffling, a refinement thereof. We provide efficient algorithms for both and discuss their application to the design of Oblivious RAM. The task of K-Oblivious Shuffling is to obliviously shuffle N encrypted blocks that have been randomly allocated on the server in such a way that an adversary learns nothing about the new allocation of blocks. The security guarantee should hold also with respect to an adversary that has learned the initial position of K touched blocks out of the N blocks. The classical notion of Oblivious Shuffling is obtained for K = N. We present a family of algorithms for Oblivious Shuffling. Our first construction, CacheShuffleRoot, is tailored for clients with $O(\sqrt{N})$ blocks of memory and uses $(4+ε)N$ blocks of bandwidth, for every $ε> 0$. CacheShuffleRoot is a 4.5x improvement over previous best known results on practical sizes of N. We also present CacheShuffle that obliviously shuffles using O(S) blocks of client memory with $O(N\log_S N)$ blocks of bandwidth. We then turn to K-Oblivious Shuffling and give algorithms that require 2N + f(K) blocks of bandwidth, for some function f. That is, any extra bandwidth above the 2N lower bound depends solely on K. We present KCacheShuffleBasic that uses O(K) client storage and exactly 2N blocks of bandwidth. For smaller client storage requirements, we show KCacheShuffle, which uses O(S) client storage and requires $2N+(1+ε)O(K\log_S K)$ blocks of bandwidth. Finally, we consider the case in which, in addition to the N blocks, the server stores D dummy blocks whose content is is irrelevant but still their positions must be hidden by the shuffling. For this case, we design algorithm KCacheShuffleDummy that, for N + D blocks and K touched blocks, uses O(K) client storage and $D+(2+ε)N$ blocks of bandwidth.

Performing searches on encrypted data is a very current and active area. Several efficient solutions have been provided for the single-writer scenario in which all sensitive data originates with one party (the Data Owner) that encrypts it and uploads it to a public repository. Subsequently, the Data Owner (or authorized clients, the Query Sources) perform queries on the encrypted data through a Query Processor which has direct access to the public repository. Motivated by the recent trend in pervasive data, we depart from this model and consider a multi-writer scenario in which data originates with several and mutually untrusted parties. In this new scenario the Data Owner provides public parameters so that each piece of the generated data stream can be put into an encrypted stream; moreover, the Data Owner keeps some related secret information needed to generate tokens so that different subscribers can access different subsets of the encrypted stream in clear. We consider the case in which each piece of the data stream consists of a fixed number of cells, organized in columns, and the data owner can authorize subscribers to access individual data based on the content of the columns. Current public-key functional encryption schemes provide a direct and impractical implementation of this scenario. We thus propose a new public-key primitive, Amortized Orthogonality Encryption or AOE, derived from Inner-Product Encryption, that can be used to encrypt each piece of data stream so that ciphertexts have size proportional to the un-encrypted data; moreover, encryption and decryption take time proportional to the number of columns. Previous schemes would give quadratic complexity. We provide a construction of AOE and prove its selective security under standard assumptions in a bilinear setting with prime order group. Using AOE, we implement all the basic operations in our multi-writer scenario in one round of communication. We demonstrate the feasibility and effectiveness of our proposal by providing an implementation of our scenario in C++.

It is often observed that agents tend to imitate the behavior of their neighbors in a social network. This imitating behavior might lead to the strategic decision of adopting a public behavior that differs from what the agent believes is the right one and this can subvert the behavior of the population as a whole. In this paper, we consider the case in which agents express preferences over two alternatives and model social pressure with the majority dynamics: at each step an agent is selected and its preference is replaced by the majority of the preferences of her neighbors. In case of a tie, the agent does not change her current preference. A profile of the agents’ preferences is stable if the each agent’s preference coincides with the preference of at least half of the neighbors (thus, the system is in equilibrium). We ask whether there are network topologies that are robust to social pressure. That is, we ask whether there are graphs in which the majority of preferences in an initial profile $${\mathbf {s}}$$ always coincides with the majority of the preference in all stable profiles reachable from $${\mathbf {s}}$$ . We completely characterize the graphs with this robustness property by showing that this is possible only if the graph has no edge or is a clique or very close to a clique. In other words, except for this handful of graphs, every graph admits at least one initial profile of preferences in which the majority dynamics can subvert the initial majority. We also show that deciding whether a graph admits a minority that becomes majority is NP-hard when the minority size is at most 1 / 4-th of the social network size.

Logit Dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g., exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. In several cases it happens that on a time-scale shorter than mixing time the chain is “quasi-stationary”, meaning that it stays close to some small set of the state space, while in a time-scale multiple of the mixing time it jumps from one quasi-stationary configuration to another; this phenomenon is usually called “metastability”. In this paper we give a quantitative definition of “metastable probability distributions” for a Markov chain and we study the metastability of the Logit dynamics for some classes of coordination games. In particular, we study no-risk-dominant coordination games on the clique (which is equivalent to the well-known Glauber dynamics for the Ising model) and coordination games on a ring (both the risk-dominant and no-risk-dominant case). We also describe a simple “artificial” game that highlights the distinctive features of our metastability notion based on distributions.

We present the first general bounds on the mixing time of logit dynamics for wide classes of strategic games. The logit dynamics describes the behaviour of a complex system whose individual components act "selfishly" and keep responding according to some partial ("noisy") knowledge of the system. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that, for potential games, the mixing time is upper and lower bounded by an "exponential" in the inverse of the noise and in the maximum potential difference. Instead, for games with dominant strategies, the mixing time cannot grow arbitrarily with the inverse of the noise. Finally, we refine our analysis for a subclass of potential games called "graphical" coordination games and we give evidence that the mixing time strongly depends on the structure of the underlying graph. Games in this class have been previously studied in Physics and, more recently, in Computer Science in the context of diffusion of new technologies.

We propose efficient schemes for information-theoretically secure key exchange in the Bounded Storage Model (BSM), where the adversary is assumed to have limited storage. Our schemes generate a secret One Time Pad (OTP) shared by the sender and the receiver,from a large number of public random bits produced by the sender or by an external source. Our schemes initially generate a small number of shared secret bits, using known techniques. We introduce a new method to expand a small number of shared bits to a much longer, shared key.

In this paper we propose a fully decentralized approach for recommending new contacts in the social network of mobile phone users. With respect to existing solutions, our approach is characterized by some distinguishing features. In particular, the application we propose does not assume any centralized coordination: it transparently collects and processes user information that is accessible in any mobile phone, such as the log of calls, the list of contacts or the inbox/outbox of short messages and exchanges it with other users. This information is used to recommend new friendships to other users. Furthermore, the information needed to perform recommendation is collected and exchanged between users in a privacy preserving way. Finally, information necessary to implement the application is exchanged transparently and opportunistically, by using the residual space in standard short messages occasionally exchanged between users. As a consequence, we do not ask users to change their habits in using SMS.

We investigate structural properties of interactive perfect zero-knowledge (PZK) proofs. Specifically, we look into the closure properties of PZK languages under monotone boolean formula composition. This gives rise to new protocol techniques. We show that interactive PZK for random self-reducible (RSR) (and for co-RSR) languages is closed under monotone boolean formula composition. Namely, we present PZK proofs for monotone boolean formulae whose atoms are statements about membership in a PZK language which is RSR (or whose complement is RSR). We also discuss extensions, recent applications, and generalizations of the techniques.

We consider general resource assignment games involvingselfish users/agentsin which users compete for resources and try to be assigned to those which maximize their own benefits (e.g., try to route their traffic through links which minimize the latency of their own traffic). We propose and study amechanism designapproach in which an allocation mechanism assigns users to resources and charges the users for using the resources so as to induce each user totruthfullyreport a private piece of information he/she holds (e.g., how much traffic he/she needs to transmit). This information is crucial for computing optimal (or close to optimal) allocations and an agent could misreport his/her information to induce the underlying allocation algorithm to output a solution which he/she likes more (e.g., which assigns better resources to him/her). For our resource allocation problems, we give analgorithmic characterizationof the solutions for which truth-telling is a Nash equilibrium. A natural application of these results is to a scheduling/routing problem which is the mechanism design counterpart of the selfish routing game of Koutsoupias and Papadimitriou [1999]: Each selfish user wants to route a piece of unsplittable traffic using one ofmlinks of different speeds so as to minimize his/herownlatency. Our mechanism design counterpart can be seen as the problem of schedulingselfish jobson parallel related machines and is the dual of the problem of scheduling (unselfish) jobs on parallelselfish machinesstudied by Archer and Tardos [2001]. Koutsoupias and Papadimitriou studied an “anarchic” scenario in which each user chooses his/her own link, and this may produce Nash equilibria of cost Ω(logm/log logm) times the optimum. Our mechanism design counterpart is a possible way of reducing the effect of selfish behavior via suitable incentives to the agents (i.e., taxes for using the links). We indeed show that in the resulting game, it is possible to guarantee an approximation factor of 8 for any number of links/machines (this solution also works for online settings). However, it remains impossible to guarantee arbitrarily good approximate solutions, even for 2 links/machines and even if the allocation algorithm is allowed superpolynomial time. This result shows that our scheduling problem with selfish jobs is more difficult than the scheduling problem with selfish machines by Archer and Tardos (which admits exact solutions). We also study some generalizations of this basic problem.

In this paper we present a SOAP extension for protecting the privacy of users of a Web service. This extension allows a user to prove to a remote SOAP server to be member of a trusted group without revealing his/her identity. Our extension has been designed as to ensure interoperability among SOAP applications written in different programming languages. We developed also some implementations of our extension using different programming languages. Moreover, we conducted an extensive experimentation of our implementation to prove its feasibility in a real-world context. In sums, our work suggests that privacy can be added to Web services with very little impact on the application developer and without compromising the performance of Web services.

We study the problem of assigning unsplittable traffic to a set of m links so to minimize the maximum link congestion (i.e., the makespan). We consider the case of selfish agents owning pieces of the traffic. In particular, we introduce a variant of the model by Koutsopias and Papadimitriou [1999] in which owners of the traffic cannot directly choose which link to use; instead, the assignment is performed by a scheduler. The agents can manipulate the scheduler by reporting falseinformation regarding the size of each piece of unsplittable traffic.We provide upper and ower bounds on the approximation achievable by mechanisms that induce a Nash equilibrium when all agents report their true values.For the case of each agent owning one job, our positive results for m identical links show the effectiveness of introducing such a scheduler since, in this case, (1+ε)-approximate solutions are guaranteed in polynomial time. In contrast, the result by Koutsopias and Papadimitriou [1999] shows that, without payments and allowing selfish routing, Nash equilibria yield (in the worst case) Ω(log m over log log m)-approximate solutions, even for unitary weighted traffic. When links have different speeds we prove lower and upper bounds on the approximation achievable by a mechanism inducing a Nash equilibrium.Similar approximability results for identical machines have been achieved by Feldman et al. [2003]. However these results do not hold in our setting because their model assumes that the algorithm is provided with the correct traffic weights. For the case of agents owning more than one job, we give mechanisms that achieve constant approximation and prove lower bounds on the approximation ratio that can be achieved by a mechanism.

In this paper we study privacy issues regarding the use of the SSL/TLS protocol and X.509 certificates. Our main attention is placed on subscription-based remote services (e.g., subscription to newspapers and databases) where the service manager charges a flat fee for a period of time independent of the actual number of times the service is requested.We start by pointing out that restricting the access to such services by using X.509 certificates and the SSL/TLS protocol, while preserving the interests of the service managers, neglects the right to privacy of the users.We then propose the concept of a crypto certificate and the Secure and Private Socket Layer protocol (SPSL protocol, in short) and show how they can be used to preserve user privacy and, at the same time, protecting the interests of the service managers. The SPSL protocol only requires the user to have a standard X.509 certificate (with an RSA key) and does not require the user to get any special ad hoc certificate.Finally, we show the viability of the proposed solution by describing a system based on SPSL for secure and private access to subscription-based web services. Our implementation includes an SPSL proxy for a TLS-enabled web client and a module for the Apache web server along with administrative tools for the server side. The system has been developed starting from the implementation of an API for the SPSL protocol that we describe in the paper.

The aim of this paper is two-fold.1) We raise concerns regarding possible violations of user privacy relative to the use of X509 Certi cates and the Transport Layer Security protocol.We stress that this approach to secure network transactions, while preserving the interests of service providers, neglects to consider the right to privacy of the users.2) We propose the concept of a crypto certi cate and the Secure and Private Socket Layer protocol (SPSL protocol, in short) and show their eectiveness in preserving user privacy and, at the same time, protecting the interests of service providers.Focusing on the particular case of web transactions, we describe a system based on SPSL for secure and private web navigation.Our implementation includes an SPSL-proxy for an SSL-enabled web client and a module for the Apache web server along with administrative tools for the server side.The system has been developed starting from the implementation of an API for the SPSL protocol that we d escribe in the paper.Experimental results show t h a t S P S L i s an eective and ecient solution to the problem of privacy in web transaction.The protocol we propose and, consequently, the implementation we describe are fully dynamic and provide an adjustable level of privacy.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.

Identification schemes allow a user to identify herself to a verifying authority in a secure way (i.e., without revealing her secret key). Group identification schemes allow a user to identify herself as a member of a group of users in a secure and anonymous way (i.e., without revealing her identity nor her secret key). Several identification schemes and group identification schemes have been proposed in the literature. In this paper we consider the problem of constructing communication-efficient group identification schemes. Assuming factoring Blum integers is hard, we construct a secure and anonymous group identification scheme having communication complexity \\Theta(m+n), where m is the size of the group and n is the security parameter (previous results achieved complexity \\Theta(mn)). In fact, we show our protocol to be perfect zero-knowledge. We extend this scheme to the case of groups of t ? 1 users and obtain a protocol that improves on the communication complexity of previous ...

In this paper we continue the study of the path length of trees with known fringe as initiated by Klein and Wood (1989) and De Santis and Persiano (1994). We compute the path length of the minimal tree with given number of leaves N and fringe Δ for the case Δ ⩾ N/2. This complements the result of De Santis and Persiano (1994) that studied the case Δ ⩽ N/2. Our methods also yield a linear time algorithm for constructing the minimal tree when Δ ⩾ N/2.

We investigate structural properties of statistical zero knowledge (SZK) both in the interactive and in the non-interactive model. Specifically, we look into the closure properties of SZK languages under monotone logical formula composition. This gives rise to new protocol techniques. We show that interactive SZK for random self reducible languages (RSR) (and for co-RSR) is closed under monotone Boolean operations. Namely, we give SZK proofs for monotone Boolean formulae whose atoms are statements about an SZK language which is RSR (or a complement of RSR). All previously known languages in SZK are in these classes. We then show that if a language L has a non-interactive SZK proof system then honest-verifier interactive SZK proof systems exist for all monotone Boolean formulae whose atoms are statements about the complement of L. We also discuss extensions and generalizations.>

The external path length of a treeT is the sum of the lengths of the paths from the root to each external node. The maximal path length difference, $\Delta $, is the difference between the lengths of the longest and shortest such paths Tight lower and upper bounds are proved on the external path length of binary trees with N external nodes and maximal path length difference $\Delta $ is prescribed. In particular, an upper bound is given that, for each value of $\Delta $, can be exactly achieved for infinitely many values of N. This improves on the previously known upper bound that could only be achieved up to a factor proportional to N. An elementary proof of the known upper bound is also presented as a preliminary result. Moreover, a lower bound is proved that can be exactly achieved for each value of N and $\Delta \leqslant {N / 2}$.

Binary prefix codes with the constraint that each codeword must end with a "1" have been recently introduced by Berger and Yeung (1990). We analyze the performance of such codes by investigating their average codeword length. In particular, we show that a very simple strategy permits the construction of a "1"-ended binary prefix code whose average codeword length is less than H+1 for any discrete source with entropy H. We also prove a tight lower bound on the optimal average codeword length in terms of H and of the minimum letter probability of the source. Finally, we discuss the problem of finding an optimum feasible code.>

A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he 'knows' the proof of a given theorem without revealing any additional information. This is different from a zero-knowledge proof system of membership where the prover convinces the verifier only of the veridicity of the statement. Zero-knowledge proofs of knowledge are very useful tools in the design of secure protocols. Though, the concept of a proof of knowledge is a very subtle one and great care is needed to obtain a satisfying formalization. The authors investigate the concept of a zero-knowledge proof of knowledge with a non-interactive model. Here, the prover and the verifier share a short random string and the only communication allowed is from the prover to the verifier. Although this is a simpler model than the interactive one, still formalizing zero-knowledge proofs of knowledge is a delicate task.>

In this paper we investigate the parallel complexity of the backtrack and branch-and-bound search on the mesh-connected array.We present an Q(~/-) lower bound for the time needed by a randomized algorithm to perform backtrack and branch-and-bound search of a tree of depth d on the ~x fl mesh, even when the depth of the tree is known in advance.The lower bound holds also for algorithms that are allowed to move tree-nodes and create multiple copies of the same tre~node.For the upper bounds we give deterministic algorithms that are within a factor of O(log ~N) from our lower bound.Our algorithms do not make any assumption on the shape of the tree to be searched, do not know the depth of the tree in advance and do not move tree-nodes nor create multiple copies of the same node; also, they guarantee optimal load and only need constant-sized buffers.The best previously known algorithm for backtrack search on the mesh was randomized and required O(d@/ log N) time.Our algorithm for branch-andbound is the first algorithm that performs branch-andbound search on a sparae network.Both the lower and the upper bounds extend to higher dimension meshes.

The codeword lengths of a maximal prefix code with minimum length among those with a given number of codewords differ by at most one. This paper studies the length of the optimal maximal prefix code with a given number N of codewords and the additional constraint that the difference of the lengths of the longest and shortest codeword must be equal to a given parameter Delta . An optimal algorithm is given that, for all N and Delta , constructs an (N, Delta )-MPC of minimum length. Then a lower bound is given for the length of the optimal (N, Delta )-MPC for Delta>

This paper investigates the possibility of disposing of interaction between prover and verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, it is proven that noninteractive zero-knowledge proofs exist for some number-theoretic languages for which no efficient algorithm is known. If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.