Search

International audience; Preserving the privacy of private communication is a fundamental concern of computing addressed by encryption. Information-theoretic reasoning models unconditional security where the strength of the results does not depend on computational hardness or unproven results. Usually the information leaked about the message by the ciphertext is used to measure the privacy of a communication , with perfect secrecy when the leakage is 0. However this is hard to achieve in practice. An alternative measure is the equivocation, intuitively the average number of message/key pairs that could have produced a given cipher-text. We show a theoretical bound on equivocation called max-equivocation and show that this generalizes perfect secrecy when achievable, and provides an alternative measure when perfect secrecy is not achievable. We derive bounds for max-equivocation for symmetric encoder functions and show that max-equivocation is achievable when the entropy of the ciphertext is minimized. We show that max-equivocation easily accounts for key re-use scenarios, and that large keys relative to the message perform very poorly under equivocation. We study encoders under this new perspective, deriving results on their achievable maximal equivocation and showing that some popular approaches such as Latin squares are not optimal. We show how unicity attacks can be naturally modeled, and how relaxing encoder symmetry improves equivocation. We present some algorithms for generating encryption functions that are practical and achieve 90 − 95% of the theoretical best, improving with larger message spaces.

Recent work has presented max-equivocation as a measure of the resistance of a cryptosystem to attacks when the attacker is aware of the encoder function and message distribution. Here we consider the vulnerability of a cryptosystem in the one-try attack scenario when the attacker has incomplete information about the encoder function and message distribution. We show that encoder functions alone yield information to the attacker, and combined with inferable information about the ciphertexts, information about the message distribution can be discovered. We show that the whole encoder function need not be fixed or shared a priori for an effective cryptosystem, and this can be exploited to increase the equivocation over an a priori shared encoder. Finally we present two algorithms that operate in these scenarios and achieve good equivocation results, ExPad that demonstrates the key concepts, and ShortPad that has less overhead than ExPad.

Fail-stop signature (FSS) schemes protect a signer against a forger with unlimited computational power by enabling the signer to provide a proof of forgery, if it occurs. A decade after its invention, there have been several FSS schemes proposed in the literature. Nonetheless, the notion of short FSS scheme has not been addressed yet. Furthermore, the short size in signature schemes has been done mainly with the use of pairings. In this paper, we propose a construction of short FSS scheme based on factorization and discrete logarithm assumption. However, in contrast to the known notion in the literature, our signature scheme does not incorporate any pairing operations. Nonetheless, our scheme is the shortest FSS scheme compared to all existing schemes in the literature that are based on the same assumption. The efficiency of our scheme is comparable to the best known FSS scheme, that is based on the discrete logarithm assumption.

The bounded storage model restricts the memory of an adversary in a cryptographic protocol, rather than restricting its computational power, making information theoretically secure protocols feasible. We present the first protocols for commitment and oblivious transfer in the bounded storage model with errors, i.e., the model where the public random sources available to the two parties are not exactly the same, but instead are only required to have a small Hamming distance between themselves. Commitment and oblivious transfer protocols were known previously only for the error-free variant of the bounded storage model, which is harder to realize.

We implement a specific protocol for bit exchange among card-playing agents in three different state-of-the-art epistemic model checkers and compare the results.

This paper gives the effect of side-information, obtained by the opponent through an initial reconciliation step, on the size of the secret-key that can be distilled safely by subsequent privacy amplification in unconditionally secure secret-key agreement protocol based on smooth entropy, and obtains the size of the secret-key.

An authentication code can be constructed with a family of ε-Almost strong universal (ε-ASU) hash functions, with the index of hash functions as the authentication key. This paper considers the performance of authentication codes from ε-ASU, when the authentication key is only partially secret. We show how to apply the result to privacy amplification against active attacks in the scenario of two independent partially secret strings shared between a sender and a receiver.

Assuming an insecure quantum channel, a quantum computer, and an authenticated classical channel, we propose an unconditionally secure scheme for encrypting classical messages under a shared key, where attempts to eavesdrop the ciphertext can be detected. If no eavesdropping is detected, we can securely re-use the entire key for encrypting new messages. If eavesdropping is detected, we must discard a number of key bits corresponding to the length of the message, but can re-use almost all of the rest. We show this is essentially optimal. Thus, provided the adversary does not interfere (too much) with the quantum channel, we can securely send an arbitrary number of message bits, independently of the length of the initial key. Moreover, the key-recycling mechanism only requires one-bit feedback. While ordinary quantum key distribution with a classical one time pad could be used instead to obtain a similar functionality, this would need more rounds of interaction and more communication.

