Graph Coloring - Based Approach to Secure Shamir’s Secret Sharing

Abstract

This paper introduces a graph coloring–based enhancement of Shamir’s Secret Sharing (SSS) to strengthen the security of distributed secret distribution. In the proposed method, participants are represented as vertices in a graph, and coloring constraints ensure that adjacent participants do not receive complementary share information, thereby minimizing the risk of collusion and data leakage. The results show that the scheme enhances robustness and access control while preserving the computational efficiency of traditional SSS.