Among the candidates for NIST's post-quantum cryptography standardization project, cryptosystems that rely on Low Rank Parity Check (LRPC) codes have interesting properties, such as a low public key size. However, the key generation phase for these cryptosystems is computationally expensive when done in constant-time, which is a security requirement on the standardization project, making it almost unusable for ephemeral key generation. We present a new constant-time algorithm for key generation on LRPC code-based cryptosystems, that divides the computational costs by four when compared to previous work over ROLLO, one of the NIST candidates. Our improvement consists in changing the way objects of a quotient ring are represented. By switching from a canonical basis to an optimal normal basis, we enable the full potential of the Itoh-Tsuiji algorithm for field inversion.

The Rényi divergence is a measure of closeness of two probability distributions which has found several applications over the last years as an alternative to the statistical distance in lattice-based cryptography. A tight bound has recently been presented for the Rényi divergence of distributions that have a bounded relative error. We show that it can be used to bound the precision requirement in Gaussian sampling to the IEEE 754 floating-point standard double precision for usual lattice-based signature parameters by using a modified cumulative distribution table (CDT), which reduces the memory needed by CDT-based algorithms and, makes their constant-time implementation faster and simpler. Then, we apply this approach to a variable-center variant of the CDT algorithm which occasionally requires the online computation of the cumulative distribution function. As a result, the amount of costly floating-point operations is drastically decreased, which makes the constant-time and cache-resistant variants of this algorithm viable and efficient. Finally, we provide some experimental results indicating that comparing to rejection sampling our approach increases the GPV signature rate by a factor 4 to 8 depending on the security parameter.

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.

Abstract A Private Information Retrieval (PIR) scheme is a protocol in which a user retrieves a record from a database while hiding which from the database administrators. PIR can be achieved using mutuallydistrustful replicated databases, trusted hardware, or cryptography. In this paper we focus on the later setting which is known as single-database computationally- Private Information Retrieval (cPIR). Classic cPIR protocols require that the database server executes an algorithm over all the database content at very low speeds which impairs their usage. In [1], given certain assumptions, realistic at the time, Sion and Carbunar showed that cPIR schemes were not practical and most likely would never be. To this day, this conclusion is widely accepted by researchers and practitioners. Using the paradigm shift introduced by lattice-based cryptography, we show that the conclusion of Sion and Carbunar is not valid anymore: cPIR is of practical value. This is achieved without compromising security, using standard crytosystems, and conservative parameter choices.

In this paper we classify all extremal and s-extremal binary self-dual codes of length 38. There are exactly 2744 extremal self-dual codes, two s-extremal codes, and 1730 s-extremal codes. We obtain our results from the use of a recursive algorithm used in the recent classification of all extremal self-dual codes of length 36, and from a generalization of this recursive algorithm for the shadow. The classification of -extremal codes permits to achieve the classification of all -extremal codes with .

In this paper we present a new 5-pass identification scheme with asymptotic cheating probability ½ based on the syndrome decoding problem. Our protocol is related to the Stern identification scheme but has a reduced communication cost compared to previous code-based zero-knowledge schemes, moreover our scheme permits to obtain a very low size of public key and secret key. The contribution of this paper is twofold, first we propose a variation on the Stern authentication scheme which permits to decrease asymptotically the cheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice) but with less communication. Our solution is based on deriving new challenges from the secret key through cyclic shifts of the initial public key syndrome; a new proof of soundness for this case is given Secondly we propose a new way to deal with hashed commitments in zero-knowledge schemes based on Stern's scheme, so that in terms of communication, on the average, only one hash value is sent rather than two or three. Overall our new scheme has the good features of having a zero-knowledge security proof based on well known hard problem of coding theory, a small size of secret and public key (a few hundred bits), a small calculation complexity, for an overall communication cost of 19kb for authentication (for a 216security) and a signature of size of 93kb (11.5kB) (for security 280), an improvement of 40% compared to previous schemes based on coding theory.

Ring signatures were introduced by Rivest, Shamir, and Tauman in 2001. These signatures allow a signer to anonymously authenticate a message on behalf of a group of his choice. This concept was then extended by Bresson, Stern, and Szydlo into$t$-out-of-$N$(threshold) ring signatures in 2002. We propose in this article a generalization of Stern's code-based identification (and signature) scheme to design a practical$t$-out-of-$N$threshold ring signature scheme. The size of the resulting signatures is in${\cal O}(N)$and does not depend on$t$, contrary to most of the existing protocols. Our scheme is existentially unforgeable under a chosen message attack in the random oracle model assuming the hardness of the minimum distance problem, is unconditionally source hiding, has a very short public key and has an overall complexity in${\cal O}(N)$. This protocol is the first efficient code-based ring signature scheme and the first code-based threshold ring signature scheme. Moreover it has a better complexity than number-theory based schemes which have a complexity in${\cal O}(Nt)$. This paper is an extended version of a paper published in the conference PQCrypto 2008, with complete proofs and definitions.

