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...
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jun 27, 2016 at 5:03