Sanitizable signatures authorize semi-trusted sanitizers to modify admissible blocks of a signed message. Most works consider only one sanitizer while those considering multiple sanitizers are limited by their capacity to manage admissible blocks which must be the same for all of them. We study the case where different sanitizers with different roles can be trusted to modify different blocks of the message. We define a model for multi-sanitizer sanitizable signatures which allow managing authorization for each sanitizer independently. We also provide formal definitions of its security properties. We propose two secure generic constructions FSV-k-SAN and IUT-k-SAN with different security properties. We implement both constructions and evaluate their performance on a server and a smartphone.

Authentication on the Internet usually has the drawback of leaking the identity of the users, or at least allowing to trace them from a server to another. Anonymous credentials overcome this issue, by allowing users to reveal the attributes necessary for the authentication, without revealing any other information (in particular not their identity). In this article, we provide a generic framework to construct anonymous credential schemes and use it to give a concrete construction of post-quantum (lattice-based) anonymous credential protocol. Our protocol thus allows for long-term security even when one considers the emergence of quantum computers able to break widely used traditional computational assumptions, such as RSA, the discrete logarithm or Diffie-Hellman. We also give a concrete implementation of our protocol, which is only one order of magnitude slower and bandwidth consuming than previous anonymous credentials that are not post-quantum.

In this paper we introduce Ouroboros, a new family of Key Exchange protocols based on coding theory. The protocols propose a middle ground between the cryptosystems based on$\mathsf {QC}$-$\mathsf {MDPC}$codes, which feature small parameter sizes, but have a security reduction to two problems: the syndrome decoding problem and the indistinguishability of the code, and the HQC protocol, which features bigger parameters but has a security reduction to the syndrome decoding problem only. Ouroboros features a reduction to the syndrome decoding problem with only a small overhead compared to the$\mathsf {QC}$-$\mathsf {MDPC}$based cryptosystems. The approach is based on an ideal structure and also works for the rank metric. This yields a simple, secure and efficient approach for key exchange, the Ouroboros family of protocols. For the Hamming metric we obtain the same type of parameters (and almost the same simple decoding) as for$\mathsf {MDPC}$based cryptosystems, but with a security reduction to decoding random quasi-cyclic codes in the Random Oracle Model. This represents a reduction of up to 38% on the public key size compared to HQC, for the most secure parameters. For the rank metric, we obtain better parameters than for RQC, saving up to 31% on the public key for the most secure set of parameters, using non homogeneous errors in Ouroboros. In this full version, the protocol and decoding algorithm have been slightly improved, additional details are given in the security proof, and the protocol is fully described for the rank metric.

Decision forests are classical models to efficiently make decision on complex inputs with multiple features. While the global structure of the trees or forests is public, sensitive information have to be protected during the evaluation of some client inputs with respect to some server model. Indeed, the comparison thresholds on the server side may have economical value while the client inputs might be critical personal data. In addition, soundness is also important for the receiver. In our case, we will consider the server to be interested in the outcome of the model evaluation so that the client should not be able to bias it. In this paper, we propose a new offline/online protocol between a client and a server with a constant number of rounds in the online phase, with both privacy and soundness against malicious clients.

Designing code-based signatures is both an important and challenging problem. A standard way to tackle it consists to use the Fiat-Shamir heuristic along with an identification scheme that is required to be zero-knowledge. The authors of [1] have highlighted an issue within the zero-knowledge proof of the Veron identification scheme [2]. It turns out that the zero-knowledge proof of the AGS protocol [3] is impacted in a similar way. In this paper, we present a masking technique that solves the aforementioned issue without inducing any performance penalty. We introduce the Masked Veron and Masked AGS protocols that both leverage this masking technique and provide their zero-knowledge proofs. In addition, we present a new technique improving the performances of signatures built from code-based identification schemes subject to the attack described in [4]. The Masked Veron and Masked AGS protocols feature all the existing performance improvements from the literature.

We introduce Anonymous Identity Based Encryption with Traceable Identities, in which we provide a new feature to anonymous identity-based encryption schemes: lifting the anonymity of some specific recipients in necessary situations (such as when they are suspected as criminals). Our primitive allows a tracer, given a tracing key associated to an identity, to filter all the ciphertexts that are sent to this specific identity (and only those). As it is primordial to preserve the privacy of the law-abiding users, the security takes into account the collusion of tracers and corrupted users.

Since the seminal result of Kilian, Oblivious Transfer (OT) has proven to be a fundamental primitive in cryptography. In such a scheme, a user is able to gain access to an element owned by a server, without learning more than this single element, and without the server learning which element the user has accessed. The NIST call for post-quantum encryption and signature schemes has revived the interest for cryptographic protocols based on post-quantum assumptions and the need for secure post-quantum OT schemes. In this paper, we show how to construct an OT scheme based on lattices, from a collision-resistant chameleon hash scheme (CH) and a CCA encryption scheme accepting a smooth projective hash function (SPHF). Note that our scheme does not rely on random oracles and provides UC security against adaptive corruptions assuming reliable erasures.

As messaging applications are becoming increasingly popular, it is of utmost importance to analyze their security and mitigate existing weaknesses. This paper focuses on one of the most acclaimed messaging applications: Signal. Signal is a protocol that provides end-to-end channel security, forward secrecy, and post-compromise security. These features are achieved thanks to a key-ratcheting mechanism that updates the key material at every message. Due to its high security impact, Signal's key-ratcheting has recently been formalized, along with an analysis of its security. In this paper, we revisit Signal, describing some attacks against the original design and proposing SAID: Signal Authenticated and IDentity-based. As the name indicates, our protocol relies on an identity-based setup, which allows us to dispense with Signal's centralized server. We use the identity-based long-term secrets to obtain persistent and explicit authentication, such that SAID achieves higher security guarantees than Signal. We prove the security of SAID not only in the Authenticated Key Exchange (AKE) model (as done by previous work), but also in the Authenticated and Confidential Channel Establishment (ACCE) model, which we adapted and redefined for SAID and asynchronous messaging protocols in general into a model we call identity-based Multistage Asynchronous Messaging (iMAM). We believe our model to be more faithful in particular to the true security of Signal, whose use of the message keys prevents them from achieving the composable guarantee claimed by previous analysis.

