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/
