Advantage (cryptography)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In cryptography, an adversary's advantage is a measure of how successfully it can attack a cryptographic algorithm, by distinguishing it from an idealized version of that type of algorithm. Note that in this context, the "adversary" is itself an algorithm and not a person. A cryptographic algorithm is considered secure if no adversary has a non-negligible advantage, subject to specified bounds on the adversary's computational resources (see concrete security). "Negligible" usually means "within O(2 −p )" where p is a security parameter associated with the algorithm. For example, p might be the number of bits in a block cipher's key.

In cryptography, an adversary's advantage is a measure of how successfully it can attack a cryptographic algorithm, by distinguishing it from an idealized version of that type of algorithm. Note that in this context, the "adversary" is itself an algorithm and not a person. A cryptographic algorithm is considered secure if no adversary has a non-negligible advantage, subject to specified bounds on the adversary's computational resources (see concrete security). "Negligible" usually means "within O(2 −p )" where p is a security parameter associated with the algorithm. For example, p might be the number of bits in a block cipher's key. Adv(A) = |\Pr[A(F)=1] - \Pr[A(G)=1]|

Example 1: Guess at random

Call this adversary A 0 . It simply flips a coin and returns 1 or 0 with equal probability and without making any oracle calls. Thus, Pr[A 0 (F)=1] and Pr[A 0 (G)=1] are both 0.5. The difference between these probabilities is zero, so Adv(A 0 ) is zero. The same thing applies if we always return 0, or always return 1: the probability is the same for both F and G, so the advantage is zero. This adversary can't tell F and G apart. If we're cipher designers, our desire (maybe not achievable) is to make it so that it's computationally infeasible for any adversary to do significantly better than this. We will have succeeded if we can make a cipher for which there's no distinguisher faster than brute force search.

Example 2: Brute force search

This adversary (call it A 1 ) will attempt to cryptanalyze its input by brute force. It has its own DES implementation. It gives a single query to its oracle, asking for the 64-bit string of all zeroes to be encrypted. Call the resulting ciphertext E 0 . It then runs an exhaustive key search. The algorithm looks like this: E 0 = oracle_query(0) for k in 0,1,...,2 56 -1: if DES k (0) == E 0 : return 1 return 0 This searches the entire 56-bit DES keyspace and returns "1" if it probably finds a matching key. In practice, several plaintexts are required to confirm the key, as two different keys can result in one or more matching plaintext-ciphertext pairs. If no key is found, it returns 0. If the input oracle is DES, this exhaustive search is certain to find the key, so Pr[A 1 (F)=1] = 1. If the input oracle is a random permutation, there are 2 64 possible values of E 0 , and at most 2 56 of them will get examined in the DES keysearch. So the probability of A 1 returning 1 is at most 2 −8 . That is: Pr[A_1(G)=1] \leq 2^{-8} , so Adv(A_1) = |Pr[A_1(F)=1] - Pr[A_1(G)=1]| \geq 1 - 2^{-8} so the advantage is at least about 0.996. This is a near-certain distinguisher, but it's not a security failure because it's no faster than brute force search, after all, it is the brute force search.

See also

Pseudorandom-function advantage Key-recovery advantage PR-CPA advantage

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371117505 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001371117505 · captured 1787587390.0 · version history

Cite this page as: encyclopegia.org, “Advantage (cryptography)”, snapshot enwiki-001371117505. https://encyclopegia.org/a/advantage-cryptography

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.