КРИПТОГРАФИЯЛЫҚ ХАТТАМА: ИНТЕРАКТИВТІ ЕМЕС НӨЛДІК ЖАРИЯ ЕТІЛГЕН ДӘЛЕЛДЕМЕЛЕРДІҢ ЕСЕПТЕУ КҮРДЕЛІЛІГІН ТАЛДАУ
https://doi.org/10.53360/2788-7995-2026-3(23)-2
Abstract
This paper is devoted to the asymptotic and formal analysis of the computational complexity of NonInteractive Zero-Knowledge Proofs (NIZK). Non-interactive zero-knowledge proofs enable a prover to convince a verifier of the validity of a given statement without revealing any additional information and are widely applied in distributed information systems.
In this study, NIZK schemes are considered within the Common Reference String (CRS) model. The evaluation of computational complexity is based on the time complexity of the proving and verification algorithms, the witness size, and the proof length. Algorithmic efficiency is analyzed within the framework of the polynomial-time computational model.
The analysis shows that the computational complexity of the proving algorithm significantly depends on the witness size, whereas the complexity of the verification algorithm is mainly determined by the proof length. Additionally, asymptotic bounds on proof size and their impact on communication costs are examined.
The obtained results provide a theoretical foundation for the comparative analysis of non-interactive zeroknowledge proofs and for the development of computationally efficient cryptographic protocols.
About the Authors
N. ModovovKazakhstan
Nurbol Modovov – 1st-year PhD doctoral student of the Information Security Systems educational program
050040, 71 Al-Farabi Ave., Almaty, Kazakhstan
N. Mekebayev
Kazakhstan
Nurbapa Mekebayev – PhD, Associate Professor, Department of Informatics
050040, 71 Al-Farabi Ave., Almaty, Kazakhstan
050000, 114 Gogol St., Almaty, Kazakhstan
A. Tleubayeva
Kazakhstan
Aksaule Tleubayeva – Master's degree holder
071412, 20A Glinka St., Semey, Kazakhstan
O. Belgozha
Kazakhstan
Оrken Belgozha – Master’s degree holder, Lecturer of the Department of Computer Science
050000, 114 Gogol St., Almaty, Kazakhstan
I. Sydykzhan
Kazakhstan
Inzhu Sydykzhan – Master’s degree holder
050000, 114 Gogol St., Almaty, Kazakhstan
References
1. How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design – Oded Goldreich, Silvio Micali & Avi Wigderson. Advances in Cryptology. – CRYPTO’86, Lecture Notes in Computer Science. – 1987. – Vol. 263. – Р. 171-185. https://doi.org/10.1007/3-540-47721-7_11.
2. Fiat A. How to Prove Yourself: Practical Solutions to Identification and Signature Problems / A. Fiat, A. Shamir // Advances in Cryptology - CRYPTO’86, LNCS 263, Springer. – 1987. https://doi.org/10.1007/3-540-47721-7_12.
3. Goldwasser S. The Knowledge Complexity of Interactive Proof Systems / S. Goldwasser, S. Micali, C. Rackoff // SIAM Journal on Computing. – 1989. – № 18(1). https://doi.org/10.1137/0218012.
4. Manuel B. Non-Interactive Zero-Knowledge and Its Applications / В. Manuel, P. Feldman, S. Micali // STOC ’88, ACM. – 1988. https://doi.org/10.1145/62212.62222.
5. Bellare M. Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols / M. Bellare, P. Rogaway // ACM CCS. – 1993. https://doi.org/10.1145/168588.168596.
6. Groth J. On the Size of Pairing-Based Non-interactive Arguments. Advances in Cryptology / J. Groth // EUROCRYPT. – 2016, LNCS 9665. https://doi.org/10.1007/978-3-662-49896-5_11.
7. Scalable, Transparent, and Post-Quantum Secure Computational Integrity / E. Ben-Sasson et al // IACR Cryptology ePrint Archive. – 2018. https://eprint.iacr.org/2018/046.
8. Bulletproofs: Short Proofs for Confidential Transactions and More / Benedikt Bünz et al // IEEE Symposium on Security and Privacy. – 2018. https://doi.org/10.1109/SP.2018.00020.
9. Quadratic Span Programs and Succinct NIZKs without PCPs / R. Gennaro et al // Advances in Cryptology – EUROCRYPT. – 2013. https://doi.org/10.1007/978-3-642-38348-9_35.
10. Micali S. Computationally Sound Proofs / S. Micali // SIAM Journal on Computing. – 2000. – № 30(4). https://doi.org/10.1137/S0097539795284959.
11. From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge / N. Bitansky et al // ITCS. – 2012. https://doi.org/10.1145/2090236.2090263.
12. Succinct Non-Interactive Arguments / A. Chiesa et al // IACR Cryptology ePrint Archive. – 2012. https://doi.org/10.1007/978-3-642-40041-4_9.
13. Adaptive Security for Interactive Proofs / R. Canetti et al // TCC. – 2002. https://doi.org/10.1007/978-3-642-40041-4_9.
14. Katz J. Introduction to Modern Cryptography / J. Katz, Y. Lindell // Chapman and Hall/CRC. – 2014. https://doi.org/10.1201/9781351133036.
15. Boneh D. A Graduate Course in Applied Cryptography / D. Boneh, V. Shoup // Draft textbook. – 2020. https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_6.pdf.
Review
For citations:
Modovov N., Mekebayev N., Tleubayeva A., Belgozha O., Sydykzhan I. КРИПТОГРАФИЯЛЫҚ ХАТТАМА: ИНТЕРАКТИВТІ ЕМЕС НӨЛДІК ЖАРИЯ ЕТІЛГЕН ДӘЛЕЛДЕМЕЛЕРДІҢ ЕСЕПТЕУ КҮРДЕЛІЛІГІН ТАЛДАУ. Bulletin of Shakarim University. Technical Sciences. 2026;(3(23)):15-22. (In Kazakh) https://doi.org/10.53360/2788-7995-2026-3(23)-2
JATS XML















