АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ НЕИНТЕРАКТИВНЫХ ДОКАЗАТЕЛЬСТВ С НУЛЕВЫМ РАЗГЛАШЕНИЕМ
https://doi.org/10.53360/2788-7995-2026-3(23)-2
Аннотация
Настоящая статья посвящена асимптотическому и формальному анализу вычислительной сложности не интерактивных доказательств с нулевым разглашением. Не интерактивные доказательства с нулевым разглашением позволяют доказывающей стороне подтвердить корректность некоторого утверждения проверяющей стороне без раскрытия какой-либо дополнительной информации и широко применяются в распределённых информационных системах. В ходе исследования схемы не интерактивных доказательств с нулевым разглашением рассматривались в модели общих исходных параметров (Common Reference String, CRS). При оценке вычислительной сложности в качестве основных параметров принимались временная сложность алгоритмов доказательства и проверки, размер свидетеля и длина доказательства. Эффективность алгоритмов анализировалась в рамках полиномиальной модели вычислений. Показано, что вычислительная сложность алгоритма доказательства существенно зависит от размера свидетеля, тогда как сложность алгоритма проверки в основном определяется длиной доказательства. Кроме того, рассмотрены асимптотические оценки размера доказательств и их влияние на коммуникационные издержки. Полученные результаты могут быть использованы в качестве теоретической основы для сравнительного анализа не интерактивных доказательств с нулевым разглашением и разработки криптографических протоколов с высокой вычислительной эффективностью.
Об авторах
Н. А. МодововКазахстан
Нурбол Алимбаевич Модовов – докторант 1 курса образовательной программы «Системы информационной безопасности»
050040, Казахстан, г. Алматы, пр. аль-Фараби, 71
Н. О. Мекебаев
Казахстан
Нурбапа Отанович Мекебаев – PhD, ассоциированный профессор кафедры информатики
050040, Казахстан, г. Алматы, пр. аль-Фараби, 71
050000, г. Алматы, Казахстан, ул. Гоголь 114 к1
А. Б. Тлеубаева
Казахстан
Аксауле Болатовна Тлеубаева – магистр
071412, Казахстан, г. Семей, ул. Глинки, 20 А
О. М. Белгожа
Казахстан
Оркен Муратханович Белгожа – магистр
050000, г. Алматы, Казахстан, ул. Гоголь 114 к1
I. А. Сыдықжан
Казахстан
Інжу Айдарқызы Сыдықжан – магистр
050000, г. Алматы, Казахстан, ул. Гоголь 114 к1
Список литературы
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.
Рецензия
Для цитирования:
Модовов Н.А., Мекебаев Н.О., Тлеубаева А.Б., Белгожа О.М., Сыдықжан I.А. АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ НЕИНТЕРАКТИВНЫХ ДОКАЗАТЕЛЬСТВ С НУЛЕВЫМ РАЗГЛАШЕНИЕМ. Вестник Университета Шакарима. Серия технические науки. 2026;(3(23)):15-22. https://doi.org/10.53360/2788-7995-2026-3(23)-2
For citation:
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















