fts encrypted
1.0.0
Nota: Token se refiere a token léxico , no de token criptográfico . Por ejemplo, un tokenizer puede convertir 'aprende', 'aprendizaje', 'aprendió' todo en el token 'aprender'.
Si no necesita cifrado, Tantivy es mejor en todos los sentidos.
Una demostración básica de GUI usando Dioxus y el conjunto de correo electrónico de Enron está disponible en mi GitHub aquí. Es principalmente mostrar que la velocidad de búsqueda es decente para el tipo de conjuntos de datos vistos almacenados en aplicaciones del lado del cliente.
Esto sigue siendo un trabajo en progreso. No se están haciendo garantías sobre esta biblioteca o sus dependencias, en implementación, conceptualmente o de otro tipo. Nunca se han realizado auditorías de seguridad. Use bajo su propio riesgo.
Cada palabra clave en una búsqueda o índice está tokenizado. Este token y el nombre de la tabla en el que ocurre, se hashan con Blake2B-128 y luego se cifran con AES-128-ECB antes de ser almacenado o usado para consultas.
Encrypt(Hash(token + table_name))
El modo ECB se usa para el cifrado. El BCE hace que el texto sin formato idéntico se vuelva idéntico, pero esto no es una preocupación para valores únicos como el hash de un token y el nombre de la tabla. Esto significa que el mismo token tendrá un texto cifrado diferente si ocurre en tablas separadas.
Una ID de documento está encriptada con AES-128-ECB. Esto se asocia con un mostrador de 32 bits.
Dado que una ID de documento aparece muchas veces y el número de ID de documento es mucho menor de lo que puede enumerarse con 128 bits, las ID de documento pueden comprimirse.
Suponiendo que 1,000 tokens / documento únicos, el costo para almacenar los acontecimientos de un token en los documentos son:
| Documentos | No optimizado | 32 bits |
|---|---|---|
| 1000 | 16 MB | 4MB |
| 10k | 160 MB | 40 MB |
| 50k | 800MB | 200MB |
| 100k | 1.6GB | 400MB |
| 250k | 4GB | 1GB |
| millón | 16 GB | 4GB |
| mil millones | 16TB | 4tb |
La diferencia está representando los valores en una secuencia como la diferencia entre ellos. Esto crea valores que se pueden representar con menos bits, lo que permite un empalme más estricto.
La caja de bit ses se usa para diferenciar y bit -spacking bloques de 128 enteros.
La diferenciación funciona mejor cuando se clasifican los valores, pero mantener los valores ordenados y de bit-bits requeriría volver a codificar todos los valores cuando se agrega una entrada fuera de servicio. El uso de un enfoque amortizado con una colección de valores fuera de pedido puede reducir el costo de los cambios amortizándolos.
| Número de capa | Esquema de embalaje | Clasificación | Diferente |
|---|---|---|---|
| 0 | Ninguno - 32 bits (<128 ints) | Ninguno | No |
| 1+ | Bitpacker4x (128 ints) | Globalmente capas de Amoung por encima de 0 | Sí |
Se comprimieron aproximadamente 9,000-10,000 correos electrónicos de Enron más cortos y el tamaño FTS DB resultante fue de 235 MB utilizando una codificación de 32 bits. El uso de la diferenciación amortizada y el bitpacking en capas cambió eso a 21 MB.
Eliminar un archivo es ... costoso ... amortización TODO
Explorar. Algo como RockSDB Memtable o Sled. Almacene los cambios en la memoria, luego se descarte cada 500 ms o cuando se alcanza el límite de memoria.
¿Las palabras de clasificación de bucket por los primeros 3 o 4 caracteres (no tokenizados), compresas? y encrypt. Bloquear en cifrado con algo con difusión como CBC o GCM (cifrado autenicado). Esto significaría que el autocompleto comenzaría después de 3 o 4 caracteres. Esto todavía está en la etapa conceptual.
La integridad de los datos es opcional al hashing el archivo de la base de datos a tiempo cercano y almacenar una versión cifrada del hash.
No hay difusión en las ID de documento cifradas. Agregar difusión requeriría encriptar ID de documento utilizando un IV generado aleatoriamente. Esto también haría que la compresión sea imposible. El almacenamiento del IV agregaría 128 bits por token y par de documentos (para AES CBC).
Lo siguiente es visible para un atacante sin una clave:
En el caso de un índice en una lista de pacientes en el consultorio de un médico, un atacante sin clave podría ver el número de pacientes y una distribución de tokens utilizados dentro de los documentos. No podían ver ningún texto sin formato, como nombres u otros identificadores, y ni siquiera podían ver la identificación del documento de ningún paciente. Podrían ver si dos pacientes comparten un token de búsqueda, pero nada sobre quién es los pacientes o cuál es la información compartida.
Por ejemplo, si el índice de búsqueda solo se basó en nombres en un país con apellidos comunes, como Vietnam, podría hacer un análisis de frecuencia y descubrir el número probable de pacientes con el apellido Nguyen (38% de la población de Vietnam). Esto se basa en su anterior (distribución de apellidos) que es válido para el conjunto de datos en cuestión. También solo sería efectivo contra nombres comunes, que no se identifica y sería poco probable que distinga con confianza documentos que contengan incluso el segundo del tercer apellido más común en Vietnam (Tran al 11% y LE al 10%).
Una vez más, se agrega información al índice de búsqueda, como la edad, la ciudad natal, la dirección, la descripción, etc., la capacidad de realizar análisis de frecuencia prácticamente desaparece.
Una preocupación puede ser el no repudio de almacenar conjuntos de datos únicos, donde un análisis de frecuencia de un gran conjunto de datos de texto sin formato conocido podría usarse para mostrar que más allá de una duda razonable, un dispositivo determinado tenía ese conjunto de datos indexado. Aparentemente, esto solo afectaría a los disidentes en países o delincuentes autoritarios. Esto se puede mitigar mediante cifrado de disco completo cuando el dispositivo está apagado.
Sea d1 un documento con un token t1 . Deje que t2 sea un token cuyo hash choca con t1 y no es una ficha del documento d1 .
Los falsos positivos, donde se incluyeron resultados adicionales no relacionados en un resultado de la búsqueda, pueden ocurrir a d1 si la búsqueda contiene t2 y no t1 .
Los falsos negativos, donde se omitieron los resultados relevantes de un resultado de la búsqueda, solo pueden ocurrir si se eliminó uno de los tokens colisionar para un documento. Esto resultaría en que la otra ficha se "elimine" también.
Los falsos positivos o negativos solo se aplican a los documentos que tienen uno de los tokens colisionados, cuando el otro token colisional está presente en la consulta de búsqueda. Esto hace que las apuestas de tal colisión sean muy bajas.
El riesgo real de una colisión es cómicamente pequeño para hashes de 128 bits (ver problema de cumpleaños en Wikipedia).
El cifrado de 64 bits solo da como resultado algunos megabytes de ahorro de espacio para índices muy grandes. El inglés tiene alrededor de 1,000,000 de palabras y menos fichas. 64 millones de bits son solo 8 MB. Dadas las distribuciones de tipo de ley de potencia observadas en los idiomas, donde las más o menos cientos de palabras pueden comprender la mitad de la frecuencia, los ahorros reales serían considerablemente menores.
