İhmal edilebilir fonksiyon
Kriptografinin “önemsenmeyecek kadar küçük” demenin biçimsel yolu: eninde sonunda her polinomun tersinden küçük olmak.
Bir μ(n) fonksiyonu, her p polinomu için eninde sonunda 1/p(n)’nin altına düşüyorsa ihmal edilebilirdir. 2−n ihmal edilebilirdir; 1/n100 değildir. Bu kavram, Goldwasser ile Micali’nin 1980’lerin başında kurduğu asimptotik ekolün temelini oluşturur. Verimli her saldırganın avantajı güvenlik parametresine göre ihmal edilebilirse şema güvenlidir; hem anlamsal güvenlik hem de IND-CPA bu şekilde tanımlanır.
Zayıflığı şu: “eninde sonunda” ne zaman olduğunu hiç söylemez. Bir şema kanıtlanabilir biçimde güvenli olup 128 bitte yine de kırılabilir. Bu yüzden çalışma kipleri için pratik kanıtlar artık somut güvenliği kullanır: avantaj, sorgu sayısı ve blok boyutuna bağlı açık bir formül olarak yazılır.