Abstract We consider access structures over a set of n participants, defined by a parameter k with $$1 \le k \le n$$ 1 ≤ k ≤ n in the following way: a subset is authorized if it contains at least k consecutive participants. Depending on whether we consider the participants placed in a line (that is, participant 1 is not next to participant n) or in a circle, we obtain two different families, that we call (k, n)-line-consecutive and (k, n)-circle-consecutive access structures, respectively. Such access structures can appear in real-life situations involving distributed cryptography, which makes it more interesting to look for the best secret sharing schemes that can realize them. For both families, we characterize which are the configurations (k, n) that admit ideal secret sharing schemes. For the non-ideal (k, n)-consecutive access structures, we give both upper and lower bounds on the information ratio of the best secret sharing schemes that can realize them. Some of these bounds are obtained after proving relations between the information ratios of access structures in the two considered families.

In this work, we study two essential but apparently contradictory properties of electronic voting systems: coercion resistance (CR) and cast-as-intended verifiability (CAI). Informally, the CR property ensures that a voter cannot prove to anybody else the vote content, which prevents vote selling and voting under duress. The CAI property ensures that a malicious voting device cannot cheat the voter and send to the ballot box an encryption of a voting option different from the one chosen by the voter. In this work, we formalize security definitions capturing both coercion resistance and cast-as-intended verification in settings without secure delivery channels between the election authority and voters. After that, we consider some previously proposed solutions aimed at providing these two properties. For some of them (that we call unsatisfactory solutions) we show why they fail to achieve some of the two properties. We then concentrate on one of the two generic solutions that we call satisfactory: we prove that it satisfies the two proposed definitions and we detail how it can be instantiated in both classical cryptographic (e.g., ElGamal ciphertexts) and quantum-resistant (e.g., using lattice-based cryptosystems) settings.

We consider a real web tool where a bank allows clients to make aggregate queries on the market share of some subset of businesses, in a specific geographic area and all belonging to the same kind of business (e.g. restaurants). A single query is positively answered if a specific basic privacy condition is satisfied by the individual market shares of the involved businesses. A more serious problem appears when multiple queries are allowed: the combination of queries which individually satisfy the basic privacy condition may lead to aggregate information of some subset of businesses which does not satisfy this condition. We give a mathematical formalization of this problem and a possible algorithmic solution, which consists in an off-line phase, run only once, and an on-line phase which is run for each new query. We analyze the complexity of the proposed algorithms and we describe the experimental results that we have obtained with the implementation of such algorithms, run on real data.

In this study, the author formally proves that designing attribute‐based encryption schemes cannot be easier than designing identity‐based encryption schemes. In more detail, they show how an attribute‐based encryption scheme which admits, at least, and policies can be combined with a collision‐resistant hash function to obtain an identity‐based encryption scheme. Even if this result may seem natural, not surprising at all, it has not been explicitly written anywhere, as far as they know. Furthermore, it may be an unknown result for some people: Odelu et al . in 2016 and 2017 have proposed both an attribute‐based encryption scheme in the discrete logarithm setting, without bilinear pairings, and an attribute‐based encryption scheme in the RSA setting, both admitting and policies. If these schemes were secure, then by using the implication proved in this study, one would obtain secure identity‐based encryption schemes in both the RSA and the discrete logarithm settings, without bilinear pairings, which would be a breakthrough in the area. Unfortunately, the author presents here complete attacks of the two schemes proposed by Odelu et al .

The problem of revocation in anonymous authentication systems is subtle and has motivated a lot of work. One of the preferable solutions consists in maintaining either a whitelist LWof non-revoked users or a blacklist LBof revoked users, and then requiring users to additionally prove, when authenticating themselves, that they are in LW(membership proof) or that they are not in LB(non-membership proof). Of course, these additional proofs must not break the anonymity properties of the system, so they must be zero-knowledge proofs, revealing nothing about the identity of the users. In this paper, we focus on the RSA-based setting, and we consider the case of non-membership proofs to blacklists L = LB. The existing solutions for this setting rely on the use of universal dynamic accumulators; the underlying zero-knowledge proofs are bit complicated, and thus their efficiency; although being independent from the size of the blacklist L, seems to be improvable. Peng and Bao already tried to propose simpler and more efficient zero-knowledge proofs for this setting, but we prove in this paper that their protocol is not secure. We fix the problem by designing a new protocol, and formally proving its security properties. We then compare the efficiency of the new zero-knowledge non-membership protocol with that of the protocol, when they are integrated with anonymous authentication systems based on RSA (notably, the IBM product Idemix for anonymous credentials). We discuss for which values of the size k of the blacklist L, one protocol is preferable to the other one, and we propose different ways to combine and implement the two protocols.

