Summary response to comments on KAZ-SIGN v1.0:
Dear all,
First and foremost, KAZ-Team would like to extend our thanks to Prof. Bernstein for his comment/concern. It was really an eye opener. It has been approximately 2 weeks since Prof. Bernstein hinted about tweaking KAZ-SIGN to identify the forged signature equation. As Prof. Bernstein correctly pointed out in his response to an earlier comment, KAZ-SIGN aspires not to be dependent on the Discrete Logarithm Problem. Rather we coin our hard problem as the Second Order Discrete Logarithm Problem (2-DLP) as defined in our Algorithm Specifications and Supporting Documentation write-up.
The design of KAZ-SIGN also aspires to be flexible, that is when a forgery mechanism has been obtained, KAZ-SIGN can identify such forgery during verification.
We note here that, in our endeavor after Prof. Bernstein comments, the aim is to tweak the signature scheme to be able to identify the forged signature without amending the foundations and increasing the key and digital signature lengths significantly. As an overview, minor changes have been made and we have managed to omit time consuming procedures and also the need to use salt.
Let us recall; let Gg be the order of g in N. That is, g^{Gg}=1 mod N. Let GRg be the order of R in Gg. That is, R^{GRg}=1 mod Gg.
To this end, we have realized that the 2-DLP is an "expensive" way of describing the underlying mathematical hard problem of KAZ-SIGN. In reality, the private signing key α is kept unknown to the adversary via the relation α=αF mod GRg. This situation can be viewed via t=(α-αF)/GRg. When αF and GRg are known, the length of t, will determine the difficulty level of retrieving back the private signing key α. For KAZ-SIGN documentation formality we coin this as the Modular Reduction Problem (MRP). Details are in the write-up.
As for the extra overhead, the private signing key and public verification key have increased. It has increased approximately 400, 700 and 1,000 bits for the public verification keys for security levels 1, 3 and 5. As for the private signing key, it sees an increase of approximately 128, 192 and 256 for security levels 1, 3 and 5. However, the signature size remains approximately the same.
Even though the size has increased, KAZ-SIGN procedures has been strip down from its heavy computations and hence a speed up of more than 500% (to say the least). One can make comparison from both write-ups [refers v1.0 & v1.1 here] for a more accurate figure.
In brief we defined the public verification key-1 as V1=α mod GRg, the public verification key-2 as a random k-bit prime (where k is the security level value 128 or 192 or 256) and V3=α mod V2. Observe that to obtain α from V1 or V3 is the MRP.
Then we sign as S1=R^(r mod GRg) mod Gg, S2=(α^(r mod V2) +h)/r mod GRgV2 and S3=r mod V2.
The verification procedure is as follows:
Compute w0=S2S3-h mod V2 and w1=V3^(S3) mod V2. If w0 ≠ w1 reject signature. Else continue to verify (the same procedures in our NIST submission, see write-up).
Note, the suggested Prof. Bernstein forgery mechanism (which can be utilized for this new setup) is of the form S2F=(V1^(r mod V2)+h+GRgx)/r mod GRgV2 for some random x in Z_{GRg} (Prof. Bernstein's random structure is x=x1+x2r for some random x1 and x2). S2F will still pass our verification procedures. But it will not pass our filtering procedures via computing w0 and w1 and making comparison.
Its clear that w0=S2FS3-h mod V2 and w1=V3^(S3) mod V2 would result in w0 ≠ w1. This is because S2FS3 - h ≠ V3^(S3) mod V2.
Thus, the adversary will have to forge S3 also (i.e. denoted as S3F). To do this, the adversary will need to resolve
V3^(S3F)-S2FS3F+h = 0 mod V2. After substitutions, this would mean the adversary needs to solve V3^(S3F)-V1^(S3F)-GRgx = 0 mod V2 ---(eq A). And after obtaining S3F, the adversary can set S1=R^(S3F) mod Gg. All these forged parameters will pass the filtering and verification procedures.
Observe that, to solve (eq A), the complexity is O(V2). Furthermore, V2 is a prime number of k-bits and the adversary will not be able to execute the Chinese Remainder Theorem to reduce this complexity.
KAZ-Team has setup this website that lists our C codes and Algorithm Specifications and Supporting Documentation according to version. The version sent to NIST prior to Prof. Bernstein comment will be known as Version 1.0 (v1.0). The version with the new procedures as mentioned above will be known as Version 1.1 (v1.1).
Thank you for the precious comment. KAZ-Team hopes that this minor tweak will not be a hindrance for KAZ-SIGN to be further evaluated.
Best regards
KAZ-Team
Aug 3, 2023