1
$\begingroup$

Recently, I grew a tremendous interest for public-key cryptography based on "groupoids", and collaborated with someone on this topic. What I notice afterwards, is that there had been a huge body of work on "non-commutative" cryptography, with a book from 2011 dedicated to that topic titled "Non-commutative Cryptography and Complexity of Group-theoretic Problems" written by A.Myasnikov et al. (published by American Mathematical Society), although I haven't gotten access to its content yet.

Obviously, non-commutative cryptography had not been matured to the stage where they'd get hash-sign-numbered standards like PKCS#1 for RSA, SEC#1 for elliptic-curve, and EESS#1 for NTRU.

What this question asks is, what are the typical parameters proposed for non-commutative cryptographic schemes? What're their typical cryptogram sizes?

$\endgroup$
1
  • 1
    $\begingroup$ I think "non-commutative cryptographic scheme" is overly broad, as naturally the product in (M)LWE comes from $\mathsf{GL}_n(R)$, which is non-commutative in the case of module rank $n > 1$. I am assuming that this question is not interested in the parameters of (M)LWE though. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 11, 2021 at 18:08

2 Answers 2

4
$\begingroup$

The most common proposals around non-commutative cryptography have been around braid groups. Its proponents have struggled to find parameter sets that are agreed to resist security analysis. Recent proposals have included the algebraic eraser key establishment system and WalnutDSA, a signature scheme that was entered in the NIST post-quantum crytpography process, but failed to pass the first round.

I don't know if there are currently any proposed parameters for the Algebraic Eraser scheme, but this 2016 paper gives a cryptanalysis of the scheme proposed for ISO/IEC 29167-20 standardisation (the standard was not published). The Algebraic Eraser authors' response is also available.

The WalnutDSA submission can be found on the website of the NIST process (the WalnutDSA website link no longer works), as can the cryptanalysis that led to its non-progression.

$\endgroup$
1
$\begingroup$

In case you would read Rusian: a Diffie-Hellman -like common key from non-commutative group operation. http://mi.mathnet.ru/dan5041 http://www.mathnet.ru/rus/person17348

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.