Informations pratiques

Description de la ressource

Résumé

Welcome to the second session. We will talk about the security-reduction proof. The security of a given cryptographic algorithm is reduced to the security of a known hard problem. To prove that a cryptosystem is secure, we select a problem which we know is hard to solve, and we reduce the problem to the security of the cryptosystem. Since the problem is hard to solve, the cryptosystem is hard to break. A security reduction is a proof that an adversary able to attack the scheme is able to solve some presumably hard computational problem, with a similar effort. For the given parameters n, k, let G be the public-key space, K be the apparent public-key space. In the original McEliece scheme G is the set of all generator matrices of a family of binary Goppa codes of length n and dimension k. K is the set of binary matrices of a size (k x n). A distinguisher is a mapping that takes as input a binary matrix of size (k x n), and returns true if the matrix is distinguishable. We define the following sample space, the set of all matrices of size (k x n) uniformly distributed, and we define the event: the set of binary matrices such that the distinguisher returns true, that is the matrices which are distinguishable. The advantage of a distinguisher for the subset D, measures how such a distinguisher could be used as a characterization for G; formally, the probability that the event will occur, minus the probability that the   event happens restricted to the subset G. In other words, it is the probability that the distinguisher detects a matrix from G, from a randomly picked up binary matrix. We will denote the running time of a distinguisher by this formula. An algorithm is a (T, ?)-distinguisher for G against K, if it runs in time at most T, and the advantage for G is greater than ?. So, for given parameters n, k and t, we define this, the message space, this, the apparent public key space, and W the error vector space.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Domaine(s)

• Cette ressource fait partie de
  • 2: McEliece Cryptosystem