Research Of Some Problems In The Theory Of Verifiable Computing

With the development of modern computation environment,it becomes more and more open,connected,distributed and dynamic,where numerous devices,mach-ines and database are involved in interactive computation and may not trust each other, it is important to ensure integrity and generate trust of computation in this kind of environment.The theory of proof-based trustiness reinterprets trustworthiness as verifia-bility. To entrust computation, delegator (prover) should give a proof to convince the user (verifier). The theory of proof-based trustiness stems in the theory of interactive proof system and develops through a series of beautiful works into ver-ifiable computation especially the theory of succinct noninteractive argument of knowledge, and its extension including data delegation and proof carrying data.In this thesis, we study some important problems concerning the verifiable computing system,such as extractablity and unobfuscablity,succinct argument system based on quadratic span program, data delegation based on cubic span program and proof carrying data for conditional data flow.As we know,the security of succinct argument for NP is bound to be founded on extractable hypothesis which is non-falsifiable and non-black-box techniques are needed to founded it on the standard falsifiable assumptions. So the rela-tion between extractable primitives and other cryptographic primitives is theo-retical important,especially the relation with unobfuscablity function family in recent non-black-box techniques.We introduce the concept of extractable evalu-ator,discuss the equivalence of succinct argument and extractable evaluator and prove that extractable hash functions actually implies the unobfuscablity hash function family.Quadratic span program based succinct argument is one of important con-struction of public verifiable succinct argument,in this thesis,we improve quadrat-ic span program based succinct argument in various way,estimating the wire gate and wire checker in the construction of quadratic span program,resulting in a construction which is much more conceptual simple,efficient,flexible and finally with a new knowledge extractor.Data delegation is one important extension of succinct argument system,current construction of it utilizes heavy machinery of probabilistic checkable proof and full homomorphic encryption,and the latter could be the barrier of efficiency.We give a new construction of data delegation based on cubic span program free from probabilistic checkable proof and full homomorphic encryption.Particularly,the store-retrieve part of our data delegation system can be used as the independent subsystem as a verifiable storage system.Proof carrying data system which naturally extends the notion of incrementally-verifiable computation to arbitrary distributed computations, attaches any data in the distributed environment with proofs,which assert not only the correctness of the computation of the party itself, but rather the correctness of all the compu-tation done by all the parties involved in the flow of computation. Current proof carrying data system is limited to static data flow without conditional edges and can only handle data flow with polynomial interaction complexity which could be exponential of its depth.We generalize proof carrying data system for any conditional data flow and improve the scale of proof carrying data to data flow of polynomial depth respect to the security parameter, rather than the interac-tion complexity of the flow,which is crucial for data flow with high interaction complexity.