Editing Digital signature (section)

==Definition==
{{Main|Public-key cryptography}}

A digital signature scheme typically consists of three algorithms:
* A ''[[key generation]]'' algorithm that selects a ''private key'' [[Uniform distribution (discrete)|uniformly at random]] from a set of possible private keys. The algorithm outputs the private key and a corresponding ''public key''.
* A ''signing'' algorithm that, given a message and a private key, produces a signature.
* A ''signature verifying'' algorithm that, given the message, public key and signature, either accepts or rejects the message's claim to authenticity.

Two main properties are required:

First, the authenticity of a signature generated from a fixed message and fixed private key can be verified by using the corresponding public key.

Secondly, it should be computationally infeasible to generate a valid signature for a party without knowing that party's private key.
A digital signature is an authentication mechanism that enables the creator of the message to attach a code that acts as a signature.
The [[Digital Signature Algorithm]] (DSA), developed by the [[National Institute of Standards and Technology]], is one of [[Digital signature#Some digital signature algorithms|many examples]] of a signing algorithm.

In the following discussion, 1<sup>''n''</sup> refers to a [[Unary numeral system|unary number]].

Formally, a '''digital signature scheme''' is a triple of probabilistic polynomial time algorithms, (''G'', ''S'', ''V''), satisfying:
* ''G'' (key-generator) generates a public key (''pk''), and a corresponding private key (''sk''), on input 1<sup>''n''</sup>, where ''n'' is the security parameter.
* ''S'' (signing) returns a tag, ''t'', on the inputs: the private key (''sk''), and a string (''x'').
* ''V'' (verifying) outputs ''accepted'' or ''rejected'' on the inputs: the public key (''pk''), a string (''x''), and a tag (''t'').
For correctness, ''S'' and ''V'' must satisfy

: Pr [ (''pk'', ''sk'') ← ''G''(1<sup>''n''</sup>), ''V''( ''pk'', ''x'', ''S''(''sk'', ''x'') ) = ''accepted'' ] = 1.<ref name="IjhTrs">Pass, def 135.1</ref>

A digital signature scheme is '''secure''' if for every non-uniform probabilistic polynomial time [[Adversary (cryptography)|adversary]], ''A''

: Pr [ (''pk'', ''sk'') ← ''G''(1<sup>''n''</sup>), (''x'', ''t'') ← ''A''<sup>''S''(''sk'', · )</sup>(''pk'', 1<sup>''n''</sup>), ''x'' ∉ ''Q'', ''V''(''pk'', ''x'', ''t'') = ''accepted''] < [[Negligible function|negl]](''n''),

where ''A''<sup>''S''(''sk'', · )</sup> denotes that ''A'' has access to the [[Oracle machine|oracle]], ''S''(''sk'', · ), ''Q'' denotes the set of the queries on ''S'' made by ''A'', which knows the public key, ''pk'', and the security parameter, ''n'', and ''x'' ∉ ''Q'' denotes that the adversary may not directly query the string, ''x'', on ''S''.<ref name="IjhTrs" /><ref name="nOvvy">Goldreich's FoC, vol. 2, def 6.1.2. Pass, def 135.2</ref>