Research On Digital Signature And Graph Algorithm Security Outsourcing Computing

In recent years,as a new type of computation mode,cloud computing has received wide attention from all communities and is also developing rapidly.Cloud servers can provide computing resources,storage space and other support for resource-constrained users.In outsourcing computation,clients can submit their complex computing tasks to the cloud server and ask the cloud server to finish them to save costs and improve efficiency.In this way,the client could save costs and improve efficiency.However,fully trusted cloud servers are rare in real-world applications.Untrusted cloud servers might steal clients’ privacy and cheat clients.Therefore,a secure outsourcing computation scheme should ensure that the clients’ privacy will not disclose and the clients can verify the correctness of the results returned by the cloud.Besides,clients’ computation costs in the outsourcing computation scheme should be less than the computation costs that take clients to finish this work locally,otherwise outsource computing will be meaningless.In the research of secure outsourcing computation,how to design a secure outsourcing computation scheme that meets the three requirements of security,efficiency and verifiability is a problem worthy of study.This thesis studies the application of secure outsourcing computation technology in digital signature and graph algorithms,and proposes three secure outsourcing computation schemes for three specific problems:(1)The generation of El Gamal signature involves modular exponentiation,which could not be afforded by resource-constrained clients.The base of the modular exponentiation in El Gamal signature scheme is public parameter which does not require to be kept secretly.We take advantage of this feature to improve existing secure outsourcing scheme,and design a secure outsourcing scheme for generating El Gamal digital signature.In our scheme,we outsource modular exponentiations and modular inversions,and improve the efficiency significantly.The security analysis proves that the scheme meets the security,efficiency and checkability of secure outsourcing computation.(2)There is large amount of modular exponentiation in ring signature generation in public cloud storage auditing.We notice that most of the bases of modular exponentiations in signature generation are public parameters,and they do not need to be kept secretly.By taking advantage of this feature,we improve existing secure outsourcing scheme and design a secure outsourcing scheme for this problem.In our scheme,we divide the signature generation into some sub-problems and outsource them respectively.The security analysis and the experimental result prove that the scheme meets the security,efficiency and checkability of secure outsourcing computation.(3)We design secure outsourcing schemes for min-cut of undirected edge-weighted graphs.In our schemes,we protect the privacy of graphs by merging and divide vertices and edges.We also develop verification mechanisms which make the client could verify the correctness of the result produced by a single untrusted cloud server and two untrusted non-colluding cloud servers.The security analysis and the experimental result prove that the scheme meets the security,efficiency and checkability of secure outsourcing computation.