Graph-theoretic zero-knowledge authentication scheme for decentralized identity management
*Sreenivas MekalaCorresponding authorsreenivas.m@kaveriuniversity.edu.inDepartment of Computer Science and EngineeringSchool of Engineering and TechnologyKaveri UniversitySiddipet, Telangana, 502279, IndiaView full profile → , Kandadai Bhargavibhargavi.mtech@gmail.comDepartment of Computer Science and EngineeringICFAI Foundation for Higher EducationShankarpally, Hyderabad, Telangana, 501203, IndiaView full profile → , Ravi Thavasi Anandamdrravit@veltech.edu.inDepartment of Computer Science and EngineeringVel Tech Rangarajan Dr. Sagunthala R&D Institute of Science and TechnologyAvadi, Chennai, Tamil Nadu, 600062, IndiaView full profile → , Akanksha Kulkarniakanksha.kulkarni@sitpune.edu.inDepartment of Computer Science and EngineeringSymbiosis Institute of TechnologySymbiosis International (Deemed University)Pune, Maharashtra, 412115, IndiaView full profile → , G. Manikandanmaniprofessional@gmail.comDepartment of Artificial Intelligence and Machine LearningSt. Joseph’s College of EngineeringChennai, Tamil Nadu, 600119, IndiaView full profile → , T. M. Amirthalakshmitm_amirthalakshmi@ch.amrita.eduDepartment of Electronics and Communication EngineeringAmrita School of EngineeringAmrita Vishwa VidyapeethamChennai, Tamil Nadu, 601103, IndiaView full profile → , T. Sunilkumar Reddysunilreddy.vit@gmail.comDepartment of Computer Science & EngineeringSri Venkatesa Perumal College of Engineering & TechnologyPuttur, Andhra Pradesh, 517583, IndiaView full profile → , V. Balajibalaji.iniyan@gmail.comDepartment of Computer Science and Engineering (Cyber Security)Easwari Engineering CollegeChennai, Tamil Nadu, 600089, IndiaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Nov 2025
- Published Online:
- 30 Sep 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-2897
- Pages:
- 3703–3712
Abstract
Classical zero-knowledge proof (ZKP) constructions such as zk-SNARKs and STARKs impose significant prover computation overhead and circuit compilation complexity that limits their accessibility for resource-constrained verifiable credential applications. This paper proposes a graph-theoretic ZKP framework that encodes identity claims as graph colouring witnesses and employs a Sigma protocol over the elliptic curve commitment scheme to prove knowledge of a valid graph colouring without revealing the colouring itself. The proposed construction leverages the NP-completeness of graph 3-colouring to achieve perfect completeness, computational soundness under the discrete logarithm assumption, and honest-verifier zero-knowledge provable by a polynomial-time simulator. The framework is deployed as an Ethereum smart contract on the EVM, using a Pedersen commitment-based hash accumulator for on-chain witness binding and Merkle proof verification for credential revocation checking. Formal security analysis under the universal composability framework establishes composable security against adaptive adversaries. Experimental evaluation on the Ethereum Sepolia testnet demonstrates proof generation in 38 ms and on-chain verification consuming 21,400 gas units, representing a 73% reduction in proving time compared to zk-SNARK Groth16 and a 58% reduction in gas cost compared to STARK proofs.
Keywords
Subject Classifications
References
[1] S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM J. Comput., vol. 18, no. 1, pp. 186–208 (1989).
[2] J. Camenisch and A. Lysyanskaya, “Dynamic accumulators and application to efficient revocation of anonymous credentials,” in Proc. CRYPTO, Springer, pp. 61–76 (2022).
[3] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev, “Scalable, transparent, and post-quantum secure computational integrity,” IACR Cryptol. ePrint Arch., Rep. 2018/046 (Apr. 2022).
[4] J. Groth, “On the size of pairing-based non-interactive arguments,” in Proc. EUROCRYPT, Springer, pp. 305–326 (2021).
[5] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” in Proc. CRYPTO, Springer, reprinted in Lecture Notes in Computer Science, vol. 263, pp. 186–194 (2022).
[6] J. B. Bernabe, J. L. Canovas, J. L. Hernandez-Ramos, R. Torres Morales, and A. Skarmeta, “Privacy-preserving solutions for blockchain: Review and challenges,” IEEE Access, vol. 7, pp. 164908–164940 (2021).
[7] D. Maram, H. Malvai, F. Zhang, N. Jean-Louis, A. Frolov, T. Kell, T. Lobban, C. Moy, A. Juels, and A. Miller, “CanDID: Can-do decentralized identity with legacy compatibility, Sybil-resistance, and accountability,” in Proc. 42nd IEEE Symp. Security Privacy (SP), pp. 1348–1366 (2021), doi: 10.1109/SP40001.2021.00038
[8] J. Benet and N. Dalrymple, “IPFS—Content addressed, versioned, P2P file system,” arXiv preprint arXiv:1407.3561 (2021).
[9] A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou, “Hawk: The blockchain model of cryptography and privacy-preserving smart contracts,” in Proc. IEEE Symp. Security Privacy (S&P), pp. 839–858 (2022).
[10] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell, “Bulletproofs: Short proofs for confidential transactions and more,” in Proc. IEEE Symp. Security Privacy (S&P), pp. 315–334 (2022).
[11] K. R. Chaudhari, A. O. Mulani, M. P. Gajare, V. Jadhav, P. Yawle, and A. V. Bang, “Bit error rate analysis of various error correction codes with concatenated RS-convolutional codes,” J. Discrete Math. Sci. Cryptogr., vol. 29, no. 1, pp. 199–214 (2026).
[12] S. Salunkhe, A. O. Mulani, D. Shahane, M. Rana, S. M. Shukla, and M. M. Jadhav, “Secure image transmission using chaotic encryption and DWT watermarking on reconfigurable platform,” J. Discrete Math. Sci. Cryptogr., vol. 29, no. 1, pp. 349–361 (2026).
