Signatures

Used to bring authenticity in pk-encryption setting.

Properties:

• publicly verifiable
• transferable
• non-repudiation

Definition: Digital signature scheme consists of three PPT algorithms:

• $\text{Gen}(1^n)\to (pk,sk)$
• $\text{Sign}(sk,m)\to \sigma$
• $\text{Vrfy}(pk,\sigma )\to b\in \{0,1\}$

Signature experiment: ${\text{Sig-forge}}_{\mathcal{A},\Pi }(n)$:

• $\text{Gen}(1^n)$ is run to obtain $pk,sk$
• $\mathcal{A}$ has access to ${\text{Sign}}_{sk}(\cdot )$ oracle, and outputs $m,\sigma$. Let $\mathcal{Q}$ be set of all queries by $\mathcal{A}$.
• $\mathcal{A}$ succeeds if ${\text{Vrfy}}_{pk}(\cdot )=1$ and $m\notin \mathcal{Q}$.

$\mathrm{Pr}[{\text{Sig-forge}}_{\mathcal{A},\Pi }(n)=1]\le \text{negl}(n)$

Hash-and-Sign paradigm: use a hash when a signature scheme of length $l$ is available, and messages are of longer length to create a digest of length $l$ as $H_s(m)$ where $s={\text{Gen}}_H(1^n)$.

rsa signatures

TODO

PKI

Digital Certificate: just a notion of public key signature binding the identity of a public entity to that public key.

${\text{cert}}_{C\to B}\stackrel{def}{=}{\text{Sign}}_{s{k}_C}({\text{Bob’s key is pk}}_B)$

Party $C$ signature should be trustworthy to be considered a certificate, and is generally known as Certificate authority (CA). Certificate can be used to build trust between two strange parties using a trusted party that notarises that $P_1$ indeed is the owner of the key.

• Can build a web of trust using single CA, but susceptible to attacks and single point of failure.
• Multiple CAs are usually configured on every browser, network devices which helps to decentralise the power a CA has.
• Certificate Chain is employed where any root authority with a certificate gives power to the party to issue certificates as a proxy.
• PGP: complete cypherpunk approach to web of trust. Anyone can issue a certificate for anyone else, and recipient has to choose whether to believe the authority issuing the certificate.
• Revocation of certificates: using expiration or Certificate expiration list broadcasted by CA at periodic time.