Re:Why cryptography is not based on NP-complete problems
by alexey-salmin on Wednesday February 12, 2025 @09:32PM
(#43032069)
I'd also note that zero-knowledge proofs (which are considered a branch of cryptography) often do rely on NP-complete problems like the three-color maps.
[ Parent
| on HN ]
Re:Why cryptography is not based on NP-complete problems
by Vervious on Wednesday February 12, 2025 @10:06PM
(#43032243)
That's completely unrelated, the reliance there is because you want to be able to prove "any statement in NP" in zero knowledge. It then suffices to give a protocol for just 3-colorings, because "any statement in NP" can then be reduced to a 3-coloring.