Hiding big data access patterns
Methods, systems, and apparatuses for disguising or otherwise hiding big data access patterns and frequencies may include a replica being directly obtained from a key and a replica index, based on applying a pseudorandom permutation or pseudorandom function. Data object access frequencies may be quantized so that the ratios of quantized data object access frequencies are rational numbers of integers, which may allow for a uniform distribution of data object accesses. Fake accesses may be implemented by simulating an access schedule produced by a cryptographic primitive and by performing a greedy mapping between the real data object accesses and simulated data object accesses.
1. An apparatus comprising:
one or more processors; and
a memory coupled with the one or more processors, the memory storing executable instructions that when executed by the one or more processors cause the apparatus to:
receive a key of a first data object;
receive a frequency number associated with an initial data object access within a period;
determine a number of replicas associated with the first data object, based on the frequency number;
obtain a replica index based on a random number;
append the replica index to the key to create a replica-key identifier (ID);
create a bit string based on the replica-key ID;
generate a schedule of a set of simulated data object accesses based on a first random function associated with the replica-key ID; and
perform a first look up on a first data structure based on the schedule.
2. The apparatus of claim 1 , wherein when the one or more processors further execute the instructions, the apparatus is configured to:
perform a second look up on a second data structure, based on the bit string.
3. The apparatus of claim 1 , wherein when the one or more processors further execute the instructions, the apparatus is configured to:
determine a mapping of a set of real data object accesses to the set of simulated data object accesses;
determine, based on the mapping of the set of the real data object accesses to the set of the simulated data object accesses, an unused slot associated with a simulated data object access not being mapped; and
select a fake data object access to map to the simulated data object access, based on the determine of the unused slot.
4. The apparatus of claim 3 , wherein the select is based on a second random function.
5. The apparatus of claim 2 , wherein the first data structure comprises a search tree, a lookup table, a hash table, linked lists, a directed acyclic graph, or heaps.
6. The apparatus of claim 1 , wherein the frequency number is obtained from a table of frequency numbers associated with a plurality of data objects.
7. The apparatus of claim 2 , wherein the create the bit string comprises encrypting and truncating the replica-key ID.
8. The apparatus of claim 1 , wherein the frequency number is a multiple of a frequency quantum.
9. The apparatus of claim 8 , wherein the frequency quantum is determined using linear optimization or nonlinear optimization.
10. A method comprising:
receiving a key of a first data object;
receiving a frequency number associated with an initial data object access within a period;
determining a number of replicas associated with the first data object, based on the frequency number;
obtaining a replica index based on a random number;
appending the replica index to the key to create a replica-key identifier (ID);
creating a bit string based on the replica-key ID; and
generating a schedule of a set of simulated data object accesses based on a first random function associated with the replica-key ID.
11. The method of claim 10 , further comprising:
performing a lookup on a data structure, based on the bit string.
12. The method of claim 10 , further comprising:
determining a mapping of a set of real data object accesses to the set of the simulated data object accesses;
determining, based on the mapping of the set of the real data object accesses to the set of simulated data object accesses, an unused slot associated with a simulated data object access not being mapped; and
selecting a fake data object access to map to the simulated data object access, based on the determining of the unused slot.
13. The method of claim 12 , wherein the selecting is based on a second random function.
14. The method of claim 11 , wherein the data structure comprises a search tree, a lookup table, a hash table, linked lists, a directed acyclic graph, or heaps.
15. The method of claim 10 , wherein the frequency number is obtained from a table of frequency numbers associated with a plurality of data objects.
16. The method of claim 11 , wherein the creating the bit string comprises encrypting and truncating the replica-key ID.
17. A computer-readable storage medium storing computer executable instructions that when executed by a computing device causes the computing device to effectuate operations comprising:
receiving a key of a first data object;
receiving a frequency number associated with an initial data object access within a period;
determining a number of replicas associated with the first data object, based on the frequency number;
obtaining a replica index based on a random number;
appending the replica index to the key to create a replica-key identifier (ID);
creating a bit string based on the replica-key ID; and
generating a schedule of a set of simulated data object accesses based on a first random function associated with the replica-key ID.
18. The computer-readable storage medium of claim 17 , wherein when the instructions are further executed by the computing device causes the computing device to effectuate operations comprising:
determining a mapping of a set of real data object accesses to the set of simulated data object accesses;
determining, based on the mapping of the set of the real data object accesses to the set of the simulated data object accesses, an unused slot associated with a simulated data object access not being mapped; and
selecting a fake data object access to map to the simulated data object access, based on the determining of the unused slot.
19. The computer-readable storage medium of claim 18 , wherein the selecting is based on a second random function.
20. The computer-readable storage medium of claim 17 , wherein when the instructions are further executed by the computing device causes the computing device to effectuate operations comprising:
performing a lookup on a data structure, based on the bit string.