Design And Implementation Of Fundamental Algorithms Considered Privacy Protection On HADOOP

With the advent of big data,in order to process big data more efficient ly and economically,people usually transfer data to the public cloud and process data in parallel.MapReduce is one of the most popular parallel programming paradigms.Finding out more effic ient algorithms for MapReduce to solve fundamental problems has always been one of the research hotspots.However,there is a security risk of information leakage in the cloud processing data.Therefore,this thesis mainly focuses on three fundamental problems,Joins,Grouping and Aggregation and Matrix Multiplication.The goal is to add privacy guarantees to those algorithms which were come up with to solve problems mentioned above for MapReduce.In this thesis,we assume that the data is externalized in an honest-but-curious server(i.e.,it executes dutifully but tries to learn the information about input data as much as possible).And a user is allowed to query the results.Meanwhile,this thesis proposes two security concepts:(1)Secure-Private(SP): assuming that the public cloud and the user do not collude,the cloud learns nothing about input data or final results and the user who queries the cloud learns nothing else than the final results.(2)Collision-Resistant-Secure-Private(CRSP): Even if the public cloud and the user collude,which means that the public cloud knows the private key of the user,the cloud learns nothing about input data or final results and the user learns nothing else than the final results.For Grouping and Aggregation,this thesis proposes and implements the algorithm that satisfies the first security concept.For the other problems,this thesis proposes and implements two algorithms that satisfy both security concepts respectively.In addition,this thesis also designs and implements a new MapReduce matrix mult iplication algorithm based on Strassen-Winograd algorithm and also adds privacy guarantees to it.Furthermore,the thesis analyzes and compares the trade-offs of all those algorithms with respect to three fundamental criteria: computation cost,communication cost,and privacy guarantees.