Las búsquedas de cadenas aproximadas se han aplicado ampliamente en muchos campos, como la bioinformática, la recuperación de textos, los motores de búsqueda y los servicios basados en la ubicación (LBS). Sin embargo, los resultados de búsqueda de cadenas aproximadas de servidores de terceros pueden ser incorrectos debido a la posibilidad de terceros malintencionados o servidores comprometidos. En este documento, diseñamos una estructura de índice autenticada (AIS) para bases de datos de cadenas, que se basa en el método del árbol de hash de Merkle (MHT) y el índice invertido de -gramos. Nuestro AIS puede facilitar la construcción de objetos de verificación para búsquedas de cadenas aproximadas con umbrales de distancia de edición. Diseñamos un algoritmo eficiente llamado para la construcción en el lado del servidor y la verificación de resultados de búsqueda en el lado del usuario. También presentamos un método de optimización llamado - que puede reducir el tamaño drásticamente. Finalmente, realizamos experimentos extensos en conjuntos de datos reales para demostrar que nuestros métodos propuestos son eficientes y prometedores.