Private scalar product protocols have proved to be interesting in various applications such as data mining, data integration, trust computing, etc. In 2007, Yao et al. proposed a distributed scalar product protocol with application to privacy-preserving computation of trust [1]. This protocol is split in two phases: an homorphic encryption computation; and a private multi-party summation protocol. The summation protocol has two drawbacks: first, it generates a non-negligible communication overhead; and second, it introduces a security flaw. The contribution of this present paper is two-fold. We first prove that the protocol of [1] is not secure in the semi-honest model by showing that it is not resistant to collusion attacks and we give an example of a collusion attack, with only four participants. Second, we propose to use a superposed sending round as an alternative to the multi-party summation protocol, which results in better security properties and in a reduction of the communication costs. In particular, regarding security, we show that the previous scheme was vulnerable to collusions of three users whereas in our proposal we can t isin [1..n - 1] and define a protocol resisting to collusions of up to t users.

A wireless ad-hoc network is a network which does not use any infrastructure such as access points or base station. Instead, the mobile nodes forward packets to each others, allowing communication among nodes outside wireless transmission range. In this dynamic network, each node is considered as a mobile router but in an energy-conserving manner. This fact makes node an active element in the network which is able of the best and of the worst. Actually, a malicious node can easily disrupt the proper functioning of the routing by simply refusing to forward routing message (misbehavior node), inject the wrong routing packets, modifying others, etc. In this paper, we propose a new routing protocol for wireless ad-hoc network based on multi-agent systems and particularly on ant behavior. The novelty of our protocol relies in the fact that, apparently for the first time, a protocol combines at the same time routing on one side and trust level and reputation between nodes on the other side. This combination permits to increase the security of route establishment. More generally, this protocol opens the door to the use of different agents for obtaining different mixed functionalities, routing and trust level in this paper but also other functionalities like key-distribution.

In this paper we introduce a new probabilistic lattice-based bounded homomorphic encryption scheme. For this scheme the sum of two encrypted messages is the encryption of the sum of two messages and the scheme is able to preserve a vector spave structure of the message. The size of the public key is rather large ap 3 Mb but the encryption and the decryption operations are very fast (of the same speed order than NTRU). The homomorphic operation, i.e. the addition of ciphertexts is dramatically fast compared to homomorphic schemes based on group theory like Paillier or El Gamal.

A PIR scheme is a scheme that allows a user to get an element of a database without giving any information about what part of the database he is interested in. In this paper we present a lattice-based PIR scheme, based on problems close to coding theory problems known to be NP-complete [1], in which the computational cost is a few thousand bit-operations per bit in the database. This improves the protocol computational performance by two orders of magnitude when compared to existing approaches. Our scheme has not as good communication performance as other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.

In this correspondence, we give a new recursive method to classify extremal self-dual codes. As an application we classify all the 41 extremal binary$[36,18,8]$self-dual codes.

Among all the security issues in Voice over IP (VoIP) communications, one of the most difficult to achieve is traffic analysis resistance. Indeed, classical approaches provide a reasonable degree of security but induce large round-trip times that are incompatible with VoIP. In this paper, we describe some of the privacy and security issues derived from traffic analysis in VoIP. We also give an overview of how to provide low-latency VoIP communication with strong resistance to traffic analysis. Finally, we present a server which can provide such resistance to hundreds of users even if the server is compromised.

In this paper, we introduce a simple analytical modeling approach for computing service unavailability due to long response time, for infinite and finite single-server systems as well as for multi-server systems. Closed-form equations of system unavailability based on the conditional response time distributions are derived and sensitivity analyses are carried out to analyze the impact of long response time on service unavailability. The evaluation provides practical quantitative results that can help distributed system developers in design decisions

Current systems providing anonymous communication with low latency are based on relay-networks. Since a single relay can betray its users, it is necessary to use several relays for each communication which distributes the trust among them. This increases the complexity of the protocols as well as the latency, and lowers the throughput to the one of the worst link used. On the other side, such distributed systems are more difficult to attack and can manage large sets of users. In this paper, we proposed a non-distributed approach by presenting the first relay for anonymous communication that cannot betray its users, the pMIX. The scalability for this relay is reduced as the computational cost grows in O(n2) (n being the number of users connected to it) and therefore pMIXes can only be used to form small anonymity sets. In this paper we present different variants for the pMIX that lower the computational cost either to O(ntimesm) or to O(m2) (m being the number of simultaneous communications). This allows a pMIX to deal with larger groups of users having a small amount of simultaneous communications

MIXes are routers that accept packets until their buffers are full, and then send them to the recipients hiding the link (usually through reencryption and rearrangement) between incoming and outgoing packets. MIXes and their variants are used today to provide untraceable communication with systems such as TOR, and they have been a major issue of research on privacy protection for more than twenty years. One of the major problems presented by a MIX is that its administrator is able to link the incoming and outgoing messages transiting through it, and this is the reason why MIXes are almost always organized in networks, according to the model presented by David Chaum (1981). In this paper, we present a protocol that combines these two fields of research, allowing us to create MIXes that have the remarkable property of being unable to link the incoming and outgoing packets transiting through them. This brings the possibility for its users to be untraceable while most of the data of their communication are sent through a single MIX, improving the performance and versatility of anonymizing systems