Preview

Труды Института системного программирования РАН

Расширенный поиск

Протокол сертификации целостности облачных вычислений

https://doi.org/10.15514/ISPRAS-2020-32(4)-8

Полный текст:

Аннотация

В статье сформулирована задача сертификации целостности вычислений, проводимых стороной, которой мы не обязательно доверяем. Предложен интерактивный многопользовательский протокол решающий эту задачу при заданных ограничениях. По сравнению с ближайшим аналогом, предложенный протокол упрощает процедуру построения доказательства с O(nlogn) до O(n), а сложность коммуникации сводит к одному раунду при сопоставимой длине сертификата.

Об авторах

Евгений Сергеевич ШИШКИН
ОАО «ИнфоТеКС»
Россия
ведущий исследователь научного отдела


Евгений Сергеевич КИСЛИЦЫН
Московский государственный университет имени М.В. Ломоносова
Россия
аспирант кафедры высшей алгебры механико-математического факультета


Список литературы

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

Просмотров: 59


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)