4-санға «Автоматтандыру және ақпараттық технологиялар», «Азық-түлік инженериясы және биотехнология», сондай-ақ «Химиялық технология» бағыттары бойынша мақалалар қабылдау жабылды.

Приём статей в четвёртый номер по направлениям «Автоматизация и информационные технологии», «Пищевая инженерия и биотехнология», а также «Химическая технология» закрыт.

Submissions for the fourth issue in the fields of Automation and Information Technology, Food Engineering and Biotechnology, as well as Chemical Technology, are now closed.

Preview

Bulletin of Shakarim University. Technical Sciences

Bulletin of Shakarim University. Technical Sciences

Advanced search

КРИПТОГРАФИЯЛЫҚ ХАТТАМА: ИНТЕРАКТИВТІ ЕМЕС НӨЛДІК ЖАРИЯ ЕТІЛГЕН ДӘЛЕЛДЕМЕЛЕРДІҢ ЕСЕПТЕУ КҮРДЕЛІЛІГІН ТАЛДАУ

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. Modovov
Al-Farabi Kazakh National University 
Kazakhstan

Nurbol Modovov – 1st-year PhD doctoral student of the Information Security Systems educational program

 050040, 71 Al-Farabi Ave., Almaty, Kazakhstan 



N. Mekebayev
Al-Farabi Kazakh National University; Kazakh National Women’s Teacher Training University
Kazakhstan

Nurbapa Mekebayev – PhD, Associate Professor, Department of Informatics

050040, 71 Al-Farabi Ave., Almaty, Kazakhstan

050000, 114 Gogol St., Almaty, Kazakhstan



A. Tleubayeva
Shakarim University
Kazakhstan

Aksaule Tleubayeva – Master's degree holder

 071412, 20A Glinka St., Semey, Kazakhstan 



O. Belgozha
Kazakh National Women’s Pedagogical University
Kazakhstan

Оrken Belgozha – Master’s degree holder, Lecturer of the Department of Computer Science

050000, 114 Gogol St., Almaty, Kazakhstan



I. Sydykzhan
Kazakh National Women’s Pedagogical University
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

Views: 16

JATS XML


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2788-7995 (Print)
ISSN 3006-0524 (Online)
X