Si el dispositivo del usuario es root da igual donde guardes la información porque el usuario podrá acceder a los ficheros de base de datos o los de Shared preferences o cualquier archivos que se almacene en el carpetas de la App.
La encriptación es fundamental para el cometido que quieres hacer para mantener la privacidad de las conversaciones. Yo te recomendaría utilizar la Base de Datos para el almacenamiento de las conversaciones, ya que te resultará más fácil acceder a la información que desees y puede almacenar un gran volumen de datos.
WhattsApp por ejemplo sino me equivoco utiliza Base de datos, de la cual va haciendo copias de seguridad todos los días y estas copias están encriptadas. Si entras con un gestor de archivos podrás ver dentro de la carpeta Whatsapp una carpeta llamada Databases en la que podrás ver la BD con el nombre msgstore.db.crypt12 y las copias de seguridad con nombre msgstore-año-mes-dia.1.db.crypt12. Telegram y Facebook Messenger no he investigado como gestionan esto.
Espero que te sirva de ayuda.