Seguridad conexion base de datos por internet :P HEEEELP ^_^

Hola

Estamos desarrollando una aplicación Cliente-Servidor para unos 20
ordenadores que se conectaran a través de Internet, ya tenemos hecha la
parte de introducción de datos y la de búsqueda, y tenia pensado para
incrementar la seguridad cifrar los datos en la base de datos con algún
tipo de algoritmo simétrico, pero claro ahora he pensado que si los
datos están cifrados cuando haga la consulta a la base de datos si tengo
cifrada la cadena es posible que nunca encuentre resultados, sobre todo
si hago una búsqueda por un cachito de cadena (select * from personal
where nombre like ‘?pp’).

Me podéis aconsejar cual seria la mejor manera para incrementar la
seguridad en el programa.

Muchas gracias

Utilizo SQL Server 2000,Windows 2000 Server y Visual C#

Un Saludo
David