# US 2019/0377884 A1 · Oblivious array shuffling in trusted execution environments

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0377884 A1
- Document ID: US20190377884A1
- Status: Published application
- Kind: A1
- Application number: 16/006,665
- Filed: 2018-06-12
- Published: 2019-12-12
- Earliest claimed: 2018-06-12
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Avradip MANDAL
- Web page: https://patentgrep.com/patent/US20190377884A1

## CPC

- G06F 21/60: Protecting data
- G06F 21/6254: {by anonymising data, e.g. decorrelating personal data from the owner's identification}
- G06F 21/53: by executing in a restricted environment, e.g. sandbox or secure virtual machine
- G06F 21/71: to assure secure computing or processing of information
- G09C 1/00: Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00)
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords}
- H04L 2209/50: Oblivious transfer
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G09C: CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method of approximate address shuffling of an array includes receiving an array having an array size and non-null elements located in initial locations. The method includes receiving a pseudo-random function (PRF) key and initializing an output array to null. The method includes shuffling the non-null elements to generate shuffled locations for the non-null elements. The shuffling may include determining an intermediate shuffled location for a first non-null element. If a location in the output array corresponding to the intermediate shuffled location is null, the shuffling may include outputting a shuffled location as the intermediate shuffled location. If not, the shuffling may include generating an updated intermediate shuffled location. The method includes returning the output array having the first non-null element the location in the output array corresponding to the shuffled location.

## Claims

### Claim 1

A method of approximate address shuffling of an array, the method comprising:
receiving an array having an array size and two or more non-null elements located in initial-arbitrary locations in the array;
receiving a pseudo-random function (PRF) key;
initializing an output array to null;
shuffling at least a portion of the non-null elements to generate shuffled locations for the non-null elements, the shuffling of a first non-null element of the non-null elements including:
determining an intermediate shuffled location for the first non-null element as an application a PRF to the PRF key and the first non-null element modulo a modulo element;
responsive to a location in the output array corresponding to the intermediate shuffled location being null, outputting a shuffled location in the output array for the first non-null element as the intermediate shuffled location;
response to the location in the output array corresponding to the intermediate shuffled location not being null, generating an updated intermediate shuffled location to a sum of the intermediate shuffled location and one modulo the array size; and
responsive to a location in the output array corresponding to the updated intermediate shuffled location being null, outputting the shuffled location in the output array for the first non-null element as the updated intermediate shuffled location; and
returning the output array having the first non-null element in the location in the output array that corresponds to the shuffled location.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
determining whether a number of the non-null elements are above a particular threshold;
in response to the number of the non-null elements being above the particular threshold:
choosing a random PRF key; and
sorting, using a memory-oblivious sort, the non-null elements based on application of the PRF to the random PRF key and the non-null elements.

### Claim 3 (depends on 2)

The method of claim 2, wherein the determining the intermediate shuffled location for the first non-null element further includes a difference between the application the PRF to the PRF key and the first non-null element modulo the modulo element and a shifted parameter.

### Claim 4 (depends on 3)

The method of claim 3, wherein the sorting includes sorting according to an odd-even merge sort.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
dividing the output array into multiple buckets, each of the multiple buckets having a bucket size that is less than a cache size of a trusted execution environment that stores the output array;
relocating the non-null elements of the received array from the initial-arbitrary locations to first locations in the received array;
filling a first bucket of the multiple buckets with a first subset of the non-null elements, the first subset including the non-null elements having a first aggregate size that is less than the bucket size; and
filling a second bucket of the multiple buckets with a second subset of the non-null elements, the second subset including the non-null elements having a second aggregate size that is less than the bucket size,
wherein the shuffling the at least a portion of the non-null elements includes shuffling the first subset in the first bucket independently of the second subset in the second bucket.

### Claim 6 (depends on 5)

The method of claim 5, wherein:
the filling of the first bucket is performed using a Boolean overflow expression; and
the filling of the first bucket is performed according to the expressions:
For i in range (n/(m*s))
count = 0;
For j in range (t)
overflow = overflow [j]
out_msi = out [m*s*i]
inp_j = inp [j]
opt_pos = PRF (k, inp_j) % n
if (count < m*s):
out [m*s*i + count] = inp_j
if (overflow == true)
count = count + 1
else
if (opt_pos >= m*s*i && opt_pos < m*s*(i+1))
count = count + 1
overflow[j] = false
else
out [m*s*i] = out_mki
if (opt_pos >=m*s*i && opt_pos < m*s*(i+1))
overflow[j] = true
else
overflow [j] = overflow, in which:
i represents an indexing variable that represents the bucket;
n represents the array size;
m represents a number of available cache lines;
s represents a number of objects that fit into one of the number of
available cache lines;
count represents a counting index variable;
j represents an indexing variable;
out[ ] represents an element in the output array;
out_pos represents an intermediate output value;
out_msi represents another intermediate output value;
inp_j represents an intermediate input value;
&& operator represents a conditional AND operator;
k represents the PRF key;
inp[ ] represents a particular element of the received array;
% operator represents a modulo operator;
* operator represents a multiplication operator;
== operator represents a equality inquiry operator;
>= operator represents a greater than or equal to operator; and
PRF (k, inp_j) represents a pseudo-random function that receives
as input the PRF key and the intermediate input value.

### Claim 7 (depends on 5)

