Let’s talk about Oblivious Computation

A high-level introduction to oblivious sorting

As originally defined in 1990 by Ostrovsky and then elaborated on in 1996, a machine is oblivious if the sequence in which it accesses memory locations is equivalent for any two programs with the same running time. To rephrase this, it effectively means that the memory accesses and the runtime of a program are independent of the actual input. Think of a program that reads an array like [13, 11, 42, 99, 23] as input and returns its sorted version (i.e., [11, 13, 23, 42, 99]). Obliviousness requires that the memory accesses and the runtime for sorting an array should not depend on the input (even if it’s already sorted!).

How big of a problem do you think not having your algorithm be oblivious could be?

Hold that thought — Side-channel attacks, memory access patterns, can leak significant amounts of data! A prominent example is the* “square and multiply for RSA”*, where modular exponentiations were vulnerable to timing attacks because attackers could measure the time it takes to compute the result and use this information to leak secret keys. You have probably heard about more recent examples like Meltdown, Spectre, Foreshadow, etc.

Let’s go back to our sorting example. In computer science, sorting algorithms are a widely studied topic, and their efficiency varies based on serial, parallel, or distributed processing capabilities as well as whether or not the inputs are pre-sorted, whether the data fits the main memory or not, and much more. Below is a simple demonstration of this: sorting a sorted array is so much faster than sorting a random array:

import time
import random

N = 10**7

print(f"Creating array of {N} elements...")
arr = [random.randint(0, 10**6) for _ in range(N)]

print("Sorting the random array...")
start = time.time()
sorted_arr = sorted(arr)
print(f"Sorting random array took: {time.time() - start:.6f} seconds")

print("Sorting the already sorted array...")
start = time.time()
sorted_again = sorted(sorted_arr)
print(f"Sorting sorted array took: {time.time() - start:.6f} seconds")

Which outputs:

Creating array of 10000000 elements...
Sorting the random array...
Sorting random array took: 1.887453 seconds
Sorting the already sorted array...
Sorting sorted array took: 0.559535 seconds

Oh, this is a side channel! Just by observing the time it takes to respond, an attacker can deduce how sorted or not the input array was! See the visualization below on how quicksort works in practice. If an array is almost sorted, then it only has to do a few operations to end up with a fully sorted array, while if the input array is completely random, quicksort has to do more work.

Quicksort visualized (source Wikipedia)

Interestingly, there exist sorting algorithms like the Bitonic sort that ensure that all comparisons between elements are performed in a pre-determined order. This means that Bitonic sort is already independent of the actual input values, making it oblivious! The lack of conditions and runtime decisions makes it ideal for hardware implementations, such as in GPUs. Back to our topic, let’s see how Bitonic sort (on CPU) compares with the built-in Python sort. (See the Appendix for a simple implementation of Bitonic sort.)

N = 2**20 # ~ 1M
print(f"Creating array of {N} elements...")
arr = [random.randint(0, 10**6) for _ in range(N)]

print("Sorting the random array with Bitonic sort...")
start = time.time()
sorted_arr = bitonic_sorted(arr)
print(f"Bitonic sort on random array took: {time.time() - start:.6f} seconds")

print("Sorting the already sorted array with Bitonic sort again...")
start = time.time()
sorted_again = bitonic_sorted(sorted_arr)
print(f"Bitonic sort on sorted array took: {time.time() - start:.6f} seconds")

Which outputs:

Creating array of 1048576 elements...
Sorting the random array with Bitonic sort...
Bitonic sort on random array took: 14.490458 seconds
Sorting the already sorted array with Bitonic sort again...
Bitonic sort on sorted array took: 14.626223 seconds

Yikes. For almost 9–10x less data, it takes more than 7 times the runtime for the unsorted array, and more than 25 times that of the sorted array. Hey, at least we solved the side channel :) Observe below the visualization of a Bitonic sorting network for 16 inputs. Regardless of how sorted or not the inputs are, Bitonic will always perform the exact same comparisons.

Bitonic sort visualized (source Wikipedia)

Well, with oblivious algorithms, most of the optimizations we saw in quicksort do not apply! Oblivious RAM (ORAM) hides how data is accessed, which is crucial for protecting sensitive information. But… what is the slowdown in the running time of any machine, if it is required to be oblivious? This is what we will dive into in the next posts!

Appendix

import time
import random

def bitonic_sorted(arr, up=True):
    def compare_and_swap(a, i, j, up):
        if (a[i] > a[j]) == up:
            a[i], a[j] = a[j], a[i]

    def bitonic_merge(a, low, cnt, up):
        if cnt > 1:
            k = cnt // 2
            for i in range(low, low + k):
                compare_and_swap(a, i, i + k, up)
            bitonic_merge(a, low, k, up)
            bitonic_merge(a, low + k, k, up)

    def bitonic_sort_rec(a, low, cnt, up):
        if cnt > 1:
            k = cnt // 2
            bitonic_sort_rec(a, low, k, True)
            bitonic_sort_rec(a, low + k, k, False)
            bitonic_merge(a, low, cnt, up)

    n = len(arr)
    pow2 = 1 << (n - 1).bit_length()
    # pad with max so sort result is unaffected
    padded = arr + [max(arr)] * (pow2 - n)
    result = padded[:]
    bitonic_sort_rec(result, 0, pow2, up)
    return result[:n]  # remove padding

• An X thread on oblivious computation with memes: https://x.com/jimouris/status/1943705223283036473