In cryptography, concrete security or exact security is a practice-oriented approach that aims to give more precise estimates of the computational complexities of adversarial tasks than polynomial equivalence would allow.
Traditionally, provable security is asymptotic: it classifies the hardness of computational problems using polynomial-time reducibility. Secure schemes are defined to be those in which the advantage of any computationally bounded adversary is negligible. While such a theoretical guarantee is important, in practice one needs to know exactly how efficient a reduction is because of the need to instantiate the security parameter - it is not enough to know that "sufficiently large" security parameters will do. An inefficient reduction results either in the success probability for the adversary or the resource requirement of the scheme being greater than desired.
Concrete security parametrizes all the resources available to the adversary, such as running time and memory, and other resources specific to the system in question, such as the number of plaintexts it can obtain or the number of queries it can make to any oracles available. Then the advantage of the adversary is upper bounded as a function of these resources and of the problem size. It is often possible to give a lower bound (i.e. an adversarial strategy) matching the upper bound, hence the name exact security.
Famous quotes containing the words concrete and/or security:
“A doctor, like anyone else who has to deal with human beings, each of them unique, cannot be a scientist; he is either, like the surgeon, a craftsman, or, like the physician and the psychologist, an artist.... This means that in order to be a good doctor a man must also have a good character, that is to say, whatever weaknesses and foibles he may have, he must love his fellow human beings in the concrete and desire their good before his own.”
—W.H. (Wystan Hugh)
“There is something that Governments care for far more than human life, and that is the security of property, and so it is through property that we shall strike the enemy.... Be militant each in your own way.... I incite this meeting to rebellion.”
—Emmeline Pankhurst (1858–1928)