Motivation

	AllPages RecentChanges Links to this page Edit this page Search Entry portal
Advice For New Users

Current Public-Key Crypto-systems (PKC's) use problems that we think are hard, but are not proven to be NP-Complete (NPC). It would be nice to have a PKC based on a problem that is known to be NPC

Note: Inserting the trap door might still weaken the problem.

Graph vertex 3-colouring (G3C) is NPC

And there is a comparatively simple, elementary, direct proof

http://www.solipsys.co.uk/new/FactoringViaGraphThreeColouring.html#toc_name009

Most instances of G3C are easy to solve

... for suitable definitions of "most" and "easy"

I think there's a result that the proportion of difficult instances goes to 0 as n goes to infinity

It's still the case that the absolute number of difficult instances goes to infinity

So here's the plan:

Find a way to create hard instances of G3C
Insert a trapdoor without weakening it
Create a PKC based on that
Profit!

Well, probably not profit, but at least it might be interesting.

Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout