**Last Updated: April 30, 2018**

Background on SecureRF and NIST’s Post-Quantum Project.

*The evaluation underway by NIST offers SecureRF (and other entities who have made submissions) a unique opportunity to be tested and evaluated by world-class experts in the field. We believe that these types of processes are critical to demonstrating the robustness and integrity of our methods. *

Download the latest source code for WalnutDSA.

*Here is a summary of comments and analysis of our method, from the NIST community, along with our responses. *

*PLEASE NOTE: To address all comments and analysis in a timely fashion, any timing or size metrics in our initial responses may not represent the performance found in a later optimized version. *

Analysis:A paper identified a factoring method, that if the two private braids in WalnutDSA^{TM}were equal, they could then create signature forgeries. However, the shortest forgery they created was over 2^30 times longer than a WalnutDSA original signature. Because WalnutDSA has a signature length limit, these forgeries are immediately considered invalid and rejected.After this paper, another researcher showed that with an extra factor-of-two in the resulting forgery he could still make the factoring attack work.

Response:The initial forgery method was mitigated before submission to NIST by ensuring that there were two distinct private braids with distinct, non-trivial permutations. The second researcher's efforts were addressed by using a more explicit length limit, and a reduction of that limit from 2^16 to 2^14 Artin generators. Regular signatures are on the order of 2^10 to 2^12 generators, so even with the conjectured 2^11 multiplier, there is no known way to generate forgeries of sufficient shortness.The reduction of the maximum limit from and implicit 2^16 to an explicit 2^14 Artin generators makes that even more challenging to forge a signature.

Analysis:A researcher using a Pollard-rho birthday algorithm discovered the parameters proposed in the WalnutDSA submission were slightly too small to achieve the desired security level. For example, instead of reaching a 128-bit security level the researcher claimed only a 108-bit security level was achieved. Specifically, he suggested that to reach a k-bit security level, q^(N (N-3) -1) > 2^(2k).

Reponse:This issue was addressed by updating the parameter N from 8 to 10 for both the 128- and 256-bit levels. This small parameter adjustment brought the security levels up to the desired strengths.

Analysis:A researcher pointed out two different issues with the encoder parameters, which define how to convert the hash value output into a braid word. The first issue was that the initial encoder was not injective (1-to-1), which reduced the number of distinct braid words created. The second issue was that the encoder parameters generated a vector space with a dimension that was too small, reducing the search space. Specifically, he suggested that to reach a k-bit security level, q^dimension > 2^(2k).

Response:This issue was addressed by updating the encoder parameters. Instead of specifying a fixed {1,3,5,7}-generator encoder using a 4-bit block (2 bits for the generator, 2 bits for an exponent), we updated the specification to use 2-bit blocks and then a rotating sequence of generators. This update made the encoding injective and significantly increased the dimension of the results, nullifying the issues raised by this analysis. Specifically, the dimension at N=10 using the updated encoding parameter is 66, resulting in the desired security levels.

Analysis:Two researchers produced an exponential attack on WalnutDSA that performs in q^(N-5/2). We have verified this timing with code provided by the researchers. In their paper, they go on to say they believe they can further reduce the running time to q^(N/2-1) but this assumes t1=t2=1.

Response:WalnutDSA has multiple parameters that can be adjusted to reach a desired security level and each parameter affects performance in a different way. We have only studied this attack for a very brief period of time, but assuming their worst-case analysis of q^(N/2 – 1) is correct, we would propose that the N and q parameters be increased to N=11, q=M31 for 128-bit security and N=11, q=M61 for 256-bit security (where Mx is the Mersenne Prime 2^x - 1). These parameter-only changes block their attack which have also been confirmed by the researchers.An additional benefit of these new parameters, specifically changing to a prime field, is that we can easily create cloaking elements that no longer require t1=t2=1. By taking generators to the fourth power (instead of the 2nd) the t-value t1 can be randomly chosen while t2 = -t1^{-1}. This further complicates this attack and increases its run time by a sqrt(60*q) factor, which then runs in sqrt(60)*q^((N-1)/2) time and has been confirmed by the researchers. In fact, this change to the prime field allows us to reduce N to 10 and still yield a 2^142 and 2^277 security level.

In summary, the parameter-only changes address this attack and our proposed change to a prime field further improves WalnutDSA and its resiliency to this type of attack.