Sidik jari merupakan salah satu biometrik yang digunakan secara luas untuk otentikasi pengguna. Karakteristik sidik jari adalah permanen dan melekat kepada pengguna sehingga data sidik jari tidak boleh diketahui oleh orang lain. Salah satu metode pengamanan data sidik jari yaitu dengan melakukan transformasi pada fitur sidik jari, transformasi menghasilkan data lain yang tidak dapat dikembalikan ke bentuk asal, kemudian data dikirimkan ke server untuk dicocokkan dengan basis data. Transfer data menimbulkan celah keamanan bocornya data hasil transformasi sehingga dimungkinkan dapat dianalisa dan disusun kembali menjadi data fitur sidik jari. Pada penelitian ini diusulkan sebuah protokol untuk mengamankan pengiriman data hasil transformasi sidik jari dengan menggunakan pewarnaan graf pada proses enkripsi dan dekripsi. Protokol ini diawali dengan pertukaran bilangan kunci antara server dengan client, bilangan kunci yang disepakati digunakan untuk mengacak IV, selanjutnya proses enkripsi dan deskripsi menggunakan graf yang telah diwarnai dengan IV teracak. Dari hasil analisis dan percobaan yang dilakukan, protokol yang diusulkan mampu mencapai kecepatan enkripsi 0.0160 milidetik dan dekripsi 0.0264 milidetik untuk data sebesar 512 byte dengan peluang maksimum data dapat dipecahkan sebesar 3.719933267899012 x 10^41