Incremental hash functions

Özet Fonksiyonları daha çok veri bütünlüğünde ve elektronik imza gibi kimlik doğrulamada kullanılan kriptolojinin en önemli araçlardan biridir. Bu fonksiyonlar, herhangi bir uzunluktaki girdiyi belli özelliklerle sıkıştırarak sabit bir uzunluktaki çıktıya götürler. Bu fonksiyonlar ayrıca hızlı hesaplanabilir olmalı ve bazı kriptografik güvenlik gereksinimlerini sağlamalıdırlar. SHA ve MD gibi özet fonksiyonları aileleri, kriptolojik uygulamalarda kullanılmak üzere standartlaştırılmış özet fonksiyonlarıdır. Bunların en önemli yapısal özelliği yinelemeli (iterative) olmalarıdır. Bu özellik büyük boyutlu verilerde verimlilik problemine neden olur, çünkü girdide ufak bir değişiklik olsa bile özet fonksiyonu bütün girdi üzerinde tekrar çalışmalıdır. Bu yüzden sormamız gereken soru "Veri üzerindeki ufak bir değişiklik olduğunda özet fonksiyonun hesaplama maliyetini düşürmek mümkün müdür?" olacaktır. 1995 yılında Bellare, Goldriech ve Goldwasser tarafından artımlılık isimli yeni bir konsept sunulmuştur: eğer x girdisi üzerinde yapılan küçük bir değişiklik sonucu f(x) değeri değişiklikle doğru orantılı olacak bir zamanda güncellenebiliyorsa f fonksiyonuna artımlı denir. Bu konsept verimlilik açısından çok önemli iki tane avantaj saglamıstır: artımlılık ve paralellestirilebilirlik. Ayrıca ayrık logaritma problemi gibi çözülmesi zor olan problemlere dayalı bir güvenlik sağlamıştır. Bu özelliği kullanan özet fonksiyonlarına Artımlı Özet Fonksiyonları diyoruz. Ayrıca, Dan Brown 2008 yılında artımlı özet fonksiyonlarına örnek olacak Elliptik Eğrilerde Özet Fonksiyonu (ECOH) adlı özet fonksiyonunu önermiştir. Bu tezde, artımlı özet fonksiyonları örnekleriyle (özellikle de ECOH örneğiyle) birlikte incelenmiş ve bunların güvenlik ispatları çözülebilirliği zor problemlerle karşılaştırılırak gösterilmiştir.