Vidéo pédagogique

5.4. Parallel-CFS

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

In this session, I willpresent a variant of the CFS signature scheme calledparallel-CFS. We start from a simple question: whathappens if you try to use two different hash functions andcompute two different CFS signatures? For the signer, you simplytake twice as much computation because you have todo two signatures. And then, the signature istwice longer because you have just to concatenate two signatures. One would assume that forthe attacker it is the same, he simply has to forge two signatures. Well, things are a littlemore complicated than that. What happens when you want to dodecoding one out of many twice in a row? So, you start with a set ofN documents and compute the hashes of these documents tobuild a list of target syndromes. As we have seen, if N =2^(mt/3), one solution is found on average. Then, we canmove on to the second hash function and try to doalso decoding one out of many. The only problem is, youonly have one solution with the first hash function. So,you only have one target document for the secondproblem and you cannot do decoding one out of many anymore. In order to be able to do decoding one out of manytwice in a row, you need to start from a muchlarger list of syndromes. Then, find a set ofsolutions instead of just a single solution and use this setof solutions to find one solution to both hashfunctions at the time. This means that the set oftarget syndromes has to be larger and the complexityof the attack will be larger. We have just seen thatfor the attacker, computing syndrome decoding twice ina row is more complicated. But the same kind ofproblem happens to the legitimate signer when using counters.The first strategy would be first, pick a document D,use the first hash function to compute a signature, thiswill get the value of the counter i; then, use h' tocompute the second signature with a second valueof the counter i'.

Langue :
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
Citer cette ressource:
Inria. (2015, 5 mai). 5.4. Parallel-CFS. [Vidéo]. Canal-U. (Consultée le 20 mai 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème