Loading...

Integrity Checking of Outsourced Computations with Distributed Data Sources

Dolatnezhad, Somayeh | 2021

226 Viewed
  1. Type of Document: Ph.D. Dissertation
  2. Language: Farsi
  3. Document No: 54654 (19)
  4. University: Sharif University of Technology
  5. Department: Computer Engineering
  6. Advisor(s): Amini, Morteza
  7. Abstract:
  8. In recent years, one of the research interests is ensuring the integrity of computations done on data received from multiple data sources. Limited research has been done to ensure the integrity of computations that the output depends on data generated by different data sources. However, there are many solutions for systems that the input data is generated by a single data source. In this thesis, ensuring the integrity of multi-source aggregate functions and general functions are investigated in an untrusted server. To verify the integrity of aggregate functions, first of all, we present a construction for verifying the results of linear functions using the RSA signature. It should be noted that in this construction, the verification cost is constant and does not growth with increasing the number of data sources. Then, using this construction, we proposed a new construction for verifying the integrity of the aggregate functions and range queries. Finally, the proposed solutions have been extended for window based queries. The proposed constructions are secure based on the RSA problem in the random oracle model and have the correctness and succinctness properties. Experimental results show that the communication and computation costs of the constructions are acceptable in practice and the proposed solution can be employed for real-world applications The second part of the thesis tries to provide a solution to ensure the integrity of the output of various functions in the model with multiple data sources. In this part of the thesis, we propose a new generic compiler to convert an SKHS scheme into an MKHS scheme. Our compiler is a generalization of the Matrioska compiler of Fiore and Pagnin for homomorphic signatures that support programs in any model of computation. As an additional contribution, we show how to instantiate our generic compiler in the Turing Machines (TM) model and argue that this instantiation allows to overcome some limitations of Matrioska. First, the MKHS we obtain require the underlying SKHS to support TMs whose size depends only linearly in the number of users. Second, when instantiated with an SKHS with succinctness $poly(\lambda)$ and fast enough verification time, e.g., S+ logT+npoly(λ) or T+npoly(λ) (where T, S and n are the running time, description size, and input length of the program to verify, respectively), our compiler yields an MKHS in which the time complexity of both the prover and the verifier remains poly(λ) even if executed on programs with inputs from $poly(\lambda)$ users. While we leave constructing an SKHS with these efficiency properties as an open problem, we make one step towards this goal by proposing an SKHS scheme with verification time Tpoly(λ) under falsifiable assumptions in the standard model
  9. Keywords:
  10. Data Security ; Turing Machine ; Computational Security ; Computation Outsourcing ; Computation Integrity ; Homomorphic Authenticators

 Digital Object List

 Bookmark

No TOC