# Cryptographic Primitives

% Remco Bloemen % 2014-05-07

## Symmetric cryptography

### Sponge functions

### One-way functions

$$ \begin{aligned} \mathrm{H} &: &\{0,1\}^{*} &→ \{0,1\}^{l} \end{aligned} $$

$$ \begin{aligned} \mathrm{H}(X_1) &= \mathrm{H}(X_2) &&⇔ &X_1 &= X_2 \end{aligned} $$

Given $Y$ compute $X$ such that $\mathrm{H}(X) = Y$.

### Message authentication codes

### Pseudo random number generator

### Key derivation functions

### Symmetric encryption

$$ \begin{aligned} \mathrm{E} &: &\{0,1\}^{l_K} × \{0,1\}^{*} &→ \{0,1\}^{*} \\ \mathrm{D} &: &\{0,1\}^{l_K} × \{0,1\}^{*} &→ \{0,1\}^{*} \end{aligned} $$

$$ \begin{aligned} \mathrm{D}(K_1, \mathrm{E}(K_2, X)) &= X &&⇔ & K_1 &= K_2 \end{aligned} $$

### Authenticated encryption

## Asymmetric cryptography

Source: http://www.larc.usp.br/~pbarreto/pblounge.html Source: http://courses.csail.mit.edu/6.897/spring04/L25.pdf

Given a group $\mathcal G$ written additively with a generator $P$, consider the following problems:

- Computational Diffie-Helman problem (CDHP): given $P$, $a\ P$ and $b\ P$ in $G$, compute $ab\ P$.
- Decisional Diffie-Helman problem (DDHP): given $P$, $a\ P$, $b\ P$ and $c\ P$ in $G$, decide whether $c = ab$ (modulo the order of $P$).
- Gap Diffie-Helman problem (GDHP): given an oracle that solves the DDHP, solve the CDHP.
- The Discrete Log Problem (DLP): given $P$ and $Q$ find a such that $Q = a\ P$. This is also written as $a = \log_P Q$.

### Diffie-Helman key agreement

Two parties $A$, $B$ have secrets $a$, $b$.

- $A → B: a\ P$
- $B → A: b\ P$
- $A: a\ (b\ P) = ab\ P$
- $B: b\ (a\ P) = ab\ P$

Now both parties have the same secret $K = ab\ P$ in $G$.

### Asymmetric encryption

This is similar to Diffie-Helman key agreement done offline.

#### Key generation

- Pick random private key $q$.
- Compute $Q = q P$.
- Publish $Q$ as public key, keep $q$ as private key.

#### Encryption

Given a message and public key $Q$:

- Pick a random key $r$.
- Compute $G = r\ Q$.
- Encrypt the message using $G$.
- Compute $R = r\ P$.
- Provide $R$ and the ciphertext

Note that $G = r\ Q = qr\ P$.

#### Decryption

Given a ciphertext, $R$ and private key $q$

- Compute $G = q\ R$.
- Decrypt the ciphertext using $G$.

Note that $G = q\ R = qr\ P$, the same as in the encryption process.

### Distributed key generation

http://distrib-rsa.sourceforge.net/

### Treshold cryptosystem

http://www.mcs.csueastbay.edu/~lertaul/IJNSTCPAPERV11.pdf

### Digital signatures

The method described here is EdDSA. https://en.wikipedia.org/wiki/EdDSA, http://ed25519.cr.yp.to/ed25519-20110926.pdf, http://blog.cr.yp.to/20140323-ecdsa.html

#### Key generation

- Pick random private key $q$.
- Pick a random salt $r$.
- Compute $Q = q\ P$.
- Publish $Q$ as public key, keep $q$ and $r$ as private key.

#### Sign

Given a message $m$, a signature can be produced with:

- Compute $k = \mathrm{H_A}(r, M)$.
- Compute $K = k\ P$.
- Compute $s = \mathrm{H_B}(K, Q, m)$.
- Compute $s' = k + qs$.
- Provide $K$ and $s'$ as the signature.

All integer calculation are done in a sufficiently large prime field.

#### Verify

Given a message $m$, a public key $Q$ and a signature $K$, $s'$ we can verify that the signature originated from the associated private key with:

- Compute $s = \mathrm{H_B}(K, Q, m)$.
- Compute $K' = s'\ P - s Q$.
- Verify $K = K'$.

This should hold true because

$$ \begin{aligned} K' &= s'\ P - s\ Q\\ &= (k + qs)\ P - s (q\ P)\\ &= (k + qs - sq)\ P \\ &= k\ P \\ &= K \end{aligned} $$

#### Forward security

The goal of forward security is to limit damage when a private key or the signature algorithm gets compromised. Given a a trusted time stamping authority the digital signature scheme can be made forward secure. By adding a trusted time stamp is to the signature. It can, after an incident, be determined if the signature was made before or after the compromise. The forward secrecy of the time stamp itself can be guaranteed by periodically adding a new time stamp, or by publication in a public ledger such as a newspaper or a block chain.

