I've seen both asymmetric encryption and secret sharing schemes based on graph 3-coloring, and I'm curious if this is a coincidence due to some peculiar property of graph 3-coloring alone.

  • could you provide the two articles about the 3-colouring based work? – kelalaka Oct 8 at 12:54
  • Page 238 of Discrete Mathematics Using Latin Squares describes a public-key system based on Latin Squares (which I believe are a form of the 3-coloring problem). The previous page describes a secret-sharing scheme using Latin Squares. Also, this paper. This paper also. – Meler Lawler Oct 8 at 21:07
  • @Meler_Lawer, Latin Square = n coloring, if n =3 the 3-coloring? My answer has mistakes. deleting. could you write one? I like to see. – kelalaka Oct 8 at 21:12
  • I think the answer is yes. EDIT: I don't understand, what do you want me to write? – Meler Lawler Oct 8 at 21:15
  • 1
    I've looked for RSA based secret sharing but couldn't one. Also, I couldn't find about asymmetric encryption scheme based on 3-coloring. – kelalaka Oct 8 at 21:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.