Since the seminal work of Diffie and Hellman [19], Non-Interactive Key Exchange (NIKE) has become one of the fundamental problems of modern cryptography, but additional security requirements have led to elaborated ad-hoc constructions, which often lack simplicity in their design. In particular, Identity-Based NIKE is still a major problem with few available constructions, and those ad-hoc constructions do not give a lot of insight on what is required to be able to achieve such a NIKE scheme only based on the identity (and not relying on the public-key setting).

With the emergence of the Internet of things and of electronic home health-care, more and more sensitive signals are transiting over easily accessible wireless networks. It has become an important task to manage to spread alerts on a wireless network at the same time as to hide the nature of these signals, in a secure and efficient way. No one (an adversarial observer or even the node transmitting the signal) should be able to learn whether a signal corresponds to an alert or a normal echo. Blind Coupon Mechanism is a primitive proposed at Asiacrypt 2005 that allows to spread such alerts quietly and quickly. In this paper, we propose to strengthen their security model and we give a concrete solution which is both more secure and more efficient than the protocol originally proposed.

We propose a framework for constructing efficient code-based encryption schemes that do not hide any structure in their public matrix. The framework is in the spirit of the schemes first proposed by Alekhnovich in 2003 and based on the difficulty of decoding random linear codes from random errors of low weight. We depart somewhat from Alekhnovich's approach and propose an encryption scheme based on the difficulty of decoding random quasi-cyclic codes. We propose two new cryptosystems instantiated within our framework: the hamming quasi-cyclic cryptosystem (HQC), based on the hamming metric, and the rank quasi-cyclic cryptosystem (RQC), based on the rank metric. We give a security proof, which reduces the indistinguishability under chosen plaintext attack security of our systems to a decision version of the well-known problem of decoding random families of quasi-cyclic codes for the hamming and rank metrics (the respective QCSD and RQCSD problems). We also provide an analysis of the decryption failure probability of our scheme in the Hamming metric case: for the rank metric there is no decryption failure. Our schemes benefit from a very fast decryption algorithm together with small key sizes of only a few thousand bits. The cryptosystems are very efficient for low encryption rates and are very well suited to key exchange and authentication. Asymptotically, for λ the security parameter, the public key sizes are respectively in O(λ2) for HQC and in O(λ 4/3) for RQC. Practical parameter compares well to the systems based on ring-learning parity with noise or the recent moderate density parity check codes system.

The concept of undeniable signatures has been introduced at Crypto'89 by Chaum and van Antwerpen. It has been revisited several times since, in particular by Jakobsson, Sako and Impagliazzo at Eurocrypt'96 who introduced designated verifier signatures and by Steinfeld, Bull, Wang and Pieprzyk at Asiacrypt'03 who designed universal designated verifier signatures. Behind all those notions lies the idea to produce some kind of signature that can be verified only by a targeted verifier. However the verifier should not be able to convince anyone that the signature is valid. In this paper, we present an efficient way to solve those three problems, under classical assumptions, namely DLin and CDH in the standard model. Once we propose such construction, we generalize our approach to a framework showing how to build efficient ID-based Designated Verifier Signature, in the standard model under classical assumptions.

In this paper we give the first blind signature protocol for code-based cryptography. Our approach is different from the classical original RSA based blind signature scheme, it is done in the spirit of the Fischlin approach [9] which is based on proofs of knowledge. To achieve our goal we consider a new tool for zero-knowledge (ZK) proofs, the Concatenated Stern ZK protocol, which permits to obtain an authentication protocol for concatenated matrices. A signature is then obtained from the usual Fiat-Shamir heuristic. We describe our blind signature protocol for cryptography based on Hamming metric and show how it can be extended to rank based cryptography. The security of our blind protocol is based on the security of a trapdoor function for the syndrome decoding problem: the CFS signature scheme for Hamming distance and on the more recent RankSign protocol for rank metric. We give proofs in the random oracle model (ROM) for our blind signature scheme, which rely on the Syndrome Decoding problem. The parameters we obtain for our protocol are practical for rank metric (200kBytes) for the signature length and 15kBytes for public key size) and a little less practical for Hamming distance.

International audience

Blind signatures allow users to obtain signatures on messages hidden from the signer; moreover, the signer cannot link the resulting message/signature pair to the signing session. This paper presents blind signature schemes, in which the number of interactions between the user and the signer is min imal and whose blind signatures are short. Our schemes are defined over bilinear groups and are proved secure in the common-reference-string model without random oracles and under standard assumptions: CDH and the decision-linear assumption. (We also give variants over asymmetric groups based on similar assumptions.) The blind signatures are Waters signatures, which consist of 2 group elements. Moreover, we instantiate partially blind signatures, where the message consists of a part hidden from the signer and a commonly known public part, and schemes achieving perfect blindness. We propose new variants of blind signatures, such as signer-friendly partially blind signatures, where the public part can be chosen by the signer without prior agreement, 3-party blind signatures, as well as blind signatures on multiple aggregated messages provided by independent sources. We also extend Waters signatures to non-binary alphabets by proving a new result on the underlying hash function.