Circuit ORAM e Desempenho Prático

Circuit ORAM, proposto por Wang, Chan e Shi (2015), foi projetado para minimizar a sobrecarga de largura de banda e, ao mesmo tempo, ser simples de implementar em estruturas de computação segura (circuitos codificados e compartilhamento de segredos). Sua principal inovação é reduzir o tamanho do compartimento para Z = 2 blocos (em comparação com Z = 5 no Path ORAM), reduzindo a largura de banda pela metade e mantendo uma probabilidade de falha desprezível. O procedimento de despejo foi reformulado para poder ser expresso como um pequeno circuito booleano.

No Path ORAM com Z = 5, a probabilidade de transbordamento do buffer temporário é controlada pela existência de vários blocos por compartimento, para acomodar a atribuição aleatória de blocos aos caminhos. Circuit ORAM prova que Z = 2 é suficiente quando se usa um procedimento determinístico de despejo (despejo em profundidade primeiro), em vez de um despejo aleatório. Isso reduz pela metade o armazenamento no servidor e a sobrecarga de comunicação em comparação com o Path ORAM com os mesmos parâmetros de segurança.

Circuit ORAM foi projetado especificamente para ter um procedimento de despejo que possa ser expresso como um circuito booleano eficiente. Em protocolos de computação segura (circuitos codificados, SPDZ), o próprio acesso à ORAM deve ser avaliado de forma obliviosa — o servidor que executa a computação não pode descobrir qual posição de memória está sendo acessada. O circuito simples e determinístico de despejo do Circuit ORAM é muito mais eficiente para ser codificado do que o procedimento de despejo do Path ORAM.

Para um banco de dados com N blocos de tamanho B bytes, Circuit ORAM exige 2 * log N * B bytes por acesso (lendo e gravando um caminho com Z = 2 blocos por compartimento). Para N = 2^20 blocos de 4KB cada, isso corresponde a 160KB por acesso, em comparação com 400KB no Path ORAM (Z=5). A sobrecarga de largura de banda em comparação com o texto claro é de cerca de 40 vezes para parâmetros típicos, abaixo das 100 vezes do Path ORAM.

Oblix (Misra, Schlegel, Sherwood, Tsudik, 2018) usa Circuit ORAM para criar versões obliviosas de estruturas de dados de alto nível: listas encadeadas obliviosas, mapas obliviosos (tabelas de dispersão) e filas de prioridade obliviosas. Essas estruturas permitem computação obliviosa sobre dados dinâmicos sem revelar padrões de acesso. Oblix é executado dentro de enclaves Intel SGX e tem como alvo a interseção privada de conjuntos e consultas privadas a bancos de dados.

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) estende o Path ORAM para oferecer acesso assíncrono de alta vazão, processando várias solicitações ORAM em paralelo e agrupando as remoções de caminhos. Ao combinar acessos ao mesmo caminho, TaoStore alcança uma vazão significativamente maior (solicitações por segundo) do que as construções ORAM síncronas, tornando-o adequado para servidores de armazenamento em nuvem com muitos clientes simultâneos.

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) constrói um sistema completo de armazenamento transacional sobre o Path ORAM. Obladi oferece suporte a transações ACID sobre armazenamento criptografado com ocultação do padrão de acesso. Ele introduz a execução adiada: as transações são agrupadas em épocas e executadas de modo a ocultar quais registros específicos foram acessados em cada época. Obladi funciona como um proxy confiável entre os clientes e o sistema de armazenamento em nuvem não confiável.

Para um ORAM de 1GB (262.144 blocos de 4KB) implantado na AWS, com um cliente acessando blocos pela internet, a latência do Path ORAM é de aproximadamente 50 a 200ms por acesso (dominada pelo tempo de ida e volta dos acessos aos compartimentos, com log N = 18). Com buscas paralelas nos compartimentos, esse valor pode ser reduzido. Para aplicações locais em SGX, com o ORAM na RAM, a latência fica na faixa de 1 a 10ms por acesso, o que é aceitável para muitas aplicações de computação segura.

A sobrecarga de largura de banda do ORAM depende muito dos padrões de acesso. Para um ORAM de armazenamento em nuvem de 1TB, com blocos de 1MB, cada acesso transfere cerca de 25MB (sobrecarga de 25 vezes para log N = 25 níveis). Para blocos pequenos (4KB), a sobrecarga por acesso é menor em bytes absolutos, mas maior em termos relativos. As organizações que implantam ORAM devem reservar largura de banda para uma amplificação de 20 a 50 vezes e garantir que seus enlaces de rede e custos de saída da nuvem levem isso em conta.

Uma alternativa ao ORAM para a privacidade de acesso é o equipamento confiável: Intel SGX ou AMD SEV fornece um ambiente de execução confiável no qual nem mesmo o sistema operacional hospedeiro pode observar a computação ou os padrões de acesso à memória (com as defesas apropriadas). O SGX sem ORAM ainda vaza padrões de acesso no nível de páginas para o equipamento, portanto é necessário usar ORAM dentro do SGX para obter proteção completa. Em comparação com o ORAM puro, o equipamento confiável reduz a sobrecarga de largura de banda, mas exige confiança no fabricante do equipamento e na cadeia de fornecimento.

O ORAM é apropriado quando: o adversário observa os padrões de acesso no lado do servidor (provedor de nuvem, co-inquilino), a sensibilidade dos dados justifica uma sobrecarga de largura de banda de 20 a 50 vezes e o próprio padrão de acesso revelaria informações sensíveis. Para a maioria das aplicações, a criptografia padrão com gerenciamento cuidadoso de chaves é suficiente. O ORAM é uma ferramenta especializada para cenários de alta segurança: análise de dados médicos, aprendizado de máquina privado, sistemas de negociação financeira e bancos de dados de aplicação da lei.

Qual tamanho de compartimento o Circuit ORAM utiliza e por que isso representa uma melhoria em relação ao Path ORAM?

O Circuit ORAM reduz o tamanho do compartimento para Z=2 (em comparação com Z=5 do Path ORAM), reduzindo a largura de banda pela metade por meio de remoções determinísticas que priorizam os níveis mais profundos. Ele foi projetado para ser usado em computação segura com circuitos embaralhados. A sobrecarga prática é uma amplificação de largura de banda de 40 vezes para parâmetros típicos. Os sistemas de produção incluem Oblix (SGX + estruturas de dados com acesso oculto), TaoStore (ORAM de alta vazão com processamento em lotes) e Obladi (ORAM transacional). O ORAM dentro do SGX é necessário porque o SGX sozinho vaza padrões de acesso no nível de páginas.