2022 project @ NCTU Cryptography Engineering lecture
Implemented with d3.v7.js
graph_coloring.pygraph coloring algorithmgraph_puzzle.pypuzzle infosolution_gen.pygenerate correct data structure as input to d3.jszkp_d3.jsdynamic network graph with d3zkp_puzzle.jspuzzle info in d3 formatzkp.htmlmain page
Zero-knowledge proof
- Have the additional property of yielding nothing beyond the validity of the interactive proof protocol.
- Interactive/ Non-interactive
Zero knowledge protocol
- Interactive method for prover to prove to verifier that a statement is true, without revealing anything other than the veracity.
A graph G is 3-colorable if the vertices of a given graph can be colored with only three colors, such that no two vertices of the same color are connected by an edge.
Assign colors one by one to different nodes, starting from the first node. For each assignment
- check for safety by considering already assigned colors to the adjacent nodes.
- If there is any safe assignment, mark the color assignment as part of the solution.
- If no safe assignment exists then backtrack and return false.
Two scenarios
- Prover is honest (graph_0), in each reveal event
- Color the graph with one correct solution
- Permute the color assignment
- Prover is lying (graph_1), in each reveal event
- Color with randomly choose from several wrong solutions
- Permute the color assignment