La computación segura de la estructura del grafo es un elemento importante en el campo de cálculo seguro de grafos, que es importante en la consulta de datos en grafos, ya que no hay algoritmos para el problema de distancia de edición de grafos que puedan resistir ataques de adversarios maliciosos. En este documento, para el problema de computación segura de la distancia de edición de similitud de grafos, en primer lugar, se propone el método de codificación aplicable al algoritmo de cifrado Paillier, y se propone el esquema de operación XOR de acuerdo con el algoritmo de cifrado homomórfico de Paillier. Luego, se diseña el algoritmo de seguridad bajo el modelo semi-honesto, que adopta el nuevo método de codificación y el esquema de operación XOR. Finalmente, para los comportamientos maliciosos que pueden ser implementados por participantes maliciosos en el algoritmo semi-honesto, utilizando la función hash, se diseña un algoritmo para la computación segura de la distancia de edición de grafos bajo el modelo malicioso, y se prueba la seguridad del algoritmo, y se analiza la complejidad computacional y la complejidad de la comunicación del algoritmo, que es más eficiente en comparación con los esquemas existentes, y tiene valor práctico. El algoritmo diseñado en este documento llena la brecha de investigación en la literatura existente sobre el problema de distancia de edición de grafos y contribuye a resolver el problema.