Cryptographic Primitives

Remco Bloemen

2014-05-07

Symmetric cryptography

Sponge functions

One-way functions

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

H(X1)=H(X2)X1=X2 \begin{aligned} \mathrm{H}(X_1) &= \mathrm{H}(X_2) &&\iff &X_1 &= X_2 \end{aligned}

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

Message authentication codes

Pseudo random number generator

Key derivation functions

Symmetric encryption

E:{0,1}lK×{0,1}*{0,1}*D:{0,1}lK×{0,1}*{0,1}* \begin{aligned} \mathrm{E} &: &\{0,1\}^{l_K} \times \{0,1\}^{*} &\rightarrow \{0,1\}^{*} \\ \mathrm{D} &: &\{0,1\}^{l_K} \times \{0,1\}^{*} &\rightarrow \{0,1\}^{*} \end{aligned}

D(K1,E(K2,X))=XK1=K2 \begin{aligned} \mathrm{D}(K_1, \mathrm{E}(K_2, X)) &= X &&\iff & 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 PP, consider the following problems:

Diffie-Helman key agreement

Two parties AA, BB have secrets aa, bb.

  1. AB:aPA \rightarrow B: a\ P
  2. BA:bPB \rightarrow A: b\ P
  3. A:a(bP)=abPA: a\ (b\ P) = ab\ P
  4. B:b(aP)=abPB: b\ (a\ P) = ab\ P

Now both parties have the same secret K=abPK = ab\ P in GG.

Asymmetric encryption

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

Key generation

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

Encryption

Given a message and public key QQ:

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

Note that G=rQ=qrPG = r\ Q = qr\ P.

Decryption

Given a ciphertext, RR and private key qq

  1. Compute G=qRG = q\ R.
  2. Decrypt the ciphertext using GG.

Note that G=qR=qrPG = 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 qq.
  2. Pick a random salt rr.
  3. Compute Q=qPQ = q\ P.
  4. Publish QQ as public key, keep qq and rr as private key.

Sign

Given a message mm, a signature can be produced with:

  1. Compute k=HA(r,M)k = \mathrm{H_A}(r, M).
  2. Compute K=kPK = k\ P.
  3. Compute s=HB(K,Q,m)s = \mathrm{H_B}(K, Q, m).
  4. Compute s=k+qss' = k + qs.
  5. Provide KK and ss' as the signature.

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

Verify

Given a message mm, a public key QQ and a signature KK, ss' we can verify that the signature originated from the associated private key with:

  1. Compute s=HB(K,Q,m)s = \mathrm{H_B}(K, Q, m).
  2. Compute K=sPsQK' = s'\ P - s Q.
  3. Verify K=KK = K'.

This should hold true because

K=sPsQ=(k+qs)Ps(qP)=(k+qssq)P=kP=K \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 AA, BB have secrets aa, bb and a shared secret cc.

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

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

  1. A,B:C=H(c)A, B: C = \mathrm{H}(c).
  2. AB:aCA \rightarrow B: a\ C.
  3. BA:bCB \rightarrow A: b\ C.
  4. A:a(bC)=abCA: a\ (b\ C) = ab\ C.
  5. B:b(aC)=abCB: b\ (a\ C) = ab\ C.

Now both parties have the same secret K=abCK = ab\ C in GG.

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 bb.
  2. Computer B=bPB = b\ P.
  3. Compute M=mBM = m\ B.
  4. Provide MM as the blinded message to be signed
  5. Remember bb as the blinding factor

Note that M=mB=bmPM = m\ B = bm\ P.

Signing

Given a blinded message MM and an private key aa, the blinded message can be signed by.

  1. Calculate S=aMS = a\ M.
  2. Provide SS as the signature.

Note that S=aM=abmPS = a\ M = abm\ P.

Unblinding

Given a blinded signature SS and blinding factor bb, unblind the signature

  1. Compute b1b^{-1}
  2. Compute S=b1SS' = b^{-1}\ S
  3. Provide SS' as the signature for MM.