The method of claim 5, wherein:
the modulo element the array size; and
the shifted parameter is equal to a product of the initial-arbitrary location of the first non-null element, a number of available cache lines, and a number of objects that fit into one of the number of available cache lines.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
relocating the non-null elements of the received array from the initial-arbitrary locations to first locations in the received array; and
sorting, using a cache agnostic memory oblivious sort, the non-null elements based on application of the PRF to the PRF key and the non-null elements.

### Claim 9 (depends on 1)

The method of claim 1, wherein:
the received array includes a hash table in a trusted execution environment; and
the output array includes the hash table with the shuffled locations.

### Claim 10 (depends on 9)

The method of claim 9, wherein the trusted execution environment includes software guard extensions (SGX).

### Claim 11

A non-transitory computer-readable medium having encoded therein programming code executable by one or more processors to perform or control performance of operations comprising:
receiving an array having an array size and two or more non-null elements located in initial-arbitrary locations in the array;
receiving a pseudo-random function (PRF) key;
initializing an output array to null;
shuffling at least a portion of the non-null elements to generate shuffled locations for the non-null elements, the shuffling of a first non-null element of the non-null elements including:
determining an intermediate shuffled location for the first non-null element as an application a PRF to the PRF key and the first non-null element modulo a modulo element;
responsive to a location in the output array corresponding to the intermediate shuffled location being null, outputting a shuffled location in the output array for the first non-null element as the intermediate shuffled location;
response to the location in the output array corresponding to the intermediate shuffled location not being null, generating an updated intermediate shuffled location to a sum of the intermediate shuffled location and one modulo the array size; and
responsive to a location in the output array corresponding to the updated intermediate shuffled location being null, outputting the shuffled location in the output array for the first non-null element as the updated intermediate shuffled location; and
returning the output array having the first non-null element in the location in the output array that corresponds to the shuffled location.

### Claim 12 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the operations further comprise:
determining whether a number of the non-null elements are above a particular threshold;
in response to the number of the non-null elements being above the particular threshold:
choosing a random PRF key; and
sorting, using a memory-oblivious sort, the non-null elements based on application of the PRF to the random PRF key and the non-null elements.

### Claim 13 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein the determining the intermediate shuffled location for the first non-null element further includes a difference between the application the PRF to the PRF key and the first non-null element modulo the modulo element and a shifted parameter.

### Claim 14 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the sorting includes sorting according to an odd-even merge sort.

### Claim 15 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the operations further comprise:
dividing the output array into multiple buckets, each of the multiple buckets having a bucket size that is less than a cache size of a trusted execution environment that stores the output array;
relocating the non-null elements of the received array from the initial-arbitrary locations to first locations in the received array;
filling a first bucket of the multiple buckets with a first subset of the non-null elements, the first subset including the non-null elements having a first aggregate size that is less than the bucket size; and
filling a second bucket of the multiple buckets with a second subset of the non-null elements, the second subset including the non-null elements having a second aggregate size that is less than the bucket size,
wherein the shuffling the at least a portion of the non-null elements includes shuffling the first subset in the first bucket independently of the second subset in the second bucket.

### Claim 16 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein:
the filling of the first bucket is performed using a Boolean overflow expression; and
the filling of the first bucket is performed according to the expressions:
For i in range (n/(m*s))
count = 0;
For j in range (t)
overflow = overflow [j]
out_msi = out [m*s*i]
inp_j = inp [j]
opt_pos = PRF (k, inp_j) % n
if (count < m*s):
out [m*s*i + count] = inp_j
if (overflow == true)
count = count + 1
else
if (opt_pos >= m*s*i && opt_pos < m*s*(i+1))
count = count + 1
overflow[j] = false
else
out [m*s*i] = out_mki
if (opt_pos >=m*s*i && opt_pos < m*s*(i+1))
overflow[j] = true
else
overflow [j] = overflow, in which:
i represents an indexing variable that represents the bucket;
n represents the array size;
m represents a number of available cache lines;
s represents a number of objects that fit into one of the number of
available cache lines;
count represents a counting index variable;
j represents an indexing variable;
out[ ] represents an element in the output array;
out_pos represents an intermediate output value;
out_msi represents another intermediate output value;
inp_j represents an intermediate input value;
&& operator represents a conditional AND operator;
k represents the PRF key;
inp[ ] represents a particular element of the received array;
% operator represents a modulo operator;
* operator represents a multiplication operator;
== operator represents a equality inquiry operator;
>= operator represents a greater than or equal to operator; and
PRF (k, inp_j) represents a pseudo-random function that receives as
input the PRF key and the intermediate input value.

### Claim 17 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein:
the modulo element the array size; and
the shifted parameter is equal to a product of the initial-arbitrary location of the first non-null element, a number of available cache lines, and a number of objects that fit into one of the number of available cache lines.

### Claim 18 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the operations further comprise:
relocating the non-null elements of the received array from the initial-arbitrary locations to first locations in the received array; and
sorting, using a cache agnostic memory oblivious sort, the non-null elements based on application of the PRF to the PRF key and the non-null elements.

### Claim 19 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein:
the received array includes a hash table in a trusted execution environment; and
the output array includes the hash table with the shuffled locations.

### Claim 20 (depends on 19)

The non-transitory computer-readable medium of claim 19, wherein the trusted execution environment includes software guard extensions (SGX).
