Search

Until quite recently, anonymous credentials systems were based on public key primitives. A new approach, that relies on algebraic Message Authentication Codes (MACs) in prime-order groups, has recently been introduced by Chase et al. at CCS 2014. They proposed two anonymous credentials systems referred to as “Keyed-Verification Anonymous Credentials (KVAC)” as they require the verifier to know the issuer secret key. Unfortunately, both systems presentation proof, for n unrevealed attributes, is of complexity O(n) in the number of group elements. In this paper, we propose a new KVAC system that provides multi-show unlinkability of credentials and is of complexity O(1) in the number of group elements while being almost as efficient as Microsoft’s U-Prove anonymous credentials system (which does not ensure multi-show unlinkability) and many times faster than IBM’s Idemix. Our credentials are constructed based on a new algebraic MAC scheme which is of independent interest. Through slight modifications on the verifier side, our KVAC system, which is proven secure in the random oracle model, can be easily turned into a public-key credentials system. By implementing it on a standard NFC SIM card, we show its efficiency and suitability for real-world use cases and constrained devices. In particular, a credential presentation, with 3 attributes, can be performed in only 88 ms.

Most electronic payment systems for applications, such as eTicketing and eToll, involve a single entity acting as both merchant and bank. In this paper, we propose an efficient privacy-preserving post-payment eCash system suitable for this particular use case that we refer to, afterwards, as private eCash. To this end, we introduce a new partially blind signature scheme based on a recent Algebraic MAC scheme due to Chase et al. Unlike previous constructions, it allows multiple presentations of the same signature in an unlinkable way. Using it, our system is the first versatile private eCash system where users must only hold a sole reusable token (i.e. a reusable coin spendable to a unique merchant). It also enables identity and token revocations as well as flexible payments. Indeed, our payment tokens are updated in a partially blinded way to collect refunds without invading user’s privacy. By implementing it on a Global Platform compliant SIM card, we show its efficiency and suitability for real-world use cases, even for delay-sensitive applications and on constrained devices as a transaction can be performed in only 205 ms.

In this paper, we introduce new methods for releasing differentially private graphs. Our techniques are based on a new way to distribute noise among edge weights. More precisely, we rely on the addition of noise whose amplitude is edge-calibrated and optimize the distribution of the privacy budget among subsets of edges. The generic privacy framework that we propose can capture most of the privacy notions introduced so far in the literature to release graphs in a differentially private manner. Furthermore, experimental results on real datasets show that our methods outperform the standard existing techniques, in particular in terms of the preservation of utility. In addition, these experiments show that our mechanisms guarantee ϵ-differential privacy for a reasonable level of privacy ϵ, while preserving the spectral information of the input graph.

International audience; The coercion issue in remote electronic voting has always been of particular interest. However, to date, all proposals addressing it either suffer from some shortcomings or are not efficient enough to be used in real world elections. To fill this gap, we propose a new coercion-resistant electronic voting scheme practical for real polls. Our scheme relies on credentials generated thanks to a recent algebraic Message Authentication Code (MAC) scheme due to Chase et al. To enable multiple elections and credentials revocation, we also design a novel sequential aggregate MAC scheme, that is of independent interest. Thanks to it, eligible voters' credentials can be efficiently updated.