Referee report, round 1: > Dear Tuomas, > > About your paper "One-time Signature Key Boosting: Full Digital Signature > Feature Set without Trapdoor Functions". > > I regret to inform you that I cannot recommend this paper for the Journal > of Cryptology. > > I find the topic of the paper very interesting. Merkle's signature tree is > well-known for its appealing characteristics, however the size of the > signatures is an equally well-known problem. It appears to me that you do > not provide a solution to this problem. A comparison to existing schemes > is not provided, which makes it hard to see the advantages of your scheme > over existing schemes. > > As I see it, you present a signature scheme based on a one-time signature > scheme with the following characteristics: > > a) the leaves of a virtual tree of keys (generated from one key) > are used to sign messages, > b) the nodes in the tree are traversed as a function of the > message to be signed, in such a way that each message is associated > to a unique path in the tree > > The virtual tree has been proposed before, e.g. see HAC page 471. For b) > there are advantages for this approach but also disadvantages. I assume > that if you are to sign a message m, you first hash it to 160 bits and > then you sign this result. In your scheme, the hashed message h(m) > will be associated to a unique path in the tree, so there is no need to > keep track of how many messages have been signed. However, if two > messages m and m' hash to the same value, i.e. h(m)=h(m'), the > signatures of these messages will be identical. This is not the case in > Merkle's signature scheme, where one increments a counter for each > message signed. So I guess for the security of your scheme you must > assume that there are no collisions in the hash function. > What happens if the random oracle produces collisions? > > It is very unclear to me how your scheme compares to Merkle's signature > scheme and other schemes. Such comparison is necessary. > > The description of your scheme (page 4) ought to be more detailed, e.g., > in the second item, how is p_x generated based on p? You should introduce > a symbol for the hash function, e.g. h, then state explicitly how the > private and public keys are generated. > > For the "proof of security" of your scheme you need to be more precise and > detailed. You probably want to show that if one can forge a signature in > your scheme, then the attacker can forge a signature in the underlying > one-time signature scheme (which is (perhaps) assumed infeasible) or the > attacker can break the key boosted scheme. If this is what you want to > show, you should give all details of such a proof. > > Please acknowledge the receipt of this message and let me know your > opinion on my comments. > > Best regards > Lars Knudsen ============================================================================= Commented version. > I find the topic of the paper very interesting. Merkle's signature tree is > well-known for its appealing characteristics, however the size of the > signatures is an equally well-known problem. Merkle signatures are exponential, but ours are polynomial - need to make this point. > It appears to me that you do > not provide a solution to this problem. Yes -- the corresponding Merkle scheme would yield enormous signatures. > A comparison to existing schemes > is not provided, which makes it hard to see the advantages of your scheme > over existing schemes. Right. We need a good comparison of Merkle vs this. > As I see it, you present a signature scheme based on a one-time signature > scheme with the following characteristics: > > a) the leaves of a virtual tree of keys (generated from one key) > are used to sign messages, > b) the nodes in the tree are traversed as a function of the > message to be signed, in such a way that each message is associated > to a unique path in the tree > > The virtual tree has been proposed before, e.g. see HAC page 471. No, it's different as in the tree shown in HAC, as the tree branches consist of *selected* numbers, not numbers generated by random oracle. Jvk referred to something that *did* have the deterministically generated ids. > For b) > there are advantages for this approach but also disadvantages. I assume > that if you are to sign a message m, you first hash it to 160 bits and > then you sign this result. In your scheme, the hashed message h(m) > will be associated to a unique path in the tree, so there is no need to > keep track of how many messages have been signed. However, if two > messages m and m' hash to the same value, i.e. h(m)=h(m'), the > signatures of these messages will be identical. This is not the case in > Merkle's signature scheme, where one increments a counter for each > message signed. So I guess for the security of your scheme you must > assume that there are no collisions in the hash function. > What happens if the random oracle produces collisions? I already pointed out in an email that this is not. > It is very unclear to me how your scheme compares to Merkle's signature > scheme and other schemes. Such comparison is necessary. Right, this is again the most crucial thing. > The description of your scheme (page 4) ought to be more detailed, e.g., > in the second item, how is p_x generated based on p? You should introduce > a symbol for the hash function, e.g. h, then state explicitly how the > private and public keys are generated. And this sounds like a good idea too. > For the "proof of security" of your scheme you need to be more precise and > detailed. You probably want to show that if one can forge a signature in > your scheme, then the attacker can forge a signature in the underlying > one-time signature scheme (which is (perhaps) assumed infeasible) or the > attacker can break the key boosted scheme. If this is what you want to > show, you should give all details of such a proof. Also a very good idea.