We present a constant-round unconditional black-box compiler that transforms any ideal (i.e., statistically-hiding and statistically-binding) straight-line extractable commitment scheme, into an extractable and equivocal commitment scheme, therefore yielding to UC-security [9]. We exemplify the usefulness of our compiler by providing two (constant-round) instantiations of ideal straight-line extractable commitment based on (malicious) PUFs [36] and stateless tamper-proof hardware tokens [26], therefore achieving the first unconditionally UC-secure commitment with malicious PUFs and stateless tokens, respectively. Our constructions are secure for adversaries creating arbitrarily malicious stateful PUFs/tokens.Previous results with malicious PUFs used either computational assumptions to achieve UC-secure commitments or were unconditionally secure but only in the indistinguishability sense [36]. Similarly, with stateless tokens, UC-secure commitments are known only under computational assumptions [13,24,15], while the (not UC) unconditional commitment scheme of [23] is secure only in a weaker model in which the adversary is not allowed to create stateful tokens.Besides allowing us to prove feasibility of unconditional UC-security with (malicious) PUFs and stateless tokens, our compiler can be instantiated with any ideal straight-line extractable commitment scheme, thus allowing the use of various setup assumptions which may better fit the application or the technology available.

We give a cheat sensitive protocol for blind universal quantum computation that is efficient in terms of computational and communication resources: it allows one party to perform an arbitrary computation on a second party's quantum computer without revealing either which computation is performed, or its input and output. The first party's computational capabilities can be extremely limited: she must only be able to create and measure single-qubit superposition states. The second party is not required to use measurement-based quantum computation. The protocol requires the (optimal) exchange of $O(J{log }_{2}(N))$ single-qubit states, where $J$ is the computational depth and $N$ is the number of qubits needed for the computation.

There is an ongoing debate about the fundamental security of existing quantum key exchange schemes. This debate indicates not only that there is a problem with security but also that the meanings of perfect, imperfect, conditional and unconditional (information theoretic) security in physically secure key exchange schemes are often misunderstood. It has been shown recently that the use of two pairs of resistors with enhanced Johnsonnoise and a Kirchhoff-loop ‒ i.e., a Kirchhoff-Law-Johnson-Noise (KLJN) protocol ‒ for secure key distribution leads to information theoretic security levels superior to those of today’s quantum key distribution. This issue is becoming particularly timely because of the recent full cracks of practical quantum communicators, as shown in numerous peer-reviewed publications. The KLJN system is briefly surveyed here with discussions about the essential questions such as (i) perfect and imperfect security characteristics of the key distribution, and (ii) how these two types of securities can be unconditional (or information theoretical).

Secure Multi-Party Computation (MPC) providing information-theoretic security allows a set of n parties to securely compute an agreed function over a finite field, even if t parties are under the control of a computationally unbounded active adversary. Asynchronous MPC (AMPC) is an important variant of MPC, which works over an asynchronous network. It is well known that perfect AMPC is possible if and only if t

The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness it is hence a natural question to ask, how much classical randomness we can extract from a quantum system. To tackle this question we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. As the first application, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. As the second application, we resolve the central open question in the noisy-storage model [Wehner et al., PRL 100, 220502 (2008)] by linking security to the quantum capacity of the adversary's storage device., Comment: 6+31 pages, 2 tables, 1 figure, v2: improved converse parameters, typos corrected, new discussion, v3: new references

The uncertainty principle, originally formulated by Heisenberg, dramatically illustrates the difference between classical and quantum mechanics. The principle bounds the uncertainties about the outcomes of two incompatible measurements, such as position and momentum, on a particle. It implies that one cannot predict the outcomes for both possible choices of measurement to arbitrary precision, even if information about the preparation of the particle is available in a classical memory. However, if the particle is prepared entangled with a quantum memory, a device which is likely to soon be available, it is possible to predict the outcomes for both measurement choices precisely. In this work we strengthen the uncertainty principle to incorporate this case, providing a lower bound on the uncertainties which depends on the amount of entanglement between the particle and the quantum memory. We detail the application of our result to witnessing entanglement and to quantum key distribution., 5 pages plus 12 of supplementary information. Updated to match the journal version

In cryptology, secure channels enable the exchange of messages in a confidential andauthenticated manner. The literature of cryptology is rich with proposals and analysis that address the secure communication over public (insecure) channels. In this work, we propose an informa-tion theoretically secure direction for the construction of secure channels. First, we propose a method of achieving unconditionally secure authentication with half the amount of key materialrequired by traditional unconditionally secure message authentication codes (MACs). Key reduction is achieved by utilizing the special structure of the authenticated encryption system. That is,authentication exploits the secrecy of the message to reduce the key material required for authentication. After the description of our method, since key material is the most important concernin unconditionally secure authentication, given the message is encrypted with a perfectly secret one-time pad cipher, we extend our method to achieve unconditionally secure authentication withalmost free key material. That is, we propose a method for unconditionally authenticating arbitrarily long messages with much shorter keys. Finally, we will show how the special structure ofthe authenticated encryption systems can be exploited to achieve provably secure authentication that is very efficient for the authentication of short messages.

