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

Summary response to comments on KAZ-SIGN v1.1:

Dear all,

First and foremost, KAZ-Team would like to extend our hearthfelt thanks to Prof. Bernstein for his insights again. The usage of the Chinese Remainder Theorem (CRT) to construct a forgery of signature parameter S2 by utilizing given public parameters (V1,V3) upon modulars V2 and GRg does indeed bypass our existing filtering strategies.

In order to overcome this issue, it is necessary not to introduce more parameters that might open new avenues for forgery. A minor tweak was done on the definition of V2. The strategy is as follows:

The public verification key-1 as V1≡α mod GRg, the public verification key-2 is the product of a random k-bit prime, denoted as ρ (where k is the security level value 128 or 192 or 256) and the largest factor of GRg denoted as β. We denote the public verification key-2 as V2=βρ. Finally the public verification key-3 is given by V3≡α mod V2. Observe that to obtain a from V1 or V3 is the MRP. To factor V2 is easy. We do not intend to deploy the integer factorization problem upon V2.

The signature procedure remains the same as v1.1. The signature parameters are S1≡R^{r mod GRg} mod Gg, S2≡(α^{r mod V2}+h)/r mod (GRgV2) and w3≡r mod V2.

The verification procedure is similar to v1.1. At the same time, as a result of Prof. Bernstein's 2nd input, we add the following procedures during verification

Procedure 1: Compute w0≡S2S3-h mod V2 and w1≡V3^(S3) mod V2. If w0 ≠ w1, reject the signature.

Procedure 2: From S1, solve the DLP to obtain rF, where rF=DLog_{R} (S1 mod Gg). Compute w2≡(GRg/β)S3 mod GRg and w3≡(GRg/β)rF mod GRg. If w2 ≠ w3, reject the signature.

Procedure 3: Compute rF, where rF=DLog_{R} (S1 mod Gg). Compute Chinese Remainder Theorem upon w4≡(V3^{S3}+h)S3^{-1} mod ρ and w5≡(V1^{S3}+h)rF^{-1} mod GRg to obtain w6 mod ρGRg. Compute w7=w6-S2. If w7=0, reject the signature.

Further discussion on this matter can be seen in section 8 in v1.2.

As for the extra overhead, the private signing key and public verification key have increased a few bits when compared to v1.1. That is approximate 35, 20 and 10 bits for the public verification keys for security levels 1, 3 and 5. As for the private signing key, it sees an increase of approximate 13 and 5 bits for security levels 1 and 3. There is no increase for security level 5. As for the signature, it sees an increase of approximate 25, 20 and 10 bits for security levels 1, 3 and 5.

Even though the size has increased, KAZ-SIGN procedures still executes fast.

KAZ-Team has made available our C codes and Algorithm Specifications and Supporting Documentation above

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 17, 2023

Summary response to comments on KAZ-SIGN v1.2:

Dear all,

Based on Prof Bernstein's comments, KAZ-SIGN v1.3 is now available for scrutiny here

All comments are welcomed.

Best wishes

KAZ-Team
Aug 31, 2023

Summary response to comments on KAZ-SIGN v1.3:

Dear all,

Based on Prof Bernstein's comments on KAZ-SIGN v1.3, in the course of scrutinizing the 10% cases where forgery was reported not able to be conducted, we have obtained interesting information. KAZ-SIGN v1.4 is now available for scrutiny here.

All comments are welcomed.

Best wishes

KAZ-Team
Sept 24, 2023
(Live on Sept 25, 2023)