<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">kaz44</journal-id><journal-title-group><journal-title xml:lang="ru">Вестник Университета Шакарима. Серия технические науки</journal-title><trans-title-group xml:lang="en"><trans-title>Bulletin of Shakarim University. Technical Sciences</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">2788-7995</issn><issn pub-type="epub">3006-0524</issn><publisher><publisher-name>«Шәкәрім университеті» КеАҚ</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.53360/2788-7995-2026-3(23)-2</article-id><article-id custom-type="elpub" pub-id-type="custom">kaz44-2751</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>АВТОМАТИЗАЦИЯ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ (ОРИГИНАЛЬНАЯ СТАТЬЯ)</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>AUTOMATION AND INFORMATION TECHNOLOGY (ORIGINAL ARTICLE)</subject></subj-group></article-categories><title-group><article-title>АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ НЕИНТЕРАКТИВНЫХ ДОКАЗАТЕЛЬСТВ С НУЛЕВЫМ РАЗГЛАШЕНИЕМ</article-title><trans-title-group xml:lang="en"><trans-title>КРИПТОГРАФИЯЛЫҚ ХАТТАМА: ИНТЕРАКТИВТІ ЕМЕС НӨЛДІК ЖАРИЯ ЕТІЛГЕН ДӘЛЕЛДЕМЕЛЕРДІҢ ЕСЕПТЕУ КҮРДЕЛІЛІГІН ТАЛДАУ</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0009-0005-1642-9834</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Модовов</surname><given-names>Н. А.</given-names></name><name name-style="western" xml:lang="en"><surname>Modovov</surname><given-names>N.</given-names></name></name-alternatives><bio xml:lang="ru"><p>Нурбол Алимбаевич Модовов – докторант 1 курса образовательной программы «Системы информационной безопасности»</p><p>050040, Казахстан, г. Алматы, пр. аль-Фараби, 71</p></bio><bio xml:lang="en"><p>Nurbol Modovov – 1st-year PhD doctoral student of the Information Security Systems educational program</p><p> 050040, 71 Al-Farabi Ave., Almaty, Kazakhstan </p></bio><email xlink:type="simple">modovov@gmail.com</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0002-9117-4369</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Мекебаев</surname><given-names>Н. О.</given-names></name><name name-style="western" xml:lang="en"><surname>Mekebayev</surname><given-names>N.</given-names></name></name-alternatives><bio xml:lang="ru"><p>Нурбапа Отанович Мекебаев – PhD, ассоциированный профессор кафедры информатики</p><p>050040, Казахстан, г. Алматы, пр. аль-Фараби, 71</p><p>050000, г. Алматы, Казахстан, ул. Гоголь 114 к1</p><p> </p></bio><bio xml:lang="en"><p>Nurbapa Mekebayev – PhD, Associate Professor, Department of Informatics</p><p>050040, 71 Al-Farabi Ave., Almaty, Kazakhstan</p><p>050000, 114 Gogol St., Almaty, Kazakhstan</p></bio><email xlink:type="simple">nurbapa80@gmail.com</email><xref ref-type="aff" rid="aff-2"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0002-5121-5867</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Тлеубаева</surname><given-names>А. Б.</given-names></name><name name-style="western" xml:lang="en"><surname>Tleubayeva</surname><given-names>A.</given-names></name></name-alternatives><bio xml:lang="ru"><p>Аксауле Болатовна Тлеубаева – магистр</p><p>071412, Казахстан, г. Семей, ул. Глинки, 20 А</p></bio><bio xml:lang="en"><p>Aksaule Tleubayeva – Master's degree holder</p><p> 071412, 20A Glinka St., Semey, Kazakhstan </p></bio><email xlink:type="simple">a.tleybaeva@shakarim.kz</email><xref ref-type="aff" rid="aff-3"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0009-0009-3231-1413</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Белгожа</surname><given-names>О. М.</given-names></name><name name-style="western" xml:lang="en"><surname>Belgozha</surname><given-names>O.</given-names></name></name-alternatives><bio xml:lang="ru"><p>Оркен Муратханович Белгожа – магистр</p><p>050000, г. Алматы, Казахстан, ул. Гоголь 114 к1</p></bio><bio xml:lang="en"><p>Оrken Belgozha – Master’s degree holder, Lecturer of the Department of Computer Science</p><p>050000, 114 Gogol St., Almaty, Kazakhstan</p></bio><email xlink:type="simple">orkenbelkoja@gmail.com</email><xref ref-type="aff" rid="aff-4"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0009-0005-8681-8835</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Сыдықжан</surname><given-names>I. А.</given-names></name><name name-style="western" xml:lang="en"><surname>Sydykzhan</surname><given-names>I.</given-names></name></name-alternatives><bio xml:lang="ru"><p>Інжу Айдарқызы Сыдықжан – магистр</p><p>050000, г. Алматы, Казахстан, ул. Гоголь 114 к1</p></bio><bio xml:lang="en"><p>Inzhu Sydykzhan – Master’s degree holder</p><p>050000, 114 Gogol St., Almaty, Kazakhstan</p></bio><email xlink:type="simple">inzhusydykzhan@gmail.com</email><xref ref-type="aff" rid="aff-4"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Казахский национальный университет имени аль-Фараби</institution><country>Казахстан</country></aff><aff xml:lang="en"><institution>Al-Farabi Kazakh National University </institution><country>Kazakhstan</country></aff></aff-alternatives><aff-alternatives id="aff-2"><aff xml:lang="ru"><institution>Казахский национальный университет имени аль-Фараби;&#13;
Казахский национальный женский педагогический университет</institution><country>Казахстан</country></aff><aff xml:lang="en"><institution>Al-Farabi Kazakh National University;&#13;
Kazakh National Women’s Teacher Training University</institution><country>Kazakhstan</country></aff></aff-alternatives><aff-alternatives id="aff-3"><aff xml:lang="ru"><institution>Шәкәрім университет</institution><country>Казахстан</country></aff><aff xml:lang="en"><institution>Shakarim University</institution><country>Kazakhstan</country></aff></aff-alternatives><aff-alternatives id="aff-4"><aff xml:lang="ru"><institution>Казахский национальный женский педагогический университет</institution><country>Казахстан</country></aff><aff xml:lang="en"><institution>Kazakh National Women’s Pedagogical University</institution><country>Kazakhstan</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2026</year></pub-date><pub-date pub-type="epub"><day>20</day><month>11</month><year>2026</year></pub-date><volume>0</volume><issue>3(23)</issue><fpage>15</fpage><lpage>22</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Модовов Н.А., Мекебаев Н.О., Тлеубаева А.Б., Белгожа О.М., Сыдықжан I.А., 2026</copyright-statement><copyright-year>2026</copyright-year><copyright-holder xml:lang="ru">Модовов Н.А., Мекебаев Н.О., Тлеубаева А.Б., Белгожа О.М., Сыдықжан I.А.</copyright-holder><copyright-holder xml:lang="en">Modovov N., Mekebayev N., Tleubayeva A., Belgozha O., Sydykzhan I.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://tech.vestnik.shakarim.kz/jour/article/view/2751">https://tech.vestnik.shakarim.kz/jour/article/view/2751</self-uri><abstract><p>Настоящая статья посвящена асимптотическому и формальному анализу вычислительной сложности не интерактивных доказательств с нулевым разглашением. Не интерактивные доказательства с нулевым разглашением позволяют доказывающей стороне подтвердить корректность некоторого утверждения проверяющей стороне без раскрытия какой-либо дополнительной информации и широко применяются в распределённых информационных системах. В ходе исследования схемы не интерактивных доказательств с нулевым разглашением рассматривались в модели общих исходных параметров (Common Reference String, CRS). При оценке вычислительной сложности в качестве основных параметров принимались временная сложность алгоритмов доказательства и проверки, размер свидетеля и длина доказательства. Эффективность алгоритмов анализировалась в рамках полиномиальной модели вычислений. Показано, что вычислительная сложность алгоритма доказательства существенно зависит от размера свидетеля, тогда как сложность алгоритма проверки в основном определяется длиной доказательства. Кроме того, рассмотрены асимптотические оценки размера доказательств и их влияние на коммуникационные издержки. Полученные результаты могут быть использованы в качестве теоретической основы для сравнительного анализа не интерактивных доказательств с нулевым разглашением и разработки криптографических протоколов с высокой вычислительной эффективностью.</p></abstract><trans-abstract xml:lang="en"><p>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.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>не интерактивные доказательства с нулевым разглашением</kwd><kwd>криптография</kwd><kwd>алгоритмы доказательства и проверки</kwd><kwd>полиномиальное время</kwd><kwd>вычислительная сложность</kwd></kwd-group><kwd-group xml:lang="en"><kwd>non-interactive zero-knowledge proofs</kwd><kwd>cryptography</kwd><kwd>proving and verification algorithms</kwd><kwd>polynomial time</kwd><kwd>computational complexity</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design – Oded Goldreich, Silvio Micali &amp; 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.</mixed-citation><mixed-citation xml:lang="en">How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design – Oded Goldreich, Silvio Micali &amp; 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.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Scalable, Transparent, and Post-Quantum Secure Computational Integrity / E. Ben-Sasson et al // IACR Cryptology ePrint Archive. – 2018. https://eprint.iacr.org/2018/046.</mixed-citation><mixed-citation xml:lang="en">Scalable, Transparent, and Post-Quantum Secure Computational Integrity / E. Ben-Sasson et al // IACR Cryptology ePrint Archive. – 2018. https://eprint.iacr.org/2018/046.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Micali S. Computationally Sound Proofs / S. Micali // SIAM Journal on Computing. – 2000. – № 30(4). https://doi.org/10.1137/S0097539795284959.</mixed-citation><mixed-citation xml:lang="en">Micali S. Computationally Sound Proofs / S. Micali // SIAM Journal on Computing. – 2000. – № 30(4). https://doi.org/10.1137/S0097539795284959.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge / N. Bitansky et al // ITCS. – 2012. https://doi.org/10.1145/2090236.2090263.</mixed-citation><mixed-citation xml:lang="en">From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge / N. Bitansky et al // ITCS. – 2012. https://doi.org/10.1145/2090236.2090263.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Succinct Non-Interactive Arguments / A. Chiesa et al // IACR Cryptology ePrint Archive. – 2012. https://doi.org/10.1007/978-3-642-40041-4_9.</mixed-citation><mixed-citation xml:lang="en">Succinct Non-Interactive Arguments / A. Chiesa et al // IACR Cryptology ePrint Archive. – 2012. https://doi.org/10.1007/978-3-642-40041-4_9.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Adaptive Security for Interactive Proofs / R. Canetti et al // TCC. – 2002. https://doi.org/10.1007/978-3-642-40041-4_9.</mixed-citation><mixed-citation xml:lang="en">Adaptive Security for Interactive Proofs / R. Canetti et al // TCC. – 2002. https://doi.org/10.1007/978-3-642-40041-4_9.</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">Katz J. Introduction to Modern Cryptography / J. Katz, Y. Lindell // Chapman and Hall/CRC. – 2014. https://doi.org/10.1201/9781351133036.</mixed-citation><mixed-citation xml:lang="en">Katz J. Introduction to Modern Cryptography / J. Katz, Y. Lindell // Chapman and Hall/CRC. – 2014. https://doi.org/10.1201/9781351133036.</mixed-citation></citation-alternatives></ref><ref id="cit15"><label>15</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
