Editing Message authentication code (section)

==Definitions==
Informally, a message authentication code system consists of three algorithms:
* A key generation algorithm selects a key from the key space uniformly at random.
* A MAC generation algorithm efficiently returns a tag given the key and the message.
* A verifying algorithm efficiently verifies the authenticity of the message given the same key and the tag. That is, return ''accepted'' when the message and tag are not tampered with or forged, and otherwise return ''rejected''.

A secure message authentication code must resist attempts by an adversary to [[digital signature forgery|forge tags, for arbitrary, select, or all messages]], including under conditions of [[Digital signature forgery|known-]] or [[Digital signature forgery|chosen-message]]. It should be computationally infeasible to compute a valid tag of the given message without knowledge of the key, even if for the worst case, we assume the adversary knows the tag of any message but the one in question.<ref>The strongest adversary is assumed to have access to the signing algorithm without knowing the key. However, her final forged message must be different from any message she chose to query the signing algorithm before. See Pass's discussions before def 134.2.</ref>

Formally, a '''message authentication code''' ('''MAC''') system is a triple of efficient<ref name=":1">Theoretically, an efficient algorithm runs within probabilistic polynomial time.</ref> algorithms (''G'', ''S'', ''V'') satisfying:
* ''G'' (key-generator) gives the key ''k'' on input [[unary numeral system|1<sup>''n''</sup>]], where ''n'' is the security parameter.
* ''S'' (signing) outputs a tag ''t'' on the key ''k'' and the input string ''x''.
* ''V'' (verifying) outputs ''accepted'' or ''rejected'' on inputs: the key ''k'', the string ''x'' and the tag ''t''.

''S'' and ''V'' must satisfy the following:

: {{math|1=Pr [ ''k'' ← ''G''(1<sup>''n''</sup>), ''V''( ''k'', ''x'', ''S''(''k'', ''x'') ) = ''accepted'' ] = 1}}.<ref>Pass, def 134.1</ref>

A MAC is '''unforgeable''' if for every efficient adversary ''A''

: {{math|1=Pr [ ''k'' ← ''G''(1<sup>''n''</sup>), (''x'', ''t'') ← ''A''<sup>''S''(''k'', · )</sup>(1<sup>''n''</sup>), ''x'' ∉ Query(''A''<sup>''S''(''k'', · )</sup>, 1<sup>''n''</sup>), ''V''(''k'', ''x'', ''t'') = ''accepted''] < negl(''n'')}},

where ''A''<sup>''S''(''k'', · )</sup> denotes that ''A'' has access to the oracle ''S''(''k'', · ), and Query(''A''<sup>''S''(''k'', · )</sup>, 1<sup>''n''</sup>) denotes the set of the queries on ''S'' made by ''A'', which knows ''n''. Clearly we require that any adversary cannot directly query the string ''x'' on ''S'', since otherwise a valid tag can be easily obtained by that adversary.<ref>Pass, def 134.2</ref>