Canal-U

5.4. Parallel-CFS

In this session, I will present a variant of the CFS signature scheme called parallel-CFS. We start from a simple question: what happens if you try to use two different hash functions and compute two different CFS signatures? For the signer, you simply take twice as much computation because you have to do two signatures. And then, the signature is twice longer because you have just to concatenate two signatures. One would assume that for the attacker it is the same, he simply has to forge two signatures. Well, things are a little more complicated than that. What happens when you want to do decoding one out of many twice in a row? So, you start with a set of N documents and compute the hashes of these documents to build a list of target syndromes. As we have seen, if N = 2^(mt/3), one solution is found on average. Then, we can move on to the second hash function and try to do also decoding one out of many. The only problem is, you only have one solution with the first hash function. So, you only have one target document for the second problem and you cannot do decoding one out of many anymore. In order to be able to do decoding one out of many twice in a row, you need to start from a much larger list of syndromes. Then, find a set of solutions instead of just a single solution and use this set of solutions to find one solution to both hash functions at the time. This means that the set of target syndromes has to be larger and the complexity of the attack will be larger. We have just seen that for the attacker, computing syndrome decoding twice in a row is more complicated. But the same kind of problem 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, this will get the value of the counter i; then, use h' to compute the second signature with a second value of the counter i'.