Different methods and paradigms to protect data sets containing sensitive statistical information have been proposed and studied. The idea is to publish a perturbed version of the data set that does not leak confidential information, but that still allows users to obtain meaningful statistical values about the original data. The two main paradigms for data set protection are the classical one and the synthetic one. Recently, the possibility of combining the two paradigms, leading to a hybrid paradigm, has been considered. In this work, we first analyze the security of some synthetic and (partially) hybrid methods that have been proposed in the last years, and we conclude that they suffer from a high interval disclosure risk. We then propose the first fully hybrid SDC methods; unfortunately, they also suffer from a quite high interval disclosure risk. To mitigate this, we propose a postprocessing technique that can be applied to any data set protected with a synthetic method, with the goal of reducing its interval disclosure risk. We describe through the paper a set of experiments performed on reference data sets that support our claims.

Comparison functions for sequences (of symbols) are important components of many applications, for example, clustering, data cleansing, and integration. For years, many efforts have been made to improve the performance of such comparison functions. Improvements have been done either at the cost of reducing the accuracy of the comparison, or by compromising certain basic characteristics of the functions, such as the triangular inequality. In this paper, we propose a new distance for sequences of symbols (or strings) called Optimal Symbol Alignment distance (OSA distance, for short). This distance has a very low cost in practice, which makes it a suitable candidate for computing distances in applications with large amounts of (very long) sequences. After providing a mathematical proof that the OSA distance is a real distance, we present some experiments for different scenarios (DNA sequences, record linkage, etc.), showing that the proposed distance outperforms, in terms of execution time and/or accuracy, other well-known comparison functions such as the Edit or Jaro-Winkler distances.

Microaggregation is one of the most employed microdata protection methods. It builds clusters of at least k original records, and then replaces these records with the centroid of the cluster. When the number of attributes of the dataset is large, one usually splits the dataset into smaller blocks of attributes, and then applies microaggregation to each block, successively and independently. In this way, the effect of the noise introduced by microaggregation is reduced, at the cost of losing the k-anonymity property. In this work we show that, besides the specific microaggregation method, the value of the parameter k and the number of blocks in which the dataset is split, there exists another factor which influences the quality of the microaggregation: the way in which the attributes are grouped to form the blocks. When correlated attributes are grouped in the same block, the statistical utility of the protected dataset is higher. In contrast, when correlated attributes are dispersed into different blocks, the achieved anonymity is higher, and so, the disclosure risk is lower. We present quantitative evaluations of such statements based on different experiments on real datasets.

In a distributed key distribution scheme, a set of servers help a set of users in a group to securely obtain a common key. Security means that an adversary who corrupts some servers and some users has no information about the key of a non-corrupted group. In this work we formalize the security analysis of one of such schemes \\cite{DHPS02}, which was not considered in the original proposal. We prove the scheme secure in the random oracle model, assuming that the Decisional Diffie-Hellman problem is hard to solve. We also detail a possible modification of that scheme and the one in \\cite{NPR99}, which allows to prove the security of the schemes without assuming that a specific hash function behaves as a random oracle. As usual, this improvement in the security of the schemes is at the cost of an efficiency loss.

Ad hoc networks are dynamic networks formed "on the fly" by a set of nodes. Achieving secure routing in such networks is a big challenge. Asymmetric signature schemes provide mechanisms for authentication, but may result in inefficient implementations, specially when a large number of nodes is expected. Some of these efficiency problems can be mitigated with the use of aggregate signatures, which reduce the space and computations required for managing many different signatures. In this work we formalize a new concept, aggregate designated verifier signature schemes, which is suitable for authentication of routes in reactive protocols. We propose a specific and efficient scheme with provable security in the random oracle model

Aggregate signatures are a useful primitive which allows aggregation into a single and constant-length signature many signatures on different messages computed by different users. Specific proposals of aggregate signature schemes exist only for PKI-based scenarios. For identity-based scenarios, where public keys of the users are directly derived from their identities, the signature schemes proposed up to now do not seem to allow constant-length aggregation. We provide an intermediate solution to this problem, by designing a new identity-based signature scheme which allows aggregation when the signatures to be aggregated come all from the same signer. The new scheme is deterministic and enjoys some better properties than the previous proposals; for example, it allows detection of a possible corruption of the master entity. We formally prove that the scheme is unforgeable, in the random oracle model, assuming that the Computational Diffie–Hellman problem is hard to solve.