NIST Category Clarification and Algorithm Clarification

[ChristianOConnor]

Hey guys! First I just got to say that I love this project and I have been experimenting with it a lot. Post quantum cryptography is a REALLY important thing to study especially with all of the research being put into quantum computing.

My question is in 2 parts:

1) Which is the actual algorithm that this project uses? Or is it a custom algorithm? I know it's a variation of unbalanced oil and vinager but there are a few specific standards as defined by projects like "open quantum secure" where there are specific algorithm titles that are proven (or at least strongly argued) secure like "Picnic2-L5-FS," "qTesla-p-III," "SPHINCS+-SHAKE256-256s-robust," or "MQDSS-31-64." What's the official title of this algorithm used by crypto-vinaigrette?

2) Totally cool if this isn't relevant but the NIST has a 5 catagory system that they use to classify the strength of post quantum algorithms:

From "https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/evaluation-criteria/security-(evaluation-criteria)"

• 1) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128-bit key (e.g. AES128)
• 2) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 256-bit hash function (e.g. SHA256/ SHA3-256)
• 3) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 192-bit key (e.g. AES192)
• 4) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 384-bit hash function (e.g. SHA384/ SHA3-384)
• 5) Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 256-bit key (e.g. AES 256)

Does the algorithm used by this program fall into one of these catagories?

Sorry to bother you all with these question, I just love the project and I'm anxious to start building projects that incorporate crypto-vinaigrette signing.

[avinashshenoy97]

Hey Christian,

1. Its called the rainbow signature scheme, here's the paper.

2. I'm not sure what category it'd fall under, the paper only compares it to other multivariate schemes, and nonchalantly quotes

From this we conclude that the total complexity to attack our example is atleast 2^80

Although we found this rainbow scheme to be quite popular, I'm sure a quick google search would answer your question as to how it compares against AES-x and SHAx

Looking forward to see what you'll be building! 👍 Hope this helps!

[ChristianOConnor]

@avinashshenoy97 Thank you so much for your very thorough answer!! I really appreciate it!