In this thesis we have studied different aspects of the novel field of quantum information with continuous variables. The higher efficiency and bandwidth of homodyne detection combined with the easiness of generation and manipulation of Gaussian states makes continuous-variable quantum information a promising and flourishing field of research. This dissertation is divided in two parts. The first part explores two applications of the “photon subtraction” operation; Firstly, a technique to generate highly non-Gaussian single-mode states of light; Secondly, an experimental setup capable of realizing a loophole-free Bell test. The second part of this dissertation develops a detailed analysis of an important family of continuous-variable quantum key distribution protocols, namely those based on Gaussian modulation of Gaussian states./Dans cette thèse on a étudié différents aspects de l'information quantique à variables continues. Les meilleures efficacité et bande passante de la détection homodyne combinées à la simplicité de génération et de manipulation d'états gaussiens rend l'information quantique à variables continues un domaine de recherche très prometteur, qui est actuellement en plein essor. La dissertation est divisée en deux parties. La première explore deux applications de l'opération “soustraction de photon”; en premier lieu on présente une nouvelle technique capable de générer des états mono-modaux de la lumière hautement non-gaussiens; deuxiemement on présente un schéma expérimental capable de réaliser un test de Bell sans faille logique. La deuxième partie de cette dissertation développe une étude détaillée d'une famille très importante de protocoles de distribution quantique de clé à variables continues, ceux basés sur la modulation gaussienne d'états gaussiens., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/published

In this thesis we have studied different aspects of the novel field of quantum information with continuous variables. The higher efficiency and bandwidth of homodyne detection combined with the easiness of generation and manipulation of Gaussian states makes continuous-variable quantum information a promising and flourishing field of research. This dissertation is divided in two parts. The first part explores two applications of the “photon subtraction” operation; Firstly, a technique to generate highly non-Gaussian single-mode states of light; Secondly, an experimental setup capable of realizing a loophole-free Bell test. The second part of this dissertation develops a detailed analysis of an important family of continuous-variable quantum key distribution protocols, namely those based on Gaussian modulation of Gaussian states./Dans cette thèse on a étudié différents aspects de l'information quantique à variables continues. Les meilleures efficacité et bande passante de la détection homodyne combinées à la simplicité de génération et de manipulation d'états gaussiens rend l'information quantique à variables continues un domaine de recherche très prometteur, qui est actuellement en plein essor. La dissertation est divisée en deux parties. La première explore deux applications de l'opération “soustraction de photon”; en premier lieu on présente une nouvelle technique capable de générer des états mono-modaux de la lumière hautement non-gaussiens; deuxiemement on présente un schéma expérimental capable de réaliser un test de Bell sans faille logique. La deuxième partie de cette dissertation développe une étude détaillée d'une famille très importante de protocoles de distribution quantique de clé à variables continues, ceux basés sur la modulation gaussienne d'états gaussiens., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

In this paper we propose an information-theoretic approach to the access control problem in a scenario where a group of users is divided into a number of disjoint classes. The set of rules that specify the information flow between different user classes in the system defines an access control policy. An access control policy can be implemented by using a key assignment scheme, where a trusted central authority (CA) assigns an encryption key and some private information to each class.We consider key assignment schemes where the key assigned to each class is unconditionally secure with respect to an adversary controlling a coalition of classes of a limited size. Our schemes are characterized by a security parameter r, the size of the adversary coalition. We show lower bounds on the size of the private information that each class has to store and on the amount of randomness needed by the CA to set up any key assignment scheme. Finally, we propose some optimal constructions for unconditionally secure key assignment schemes.

Journal of Cryptology, 18 (3), ISSN:1432-1378, ISSN:0933-2790

Quantum key growing, often called quantum cryptography or quantum key distribution, is a method using some properties of quantum mechanics to create a secret shared cryptography key even if an eavesdropper has access to unlimited computational power. A vital but often neglected part of the method is unconditionally secure message authentication. This thesis examines the security aspects of authentication in quantum key growing. Important concepts are formalized as Python program source code, a comparison between quantum key growing and a classical system using trusted couriers is included, and the chain rule of entropy is generalized to any Rényi entropy. Finally and most importantly, a security flaw is identified which makes the probability to eavesdrop on the system undetected approach unity as the system is in use for a long time, and a solution to this problem is provided. ICG QC

Journal of Cryptology, 17 (1), ISSN:1432-1378, ISSN:0933-2790