### Password-authenticated key agreement

Two parties $A$, $B$ have secrets $a$, $b$ and a shared secret $c$.

$$ \begin{aligned} \mathrm{H}&:& &{0,1}^* &→& \mathcal{G} \end{aligned} $$

TODO: Is $H(c) = c\ P$ sufficient?

- $A, B: C = \mathrm{H}(c)$.
- $A → B: a\ C$.
- $B → A: b\ C$.
- $A: a\ (b\ C) = ab\ C$.
- $B: b\ (a\ C) = ab\ C$.

Now both parties have the same secret $K = ab\ C$ in $G$.

What about offline attacks?

### Zero-knowledge proof

### Blind signatures

The blind signature scheme allows a person to get a message signed by another party without revealing any information about the message to the other party. It differs from having the hash of the message signed by the signer in that the signer can not determine which of a small set of possible plaintexts the original message was.

#### Blinding

Given a message m, the message can be *blinded* to make it unreadable to
the signer.

- Generate a random number $b$.
- Computer $B = b\ P$.
- Compute $M = m\ B$.
- Provide $M$ as the blinded message to be signed
- Remember $b$ as the blinding factor

Note that $M = m\ B = bm\ P$.

#### Signing

Given a blinded message $M$ and an private key $a$, the blinded message can be signed by.

- Calculate $S = a\ M$.
- Provide $S$ as the signature.

Note that $S = a\ M = abm\ P$.

#### Unblinding

Given a blinded signature $S$ and blinding factor $b$, unblind the signature

- Compute $b^{-1}$
- Compute $S' = b^{-1}\ S$
- Provide $S'$ as the signature for $M$.

Note that $S' = b^{-1}\ S = abb^{-1}m\ P = am\ P$.

#### Verifying

## Pairing cryptography

Given two groups $\mathcal G$ and $\mathcal{G'}$ written multiplicatively and a bilinear non-degenerate map (a.k.a a paring) $e : \mathcal{G} × \mathcal{G} → \mathcal{G'}$.

