1
$\begingroup$

Are there any symmetric authentication systems based on the hardness of an NP-complete problem? I understand that it doesn't really matter, since NP-completeness is about the worst case, and in crypto we care about the average case, but I still feel it's somewhat interesting...

$\endgroup$
1
$\begingroup$

You could use the turtle block cipher with CMAC, maybe.

The turtle block cipher claims a cipher design that is based on "an NP-Complete Subproblem".

Block ciphers can be used to produce authentication tags via algorithms such as CMAC.

I'm not sure if this combination necessarily qualifies the authentication as being based on an NP-Complete subproblem too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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