ARITHMETIC CIRCUIT COMPLEXITY OF LEGACY CRYPTOGRAPHIC STANDARDS AS A BARRIER TO ZERO-KNOWLEDGE CREDENTIAL VERIFICATION
Keywords:
zero-knowledge proofs, GOST 34.311-95, DSTU 4145-2002, ECDSA, SHA-256, arithmetic circuits, R1CS, Groth16Abstract
The study addresses the issues that prevent the implementation of confidential document verification. The first issue is the outdated cryptographic algorithms used by the EDEBO registry (GOST 34.311-95 and DSTU 4145-2002), for which the number of R1CS constraints in the Groth16 system was calculated for the first time. For a 10 KB document, the hash function alone generates over 19 million constraints (~15 minutes to generate a proof), and signature verification generates over 140 million. For comparison, SHA-256 and ECDSA P-256 together require around 2 million constraints (60–120 seconds). The second problem is that the PDF/XML document format does not support selective field exposure, which is an independent obstacle regardless of the algorithms. A transition to SHA-256/ECDSA or “Kupina” and the structured JSON-LD format is proposed.
References
Goldwasser S., Micali S., Rackoff C. The knowledge complexity of interactive proof systems. SIAM Journal on Computing. 1989. Vol. 18, No. 1. P. 186–208. https://doi.org/10.1137/0218012.
Bernhard D., Pereira O., Warinschi B. How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios. Advances in Cryptology – ASIACRYPT 2012. Lecture Notes in Computer Science. Vol. 7658. Berlin, Heidelberg : Springer, 2012. https://doi.org/10.1007/978-3-642-34961-4_38.
Hamila F., Hamad M., Salgado D. C. et al. Enhancing security in Fiat–Shamir transformation-based non-interactive zero-knowledge protocols for IoT authentication. International Journal of Information Security. 2024. Vol. 23. P. 1131–1148. https://doi.org/10.1007/s10207-023-00779-8.
Groth J. On the size of pairing-based non-interactive arguments. Advances in Cryptology – EUROCRYPT 2016. Lecture Notes in Computer Science. Vol. 9666. Springer, 2016. P. 305–326. https://doi.org/10.1007/978-3-662-49896-5_11.
Verifiable Credentials Data Model v1.1 : W3C Recommendation. World Wide Web Consortium, 2022. URL: https://www.w3.org/TR/vc-data-model/ (date of access: 12.04.2026).
Ramić Š. B., et al. Selective disclosure in digital credentials: A review. ICT Express. 2024. Vol. 10, No. 4. P. 916–934. https://doi.org/10.1016/j.icte.2024.05.011.
