Протокол сертификации целостности облачных вычислений
https://doi.org/10.15514/ISPRAS-2020-32(4)-8
Аннотация
В статье сформулирована задача сертификации целостности вычислений, проводимых стороной, которой мы не обязательно доверяем. Предложен интерактивный многопользовательский протокол решающий эту задачу при заданных ограничениях. По сравнению с ближайшим аналогом, предложенный протокол упрощает процедуру построения доказательства с O(nlogn) до O(n), а сложность коммуникации сводит к одному раунду при сопоставимой длине сертификата.
При поддержке: Благодарим Андрея Рыбкина и Михаила Бородина за конструктивную критику первой версии протокола: благодаря их замечаниям удалось обнаружить и устранить уязвимость в логике протокола. Мы также благодарим Джэйсона Тетча (Jason Teutsch) за конструктивную критику черновика статьи и за объяснения деталей протокола TrueBit.
Об авторах
Евгений Сергеевич ШИШКИН
ОАО «ИнфоТеКС»
Россия
ведущий исследователь научного отдела
Россия
ведущий исследователь научного отдела
Евгений Сергеевич КИСЛИЦЫН
Московский государственный университет имени М.В. Ломоносова
Россия
аспирант кафедры высшей алгебры механико-математического факультета
Россия
аспирант кафедры высшей алгебры механико-математического факультета
Список литературы
1. Appel A. W., Jim T. Continuation-passing, closure-passing style. In Proc. of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1989, pp. 293-302.
2. Benet J. Ipfs-content addressed, versioned, p2p file system. arXiv preprint, arXiv:1407.3561, 2014.
3. Biere A., Cimatti A., Clarke E., Zhu Y. Symbolic model checking without BDDs. Lecture Notes in Computer Science, vol. 1579, 1999, pp. 193-207.
4. Buterin V. What is Ethereum? Ethereum Official webpage. Available at: http://www.ethdocs.org/en/latest/introduction/what-is-ethereum.html, accessed 14.08.2020.
5. Cook S. A. The complexity of theorem-proving procedures. In Proc. of the Third Annual ACM Symposium on Theory of Computing, 1971, pp. 151-158.
6. Davis M., Logemann G., Loveland D. A machine program for theorem-proving. Communications of the ACM, vol. 5, no. 7, 1962, pp. 394-397.
7. Dershowitz N., Hanna Z., Nadel A. A scalable algorithm for minimal unsatisfiable core extraction. Lecture Notes in Computer Science, vol. 4221, 2006, pp. 36-41.
8. Goldwasser S., Kalai Y.T., Rothblum G.N. Delegating computation: interactive proofs for muggles. Journal of the ACM, vol. 62, no. 4, 2015, pp. 1-64.
9. Hopcroft J.E., Motwani R., Ullman J.D. Introduction to Automata Theory, Languages, and Computation: Pearson New International Edition. Pearson, 2013, 496 p.
10. Kochovski P., Gec S., Stankovski V., Bajec M., Drobintsev P.D. Trust management in a blockchain based fog computing platform with trustless smart oracles. Future Generation Computer Systems, vol. 101, 2019, pp. 747-759.
11. Luu L., Teutsch J., Kulkarni R., Saxena, P. Demystifying incentives in the consensus computer. In Proc. of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015, pp. 706-719.
12. Mandt T., Solnik M., Wang D. Demystifying the secure enclave processor. Available at: http://mista.nu/research/sep-paper.pdf, accessed 14.08.2020.
13. Parno B., Howell J., Gentry C., Raykova M. Pinocchio: Nearly practical verifiable computation. In Proc. of the IEEE Symposium on Security and Privacy, 2013, pp. 238-252.
14. Reynold, J. C. The discoveries of continuations. Lisp and symbolic computation, vol. 6, no. 3-4, 1993, pp. 233-247.
15. Setty S., Braun B., Vu V., Blumberg A. J., Parno B., Walfish M. Resolving the conflict between generality and plausibility in verified computation. In Proc. of the 8th ACM European Conference on Computer Systems, 2013, pp. 71-84.
16. Setty S., Vu V., Panpalia N., Braun B., Blumberg A. J., Walfish M. Taking proof-based verified computation a few steps closer to practicality. In Proc. of the 21st USENIX Security Symposium, 2012, pp. 253-268.
17. Teutsch J., Reitwießner C. A scalable verification solution for blockchains. arXiv preprint arXiv:1908.04756, 2019.
18. Thaler J. Time-optimal interactive proofs for circuit evaluation. Lecture Notes in Computer Science, vol. 8043, 2013, pp. 71-89.
19. Vollmer, H. Introduction to circuit complexity: a uniform approach. Springer Science & Business Media, 2013, 272 p.
20. Xie T., Zhang J., Zhang Y., Papamanthou C., Song D. Libra: Succinct zero-knowledge proofs with optimal prover computation. Lecture Notes in Computer Science, vol. 11694, 2019, pp. 733-764.
21. Верещагин Н.К., Шень, А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. Учебное пособие. МЦНМО, 2013, 160 стр. / Vereshchagin N.K., Shen A. Lectures on mathematical logic and theory of algorithms. Part 3. Computable functions. MCCME, 2013, 160 p. (in Russian).
22. Ложкин С. А. Лекции по основам кибернетики. Издательский отдел ф-та ВМиК МГУ, 2004 г., 251 стр. / Lozhkin S.A. Lectures on the basics of cybernetics. Publishing department of the Faculty of Computational Mathematics and Cybernetics, Moscow State University, 2004, 251 p. (in Russian).
Рецензия
Для цитирования:
ШИШКИН Е.С., КИСЛИЦЫН Е.С. Протокол сертификации целостности облачных вычислений. Труды Института системного программирования РАН. 2020;32(4):115-132. https://doi.org/10.15514/ISPRAS-2020-32(4)-8
For citation:
SHISHKIN E.S., KISLITSYN E.S. Protocol for Certifying Cloud Computations Integrity. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2020;32(4):115-132. (In Russ.) https://doi.org/10.15514/ISPRAS-2020-32(4)-8
Послать статью по эл. почте 