Note that S=b1S=abb1mP=amPS' = 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:𝒢×𝒢𝒢e : \mathcal{G} \times \mathcal{G} \rightarrow \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 GG' is a finite field. Weil and Tate pairings are two well-known pairing schemes.

Bilinearity:

P𝒢,Q𝒢,a,bq*e(aP,bQ)=abe(P,Q) \forall _{P ∈ \mathcal{G}}, \forall _{Q ∈ \mathcal{G}} , \forall 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𝒢P∈\mathcal{G}.

With parings one can efficiently solve DDHP since c=abc = ab if and only if e(aP,bP)=e(P,cP)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=aPQ = a\ P and we can solve then

logPQ=loge(P,P)e(P,Q)=loge(P,P)e(P,aP)=loge(P,P)(ae(P,P))=a \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 AA, BB, CC have secrets aa, bb, cc.

  1. AB,C:aPA \rightarrow B, C: a\ P
  2. BA,C:bPB \rightarrow A, C: b\ P
  3. CA,B:cPC \rightarrow A, B: c\ P
  4. A:ae(bP,cP)=abce(P,P)A: a\ e(bP, cP) = abc\ e(P, P)
  5. B:be(aP,cP)=abce(P,P)B: b\ e(aP, cP) = abc\ e(P, P)
  6. C:ce(aP,bP)=abce(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)(1, 2, 3) and (4,5,6)(4, 5, 6) can be done in parallel. At the end all parties have the same secret K=abce(P,P)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 sPs\ P known to all parties and two random oracles:

H1:{0,1}*𝒢H2:𝒢{0,1}* \begin{aligned} \mathrm{H_1} &:& & \{0,1\}^* &\rightarrow & \mathcal{G} \\ \mathrm{H_2} &:& & \mathcal{G'} &\rightarrow & \{0,1\}^* \end{aligned}

Encrypt

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

  1. Pick a random number rr.
  2. Compute Q=HA(A)Q = \mathrm{H_A}(A).
  3. Compute G=e(Q,sP)G = e(Q, s\ P).
  4. Compute G=rGG' = r\ G.
  5. Encrypt the message using key stream H2(G)\mathrm{H_2}(G').
  6. Compute rPr\ P.
  7. Provide rPr\ P and the ciphertext to the recipient.

Note that G=rG=re(Q,sP)=sre(Q,P)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 A0,1*A ∈ {0,1}^* the authority can derive the corresponding private key:

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

Decryption

Given a private key DD, the ciphertext and rPr\ P construct as above.

  1. Compute G=e(D,rP)G' = e(D, r\ P).
  2. Decrypt the ciphertext using the keystream H2(G)\mathrm{H_2}(G').

Note that G=e(D,rP)=e(sQ,rP)=sre(Q,P)G' = e(D, r\ P) = e(s\ Q, r\ P) = sr\ e(Q, P) and thus equals the GG' 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:

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=f1f2 f = f_1 \lor f_2

Given κ\kappa .

  1. Compute a perfect (2,2)(2,2)-sharing of κ\kappa as κ1\kappa _1 and κ2\kappa _2.
  2. Compute f(κ)=(f1(κ),f2(κ))f(\kappa ) = (f_1(\kappa ), f_2(\kappa )).

To recover κ\kappa both f1f_1 and f2f_2 are required. With generic j out of n sharing schemes this can be generalized.

Conjunctive construction

f=f1f2 f = f_1 \wedge f_2

Given κ\kappa .

  1. Compute a perfect (2,2)(2, 2)-sharing of κ\kappa as κ1\kappa _1 and κ2\kappa _2.
  2. Compute f(κ)=(f1(κ1),f2(κ2))f(\kappa ) = (f_1(\kappa _1), f_2(\kappa _2)).

To recover κ\kappa either f1f_1 or f2f_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 m1m_1 and m2m_2, you can derive the encryption of m1+m2m_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