Concrete security

Concrete security

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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Concrete, Washington —   Town   Welcome sign chainsaw carved from cedar logs greets visitors to Concrete, Washington …   Wikipedia

  • Security level management — (SLM) comprises a quality assurance system for electronic information security. The aim of SLM is to display the IT security status transparently across a company at any time, and to make IT security a measurable quantity. Transparency and… …   Wikipedia

  • Security Assertion Markup Language — (SAML) is an XML based standard for exchanging authentication and authorization data between security domains, that is, between an identity provider (a producer of assertions) and a service provider (a consumer of assertions). SAML is a product… …   Wikipedia

  • Provable security — In cryptography, a system has provable security if its security requirements can be stated formally in an adversarial model, as opposed to heuristically, with clear assumptions that the adversary has access to the system as well as enough… …   Wikipedia

  • National security — Security measures taken to protect the Houses of Parliament in London, UK. These heavy blocks of concrete are designed to prevent a car bomb or other device being rammed into the building. National security is the requirement to maintain the… …   Wikipedia

  • Computer security policy — A computer security policy defines the goals and elements of an organization s computer systems. The definition can be highly formal or informal. Security policies are enforced by organizational policies or security mechanisms. A technical… …   Wikipedia

  • Precast concrete — is a form of construction, where concrete is cast in a reusable mold or form which is then cured in a controlled environment, transported to the construction site and lifted into place. In contrast, standard concrete is poured into site specific… …   Wikipedia

  • Human security — is an emerging paradigm for understanding global vulnerabilities whose proponents challenge the traditional notion of national security by arguing that the proper referent for security should be the individual rather than the state. Human… …   Wikipedia

  • Common Security and Defence Policy — European Union This article is part of the series: Politics and government of the European Union …   Wikipedia

  • Common Foreign and Security Policy — This article deals with the workings of European Union foreign policy. For the relations between the European Union and third countries, see Foreign relations of the European Union. European Union This a …   Wikipedia