Research And Application Of Order-preserving Encryption In Database System

The current popularity of novel network application has led to explosive growth of user data,resulting in increasingly high maintenance and management costs for local data storage.As a result,more and more users choose to outsource data to the remote servers with centralized storage and computing resources.However,handing over data to others incurs higher risks of privacy and data leakage.Encryption technology can ensure data security,but simple encryption makes the database lose computing capabilities of ciphertexts.Considering private data security and availability,functional encryption is proposed to perform specific operations on ciphertexts directly and efficiently.In order to realize the numerical operations on ciphertexts like data comparion,sorting,and range query,order-preserving encryption scheme,OPE,is proposed,which can rebuild the numerical sequence order of the underlying plaintexts on the ciphertexts.Popa et al.'s mutable OPE scheme is an effective solution to performing numerical comparison with ideal security in the encrypted database environment,but due to the frequent interactions and redundant updates,it only achieves a low efficiency.To solve the above problems,the major work of this thesis is summarized as follows.(1)An encoding relaxed updating algorithm for mutable order-preserving encoding,ERU,is proposed,which alleviates the problem of redundant updates and time costs during maintenance of the obsolete codes.ERU is designed to update the lookup table only when necessary,which keeps a relaxed update state for mutable codes.It accurately determines whether to update the lookup table according to the type of query and historical operation information.The update efficiency of ERU has reached more than 3 times that of mOPE,and the whole update costs is reduced by 70%.In scenarios where high-frequency modification to the OPE tree is required,the update performance of ERU has outstanding advantages.(2)A threshold first searching algorithm based on the boundary search tree,TFS,is established,which reduces the impact of frequent interaction and comparison on encryption performance in the interactive tree search of mOPE.TFS constructs a novel data structure,called the boundary search tree.It utilizes subtree boundary in the tree to finely divide the search domain for each iteration,positioning the node more effectively and reducing the cost of communication between entities,which improves the encryption performance.The number of iteractions in TFS is reduced by more than 10% with the mOPE,and the encryption efficiency also achieves obvious advantages.Under the sequential configuration,the encryption efficiency of TFS can reach more than 5 times that of mOPE,and the interaction costs is reduced by 90%.(3)A boundary order-preserving encryption algorithm,BOPE,is designed,which is well adapted to the tripartite architecture of the encrypted database system,supports direct numerical order comparison on ciphertexts,and achieves the ideal order-preserving security in practice.BOPE effectively reduces the number of communications between entities in the interactive scheme,and improves the efficiency of order-preserving encryption and ciphertext order calculation.For the random instruction sets,BOPE achieves a performance increase of more than 10% on average from mOPE.When a large amount of ordered data needs to be order-preserving encrypted,BOPE can achieve a more significant performance improvement.