Informacion encriptada

Me presento ante un problema que mas tecnico digamos que es de procedimiento y quería saber algunas ideas de ustedes o si se han enfrentado algo asi.
Estoy desarrollando una aplicación para el gobierno y por lo delicado de la información, incluso estará en la nube y después de estos lios de Snowden, el primer requisito ha sido que la información, ya que es muy sensible, necesita estar encriptada y ya sabemos a donde va esto.
Pense en ecriptar mediante claves publicas/privadas y mantener yo la clave publica mientras la privada cada persona deberia tenerla . Pense en una forma como la solucion de Mega, si pierdes tu clave pierdes la información porque yo no sabre como desencriptar esa información claro que esto es bien drástico y me pone a pensar. Otro asunto es como esa persona cambia la información que ya fue encriptada con su antigua clave para usar la nueva clave.
Lo que me preocupa es la velocidad de busqueda de esta información encriptada si tengo primero que desencriptar o hacer la busqueda de igual forma, claro no sera toda la BD que estara encriptada sino varios campos como textos pero habra mucha información sin encriptar como fechas, ID, códigos, atributos de relaciones,etc.
Esto es algo critico en este proyecto y por eso es la preocupacion, escucho sus opiniones.
Edwin Quijada