Binary-Tree-Structured Multi-User Oblivious RAM Scheme

Massive amounts of data sharing and access led to the rapid development of network technology. Combining with the traditional computer applications, the new cloud computing model produced. Cloud computing with its fault-tolerant, low-cost advantages obtained extensive research and application. At the same time, its safety has become the focus of public attention. In the backdrop of the rapid development of cloud computing and data mining, the address sequence generated by the interaction of the users and the server(access pattern) will result in disclosure of user privacy. Information retrieval, oblivious RAM technology and dynamically allocated data structures can effectively protect the user’s access pattern. Among them, the oblivious RAM technology-a newcomer of cryptographic primitives as an extremely effective method has become a hotspot of research scholars at home and abroad.The principle of the oblivious RAM technology is to make the program complicated. In other words, split one step into random multi-step so as to achieve the purpose of protecting user’s access pattern and ensure the access operation of oblivious. There are many implementations of oblivious RAM technology, for example, hierarchical solution, binary-tree-structured multi-user oblivious RAM scheme, oblivious RAM scheme having computing power. In the existing solution, basically a single-user solution. But, in practical applications, users want to share their own data that they stored to the cloud server with other users. Therefore, multi-user oblivious RAM scheme has a strong practical background. In 2014, Zhang et al first proposed a multi-user oblivious RAM scheme of a real sense. However, the access cost is expensive. Therefore, it is necessary to design more efficient multi-user oblivious RAM scheme.In order to achieve data share in specific user groups, proxy must be introduced as a bridge between users and servers. The proxy encryption scheme with authorized functions is expensive. And in this paper, it does not involve the authority within the user groups in data access. So only need to use a simple and efficient proxy encryption scheme without authorized functions. In this paper, design a new proxy encryption scheme that is similar to the prototype of the proxy encryption of Dong et. The new proxy encryption scheme greatly reduces the amount of data that needs to be stored on the proxy. In the same time, the security of the new proxy encryption scheme did not decrease.This paper designs a binary-tree-structured multi-user oblivious RAM scheme (BTS-M ORAM) using the new proxy encryption scheme. The BTS-M ORAM scheme has two design innovations. The first innovation is that data on the server is stored and organized in a binary tree, not like Zhang et al, who used hierarchical solution, which greatly improves the efficiency of the data access. The second innovation is using the new proxy encryption scheme, which greatly reduces the amount of data that needs to be stored on the proxy at the same level of security. Based on the BTS-M ORAM scheme, this paper designs a new recursive binary-tree-structured multi-user oblivious RAM scheme (R-BTS-M ORAM) referencing the recursive method of Shi et al, which successfully eliminates the position map need to store on the proxy and further reduces the amount of data stored on the proxy.This paper firstly introduces the concept and development process of the oblivious RAM technology and the proxy encryption mechanism and the working principle of the binary-tree-structured single-user oblivious RAM scheme. Then, describe in detail the modified new proxy encryption scheme and analysis the security of the new scheme. Finally, design the BTS-M ORAM and R-BTS-M ORAM using the new proxy encryption scheme. The two schemes have their choice of suitable applications according to the trade-offs between space and efficiency. With respect to the existing multi-user oblivious RAM scheme, the access efficiency of the two schemes has been greatly improved. Therefore, the present work has a certain significance.