The topic of this dissertation is Cryptography, and its connections with Coding Theory. Concretely, we make use of techniques from Coding Theory to construct and analyze cryptographic protocols with new and/or enhanced properties. We first focus on Secret Sharing, an important topic with many applications to modern Cryptography, which also forms the common ground for most of the concepts discussed in this thesis. In the flavor we are interested in, a secret-sharing scheme takes as input a secret value, and produces as output n shares in such a way that small enough sets of shares yield no information at all on the secret (privacy), while large enough sets of shares allow to recover the secret (reconstruction). A secret-sharing scheme can thus be seen as a solution to a secure communication problem where a sender Alice is connected to a receiver Bob via n distinct channels, some of which are controlled by an adversary Eve. Alice can use a secret-sharing scheme to communicate a secret message to Bob in such a way that Eve learns no information on the message by eavesdropping on the channels she controls, while Bob can receive the message even if Eve blocks the channels under her control. Our contributions to Secret Sharing concern its connection with Coding Theory; since the two fields share the goal of recovering data from incomplete information, it is not surprising that Secret Sharing and Coding Theory have known a long and fruitful interplay. In particular, Massey initiated a very successful analysis on how to construct and study secret-sharing schemes from error-correcting codes. The downside of this analysis is that the privacy of secret-sharing schemes is estimated in terms of the dual of the underlying code; this can be problematic as it might not be possible to obtain codes with desirable properties that have good duals as well. We circumvent this problem by establishing a new connection between the two fields, where the privacy of secret-sharing schemes is no longer controlled by the dual of the underlying code. This allows us to fully harness the potential of recent code constructions to obtain improved schemes; we exemplify this by means of two applications. First, by making use of linear-time encodable and decodable codes we obtain a family of secret-sharing schemes where both the sharing (computation of the shares from the secret) and the reconstruction can be performed in linear time; for growing privacy and reconstruction thresholds, this was an hitherto open problem. Second, we make use of list-decodable codes to construct robust secret-sharing schemes, i.e., schemes that can recover the secret even if some of the shares are incorrect, except with a small error probability. The family we present optimizes the trade-off between the extra data that needs to be appended to the share to achieve robustness and the error probability in the reconstruction, reaching the best possible value. etc...; Le sujet de cette thèse est la cryptographie et son interconnexions avec la théorie des codes. En particulier, on utilise des techniques issues de la théorie des codes pour construire et analyser des protocoles cryptographiques avec des propriétés nouvelles ou plus avancées. On se concentre d'abord sur le partage de secret ou secret sharing, un sujet important avec de nombreuses applications pour la Cryptographie actuelle. Dans la variante à laquelle on s'intéresse, un schéma de partage de secret reçoit en entrée un élément secret, et renvoie en sortie n parts de telle façon que chaque ensemble de parts de taille suffisamment petite ne donne aucune information sur le secret (confidentialité), tandis que chaque ensemble de taille suffisamment grande permet de reconstituer le secret (reconstruction). Un schéma de partage de secret peut donc être vu comme une solution à un problème de communication où un émetteur Alice est connectée avec un destinataire Bob par n canaux distincts, dont certains sont contrôlés par un adversaire Ève. Alice peut utiliser un schéma de partage de secret pour communiquer un message secret a Bob de telle façon qu'Ève n'apprenne aucune information sur le secret en lisant les données transmises sur les canaux qu'elle contrôle, tandis que Bob peut recevoir le message même si Ève bloque ces dits canaux. Notre contributions au partage de secret concernent ses liens avec la théorie des codes ; comme les deux domaines partagent un même but (récupérer des données à partir d'informations partielles), ce n'est pas surprenant qu'ils aient connu une interaction longue et fertile. Plus précisément, Massey commença une analyse fructueuse à propos de la construction et de l'étude d'un schéma de partage de secret à partir d'un code correcteur. L'inconvénient de cette analyse est que la confidentialité d'un schéma de partage de secret est estimé grâce au dual du code sous-jacent ; cela peut être problématique vu qu'il pourrait ne pas être possible d'obtenir des codes avec des propriétés souhaitables qui aient aussi un bon code dual. On contourne ce problème en établissant une connexion nouvelle entre les deux domaines, telle que la confidentialité d'un schéma de partage de secrets n'est plus contrôlée par le dual du code sous-jacent. Cela nous permet d'exploiter complètement le potentiel de certaines constructions récentes de codes pour obtenir des meilleurs schémas; on illustre ceci avec deux applications. Premièrement, en utilisant des codes avec codage et décodage en temps linéaire on obtient une famille de schémas de partage de secret où le partage (calcul des parts issues du secret) tout comme la reconstruction peuvent s'effectuer en temps linéaire ; pour des seuils de confidentialité et de reconstruction croissants, ceci restait jusqu'à présent un problème ouvert. Deuxièmement, on utilise des codes avec décodage en liste pour construire des schémas de partage de secret robustes, c'est-à-dire des schémas qui peuvent reconstituer le secret même si certaines parts sont incorrectes, sauf avec une petite probabilité d'erreur. etc...