How to protect your privacy in a zero-trust network? Introduction to the oblivious random access machine

When we watch spy movies, we often see underground party members making contact. In order to prevent themselves from being followed, they have to go around in circles, sit here for a while, stay there for a while, buy something here, and chat there. The purpose is to prevent themselves from being followed and thus expose their comrades. After all, if a spy finds out that a suspect goes to a roadside stall to buy pancakes every day, even if it means taking a detour. Then the person selling pancakes is likely to be the contact person, and they may be arrested together. Therefore, people who do this kind of work usually need to avoid their main destination being discovered as much as possible, so they will protect the person they are contacting by doing some random things.

In the Internet age, all kinds of important information are communicated on the Internet, so it is inevitable that they will be monitored and stolen by people with ulterior motives. After all, we live in a zero-trust network (), so we need to process every important access. Usually, we use various encryption algorithms to protect our data privacy. For example, when uploading important data such as ID number, user name, password, home address, etc., this data must be encrypted. Usually we use symmetric encryption algorithms such as AES, DES, 3DES, Blowfish, RC6, etc., or asymmetric encryption, such as RSA, DSA, ECC, Diffie-Hellman, etc. And some hash algorithms, such as MD5, SHA, WHIRLPOOL, etc.

However, these encryption technologies only encrypt the information itself, ensuring that the information itself is difficult to be cracked by a third party, but the user's access to the information is not protected. Attackers can infer a lot of private information about users by monitoring the user's access mode and access process to the data, such as the importance of the data, the relevance of the data, and even infer the content of the encrypted data through some methods. This information will expose some important behavioral characteristics of the user, such as hobbies, social circles, etc. For example, if an important person often searches for a certain type of medicine, it is very likely that he suffers from a certain disease.

Therefore, in the application scenarios of the information age, simply encrypting the content of the data itself cannot completely protect the user's privacy. The protection of the user's access mode and access process is also a key area.

Many people have heard of a story that the Japanese determined a lot of information about Daqing Oilfield, China's largest oil base at the time, from a photo of Wang Jinxi in China Pictorial in 1966. For example, they determined from Wang Jinxi's clothes that he only needed to dress like that in the area between 46 and 48 degrees north latitude, so the oilfield was located between Qiqihar and Harbin. From the way Wang Jinxi held the handle, they inferred the type of oil well, etc.

Whether this story is true or not, in a zero-trust network, hiding these revealing details is obviously necessary. Especially as technology develops and more and more data is stored in the cloud, it becomes more and more important to protect users' access patterns.

The random access machine is an important means of protecting access patterns and access processes. The purpose of this technology is to hide access to real data, so that attackers cannot distinguish whether each access is real or random, just like spies cannot tell whether comrades are really buying pancakes or exchanging information. The use of random access machines can effectively prevent attackers from using access patterns to obtain private information, reduce the attack surface of information storage systems, break the system framework that simply uses traditional encryption methods to protect data privacy, and provide users with more secure cloud services. This is of great significance to the design of a more secure and efficient distributed computing framework.

However, using random access machines inevitably brings additional system overhead. In order to hide the access pattern, multiple data need to be accessed randomly, which undoubtedly increases the overhead of the client and the server. It is like exchanging information. Originally, you only need to visit a pancake stall, but you end up visiting a pancake stall, a kebab stall, a fruit stall, etc.

The concept of oblivious RAM (ORAM) originated from the RAM (Random Access Machine) model. RAM is an important computing simulation method. The processor executes the program by reading and writing the memory. In the 1980s, in order to hide the program's access mode to the memory to avoid software reverse engineering, Goldriche et al. proposed the ORAM model on this basis. In this model, any data block in the memory will not permanently reside in a certain physical address, which ensures that any two accesses will not be associated. At the same time, ORAM breaks down each read and write access into an atomic operation of one read and one write back. Among them, the read access is converted into reading the content and then writing the same content, and the write access is converted into reading the content and then writing back the updated content, so that attackers cannot distinguish the specific access method.

The ORAM model can well protect the following four properties:

1. The location of the access data block;

2. The order in which data blocks are requested;

3. Frequency of access to the same data block;

4. Specific read and write access methods.

This means that after the access is over, the attacker cannot judge the user's true intentions based on the access pattern, effectively protecting the user's personal privacy.

Currently, ORAM has been applied in many fields, and researchers are still optimizing its functions and performance. ​