fts encrypted
1.0.0
NOTA: O token refere -se a token lexical , e não ao token criptográfico . Por exemplo, um tokenizador pode transformar 'aprendiz', 'aprendizado', 'aprendeu' tudo no token 'aprendendo'.
Se você não precisa de criptografia, Tantivy é melhor em todos os aspectos.
Uma demonstração básica da GUI usando Dioxus e o conjunto de email da Enron está disponível no meu github aqui. É principalmente para mostrar que a velocidade de pesquisa é decente para o tipo de conjunto de dados vistos armazenados nos aplicativos do lado do cliente.
Este ainda é um trabalho em andamento. Nenhuma garantia sobre esta biblioteca ou suas dependências, na implementação, conceitualmente ou não, está sendo feita. Nenhuma auditoria de segurança foi realizada. Use por sua conta e risco.
Cada palavra -chave em uma pesquisa ou índice é tokenizada. Este token e o nome da tabela em que ocorre, são hashed com Blake2b-128 e depois criptografados com AES-128-ECB antes de serem armazenados ou usados para consultas.
Encrypt(Hash(token + table_name))
O modo BCE é usado para criptografia. O BCE faz com que o texto simples idêntico se torne idêntico, mas isso não é uma preocupação para valores únicos, como o hash de um nome de token e tabela. Isso significa que o mesmo token terá um texto cifrado diferente se ocorrer em tabelas separadas.
Um ID do documento é criptografado com AES-128-ECB. Isso está então associado a um contador de 32 bits.
Como um ID do documento aparece muitas vezes e o número de IDs de documentos é muito menor do que pode ser enumerado com 128 bits, os IDs do documento podem ser compactados.
Assumindo 1.000 tokens / documentos exclusivos, o custo para armazenar as ocorrências de um token nos documentos são:
| Documentos | Não otimizado | 32 bits |
|---|---|---|
| 1000 | 16 MB | 4 MB |
| 10k | 160 MB | 40 MB |
| 50k | 800 MB | 200 MB |
| 100k | 1,6 GB | 400 MB |
| 250K | 4GB | 1 GB |
| milhão | 16 GB | 4GB |
| bilhão | 16tb | 4tb |
A diferenciação está representando valores em uma sequência como a diferença entre eles. Isso cria valores que podem ser representados com menos bits, o que permite um bitpacking mais apertado.
A caixa Bitpacking é usada para diferenciar e bitpacking blocos de 128 números inteiros.
A diferenciação funciona melhor quando os valores são classificados, mas a manutenção de valores classificados e Bitpacked exigiria re-codificação de todos os valores quando uma entrada fora de ordem for adicionada. O uso de uma abordagem amortizada com uma coleção de valores fora de ordem pode reduzir o custo das alterações, amortizando -as.
| Número da camada | Esquema de embalagem | Classificação | Diffing |
|---|---|---|---|
| 0 | Nenhum - 32 bits (<128 ints) | Nenhum | Não |
| 1+ | Bitpacker4x (128 ints) | Camadas globalmente amoung acima de 0 | Sim |
Aproximadamente 9.000 a 10.000 emails mais curtos da Enron foram compactados e o tamanho de dB de FTS resultante foi de 235 MB usando a codificação de 32 bits. O uso da diferenciação amortizada e do pacote de bits em camadas mudou para 21 MB.
Excluir um arquivo é ... caro ... amortização TODO
TODO explorar. Algo como rocksdb memorável ou trenó. Alterações da loja na memória e lave a cada 500ms ou quando o limite de memória for atingido.
Classificar as palavras dos primeiros 3 ou 4 caracteres (não tokenizados), compactar? e criptografar. Bloco criptografado com algo com difusão como CBC ou GCM (criptografia autenicada). Isso significaria que o preenchimento automático entraria em ação após 3 ou 4 caracteres. Isso ainda está no estágio conceitual.
A integridade dos dados é opcional por hash do arquivo de banco de dados em horário de fechamento e armazenando uma versão criptografada do hash.
Não há difusão nos IDs de documentos criptografados. Adicionar difusão exigiria criptografando IDs de documentos usando um IV gerado aleatoriamente. Isso também tornaria a compactação impossível. O armazenamento do IV adicionaria 128 bits por token e par de documentos (para AES CBC).
A seguir, é visível a um atacante sem uma chave:
No caso de um índice em uma lista de pacientes em um consultório médico, um invasor sem chave pode ver o número de pacientes e uma distribuição de tokens usados nos documentos. Eles não podiam ver nenhum texto simples, como nomes ou outros identificadores, e nem podiam ver o ID do documento de nenhum paciente. Eles podiam ver se dois pacientes compartilham um token de pesquisa, mas nada sobre quem os pacientes ou quais são as informações compartilhadas.
Por exemplo, se o índice de pesquisa foi construído apenas com nomes em um país com sobrenomes comuns, como o Vietnã, você poderá fazer uma análise de frequência e descobrir o número provável de pacientes com o sobrenome Nguyen (38% da população do Vietnã). Isso depende da sua prévia (distribuição de sobrenomes) sendo válida para o conjunto de dados em questão. Também seria eficaz contra nomes comuns, o que não é identificação e é improvável que distinguisse documentos com confiança que contêm até o segundo do terceiro sobrenome mais comum no Vietnã (Tran a 11% e LE a 10%).
Uma vez mais informações são adicionadas ao índice de pesquisa, como idade, cidade natal, endereço, descrição etc., a capacidade de realizar a análise de frequência praticamente desaparece.
Uma preocupação pode não ser a repudiação de armazenar conjuntos de dados exclusivos, onde uma análise de frequência de um grande conjunto de dados de texto simples conhecido pode ser usado para mostrar que, além de uma dúvida razoável, um determinado dispositivo tinha esse conjunto de dados indexado. Aparentemente, isso afetaria apenas os dissidentes em países ou criminosos autoritários. Isso pode ser mitigado pela criptografia completa do disco quando o dispositivo estiver desligado.
Seja d1 um documento com um token t1 . Seja t2 um token cujo hash colide com t1 e não é um token do documento d1 .
Os falsos positivos, onde resultados adicionais não relacionados foram incluídos em um resultado de pesquisa, podem ocorrer no d1 se a pesquisa contiver t2 e não t1 .
Os falsos negativos, quando os resultados relevantes foram omitidos de um resultado de pesquisa, só podem ocorrer se um dos tokens em colisão foi excluído para um documento. Isso resultaria no outro token sendo "excluído" também.
Falsos positivos ou negativos se aplicam apenas a documentos que possuem um dos tokens em colisão, quando o outro token em colisão está presente na consulta de pesquisa. Isso torna as apostas de tal colisão muito baixas.
O risco real de uma colisão é comicamente pequeno para hashes de 128 bits (ver problema de aniversário na Wikipedia).
A criptografia de 64 bits resulta apenas em alguns megabytes de economia de espaço para índices muito grandes. O inglês tem cerca de 1.000.000 de palavras e menos tokens. 64 milhões de bits são de apenas 8 MB. Dadas as distribuições do tipo de lei de energia observadas nos idiomas, onde as centenas melhores podem compreender metade da frequência, a economia real seria consideravelmente menor.