It is currently not known how to construct pairings with $\mathcal{G} = \mathcal{G'}$. Typically $\mathcal{G}$ is an elliptic-curve group and $G'$ is a finite field. Weil and Tate pairings are two well-known pairing schemes.

Bilinearity:

$$ ∀_{P ∈ \mathcal{G}}, ∀_{Q ∈ \mathcal{G}} , ∀ a, b ∈ ℤ_q^* e(a\ P, b\ Q) = ab\ e(P, Q) $$

Non-degeneracy means that not every thing maps to the identity and in fact, given an nonzero element $P∈\mathcal{G}$.

With parings one can efficiently solve DDHP since $c = ab$ if and only if $e(a\ P, b\ P) = e(P, c\ P)$. This solves the DDHP for $\mathcal{G}$ and can be used as an oracle for the GDHP in $\mathcal{G}$.

It should also be noted that the DLP in $\mathcal{G}$ can be solved in terms of the one in $\mathcal{G'}$. Suppose $Q = a\ P$ and we can solve then

$$ \begin{aligned} \log_P Q &= \log_{e(P, P)} {e(P, Q)} \\ &= \log_{e(P, P)} {e(P, a\ P)} \\ &= \log_{e(P, P)} \left(a\ e(P, P) \right) \\ &= a \end{aligned} $$

It also introduces a new problem:

- Bilinear Diffie-Helman problem (BDHP): given given $P$, $aP$, $bP$ and $cP$ in $\mathcal{G}$, compute $abc e(P,P)$

### 3-party Diffie-Helman agreement

Three parties $A$, $B$, $C$ have secrets $a$, $b$, $c$.

- $A → B, C: a\ P$
- $B → A, C: b\ P$
- $C → A, B: c\ P$
- $A: a\ e(bP, cP) = abc\ e(P, P)$
- $B: b\ e(aP, cP) = abc\ e(P, P)$
- $C: c\ e(aP, bP) = abc\ e(P, P)$

Note that this scheme is not secure under the *IND-CCA2* model, which
means it is vulnerable to adaptive chosen-ciphertext attacks. It can be
made secure with the Fujisaki-Okamoto construction. Essentially this
amounts to adding a random nonce to the message and including a hash.
The scheme is then secure under the *IND-CCA2* model with the BDH
assumption, the Random Oracle model and the hash.

Other desirable properties are:

*Recipient anonymity*, or*key privacy*: it should not be possible to determine which public key was used in the encryption process.

Note that steps $(1, 2, 3)$ and $(4, 5, 6)$ can be done in parallel. At the end all parties have the same secret $K = abc\ e(P, P)$ in $\mathcal{G'}$.

### Identity-based encryption

The public key can be arbitrary text strings, and therefore do not have to be looked up.

It allows for a lazy PKI, people can encrypt messages for the recipient, and when the recipient wants to open them, he can ask the authority for the private key belonging to his identity. The authority can hand out the private key after the users authority is verified. Note that after the initial set up and domain parameter distribution, the authority is only involved for retrieving the private key lazily.

Set up a paring as above, a secret key s known only to the authority, public key $s\ P$ known to all parties and two random oracles:

$$ \begin{aligned} \mathrm{H_1} &:& & \{0,1\}^* &→& \mathcal{G} \\ \mathrm{H_2} &:& & \mathcal{G'} &→& \{0,1\}^* \end{aligned} $$

#### Encrypt

Encrypt a message $M ∈ {0,1}^*$ to public key $A ∈ {0,1}^*$.

- Pick a random number $r$.
- Compute $Q = \mathrm{H_A}(A)$.
- Compute $G = e(Q, s\ P)$.
- Compute $G' = r\ G$.
- Encrypt the message using key stream $\mathrm{H_2}(G')$.
- Compute $r\ P$.
- Provide $r\ P$ and the ciphertext to the recipient.

Note that $G' = r\ G = r\ e(Q, s\ P) = sr\ e(Q, P)$, this will be important when decrypting.

#### Deriving the private key

Given a public key $A ∈ {0,1}^*$ the authority can derive the corresponding private key:

- Validate the identity of requester
- Compute $Q = \mathrm{H_A}(A)$.
- Compute $D = s\ Q$.
- Provide $D$ as the private key

#### Decryption

Given a private key $D$, the ciphertext and $r\ P$ construct as above.

- Compute $G' = e(D, r\ P)$.
- Decrypt the ciphertext using the keystream $\mathrm{H_2}(G')$.

Note that $G' = e(D, r\ P) = e(s\ Q, r\ P) = sr\ e(Q, P)$ and thus equals the $G'$ from the encryption process.

#### Final remarks

Note that this scheme is not secure under the *IND-CCA2* model, which
means it is vulnerable to adaptive chosen-ciphertext attacks. It can be
made secure with the Fujisaki-Okamoto construction. Essentially this
amounts to adding a random nonce to the message and including a hash.
The scheme is then secure under the *IND-CCA2* model with the BDH
assumption, the Random Oracle model and the hash.

Other desirable properties are:

*Recipient anonymity*, or*key privacy*: it should not be possible to determine which public key was used in the encryption process.

### Attribute based encryption

Attribute based encryption builds upon identity based encryption by adding to the key management, the algorithms are the same. Attributes take the form of credentials issued by an authority that is in essence an AA (attribute authority).

Can implement any access-control policy expressible as a monotone
boolean formula on attribute values. That is, any function using *and*
and *or* without negation over the attributes. Should it be required the
absence of an attribute can be implemented as a separate attribute.

A resource protected with an access-control policy can only be read using a key with attributes that satisfy the access-control policy. In particular it is not possible to collude.

First the boolean function to is converted to *disjunctive normal form*
or another form involving only attributes, and and or operations. Some
algorithms optimize these for size and might be relevant:

- https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
- https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer

Given a message m to be encrypted with attribute a. Encrypt the message using identity based encryption on identity "a".

Given a message m to be encrypted with attribute a for user u. Encrypt the message with identity "u || a".

For key management purposes it can be useful to add expiry dates to the keys. Given a message m to be encrypted with attribute a for user u valid in month x. Encrypt the message with identity "u || a || x".

#### Disjunctive construction

$$ f = f_1 ∨ f_2 $$

Given $κ$.

- Compute a perfect $(2,2)$-sharing of $κ$ as $κ_1$ and $κ_2$.
- Compute $f(κ) = (f_1(κ), f_2(κ))$.

To recover $κ$ both $f_1$ and $f_2$ are required. With generic *j* out of
*n* sharing schemes this can be generalized.

#### Conjunctive construction

$$ f = f_1 ∧ f_2 $$

Given $κ$.

- Compute a perfect $(2, 2)$-sharing of $κ$ as $κ_1$ and $κ_2$.
- Compute $f(κ) = (f_1(κ_1), f_2(κ_2))$.

To recover $κ$ either $f_1$ or $f_2$ can be used.

### Key revocation schemes

### Functional Encryption

## Homomorphic cryptography

### Additive homomorphic

e.g. Damgård–Jurik cryptosystem

Additive homomorphic: given only the public key and the ciphertext of $m_1$ and $m_2$, you can derive the encryption of $m_1 + m_2$. As a consequence, it is also possible to do multiplication by a plaintext integer.

The encryption is also randomized, encrypting the same plaintexts with the same keys will result in different ciphertexts. A blinding operation can be implemented by encrypting 0 and adding it to the ciphertext.

The Pallier cryptosystem, which is very similar, with an additional hash
can be proven *IND-CCA2* secure in the random oracle model under the
DCRA assumption.

### Signed network coding

https://en.wikipedia.org/wiki/Homomorphic_Signatures_for_Network_Coding

### Fully homomorphic

- http://www.cs.ut.ee/~lipmaa/crypto/link/public/homomorphic.php
- https://github.com/shaih/HElib
- https://code.google.com/p/thep/