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:

Diffie-Helman key agreement

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

  1. $A → B: a\ P$
  2. $B → A: b\ P$
  3. $A: a\ (b\ P) = ab\ P$
  4. $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

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

Encryption

Given a message and public key $Q$:

  1. Pick a random key $r$.
  2. Compute $G = r\ Q$.
  3. Encrypt the message using $G$.
  4. Compute $R = r\ P$.
  5. Provide $R$ and the ciphertext

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

Decryption

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

  1. Compute $G = q\ R$.
  2. 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

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

Sign

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

  1. Compute $k = \mathrm{H_A}(r, M)$.
  2. Compute $K = k\ P$.
  3. Compute $s = \mathrm{H_B}(K, Q, m)$.
  4. Compute $s' = k + qs$.
  5. 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:

  1. Compute $s = \mathrm{H_B}(K, Q, m)$.
  2. Compute $K' = s'\ P - s Q$.
  3. 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?

  1. $A, B: C = \mathrm{H}(c)$.
  2. $A → B: a\ C$.
  3. $B → A: b\ C$.
  4. $A: a\ (b\ C) = ab\ C$.
  5. $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.

  1. Generate a random number $b$.
  2. Computer $B = b\ P$.
  3. Compute $M = m\ B$.
  4. Provide $M$ as the blinded message to be signed
  5. 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.

  1. Calculate $S = a\ M$.
  2. 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

  1. Compute $b^{-1}$
  2. Compute $S' = b^{-1}\ S$
  3. 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:

3-party Diffie-Helman agreement

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

  1. $A → B, C: a\ P$
  2. $B → A, C: b\ P$
  3. $C → A, B: c\ P$
  4. $A: a\ e(bP, cP) = abc\ e(P, P)$
  5. $B: b\ e(aP, cP) = abc\ e(P, P)$
  6. $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:

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}^*$.

  1. Pick a random number $r$.
  2. Compute $Q = \mathrm{H_A}(A)$.
  3. Compute $G = e(Q, s\ P)$.
  4. Compute $G' = r\ G$.
  5. Encrypt the message using key stream $\mathrm{H_2}(G')$.
  6. Compute $r\ P$.
  7. 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:

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

Decryption

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

  1. Compute $G' = e(D, r\ P)$.
  2. 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:

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:

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 $κ$.

  1. Compute a perfect $(2,2)$-sharing of $κ$ as $κ_1$ and $κ_2$.
  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 $κ$.

  1. Compute a perfect $(2, 2)$-sharing of $κ$ as $κ_1$ and $κ_2$.
  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

Other

Proof-of-work

Secret sharing scheme

Remco Bloemen
Math & Engineering
https://2π.com