Ö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.

Hash functions are one of the most important cryptographic primitives. They map an input of arbitrary finite length to a value of fixed length by compressing the input, that is why, they are called hash. They must run efficiently and satisfy some cryptographic security arguments. They are mostly used for data integrity and authentication such as digital signatures.Some hash functions such as SHA family (SHA1-SHA2) and MD family (MD2-MD4-MD5) are standardized to be used in cryptographic schemes. A common property about their construction is that they are all iterative. This property may cause an efficiency problem on big size data, because they have to run on the entire input even it is slightly changed. So the question is `Is it possible to reduce the computational costs of hash functions when small modifications are done on data?`In 1995, Bellare, Goldreich and Goldwasser proposed a new concept called incrementality: a function f is said to be incremental if f(x) can be updated in time proportional to the amount of modification on the input x. It brings out two main advantages on efficiency: incrementality and parallelizability. Moreover, it gives a provable security depending on hard problems such as discrete logarithm problem (DLP). The hash functions using incrementality are called Incremental Hash Functions. Moreover, in 2008, Dan Brown proposed an incremental hash function called ECOH by using elliptic curves, where DLP is especially harder on elliptic curves, and which are therefore quite popular mathematical objects in cryptography.We state incremental hash functions with some examples, especially ECOH, and give their security proofs depending on hard problems.

95