cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, 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. It quantifies the security of a cryptosystem by bounding the

probability Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...

of success for an adversary running for a fixed amount of time. Security proofs with precise analyses are referred to as ''concrete''. Traditionally,

provable security Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields. Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...

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 In information theory, the computationally bounded adversary problem is a different way of looking at the problem of sending data over a noisy channel. In previous models the best that could be done was ensuring correct decoding for up to ''d''/2 e ...

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 In cryptography, a security parameter is a way of measuring of how "hard" it is for an adversary to break a cryptographic scheme. There are two main types of security parameter: ''computational'' and ''statistical'', often denoted by \kappa and \ ...

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

Examples

Concrete security estimates have been applied to cryptographic algorithms: * In 1996, schemes for

digital signatures A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...

based on the RSA and

Rabin Rabin is a List of Jewish surnames, Hebrew surname. It originates from the Hebrew word ''rav'' meaning Rabbi, or from the name of the specific Rabbi Abin I, Abin. The most well known bearer of the name was Yitzhak Rabin, prime minister of Israel ...

cryptosystems were proposed, which were shown to be approximately as difficult to break as the original cryptosystems. * In 1997, some notions of concrete security (''left-or-right indistinguishability'', ''real-or-random indistinguishability'', ''find-then-guess security'', and ''semantic-security'') for symmetric encryption algorithms were proved approximately equivalent in various

block cipher modes of operation In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transform ...

such as CBC, CTR, and XOR (a stateless variant of CBC). * In 2017, a thesis showed that lattice point enumeration and lattice block reduction algorithms could be used to attack

lattice-based cryptography Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for pos ...

. * In 2021, "guess-and-determine" and "guess-and-decode"-type attacks were demonstrated against a proposed

pseudorandom generator In theoretical computer science and cryptography, a pseudorandom generator (PRG) for a class of statistical tests is a deterministic procedure that maps a random seed to a longer pseudorandom string such that no statistical test in the class ...

in NC0, where instances with parameter values previously claimed to have 128-bit security were solved in about

2^

operations. In addition, a software tool named the "Foundational Cryptography Framework", which embeds into

Coq Coq is an interactive theorem prover first released in 1989. It allows for expressing mathematical assertions, mechanically checks proofs of these assertions, helps find formal proofs, and extracts a certified program from the constructive proof ...

, is able to formally verify proofs of concrete security. For example, it is able to verify the concrete security of

ElGamal encryption In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in t ...

References

Theory of cryptography

External links

*https://www.cs.purdue.edu/homes/jblocki/courses/555_Fall18/slides/Week2.pdf *https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf
https://eprint.iacr.org/2006/278.pdf
*https://www.baigneres.net/downloads/2007_provable_security.pdf *https://eprint.iacr.org/2020/1213.pdf {{crypto-stub