Someone's Intermediate Representation

0%

All info comes from Manuel’s slides on Lecture 1.

# Five Main Types of Attacks

• Ciphertext only: Attacker has only a copy of the ciphertext
• Known Plaintext Attack: Attacker has a copy of ciphertext and corresponding plaintext
• Chosen Plaintext Attack: Attacker chooses the plaintext to be encrypted.
• Chosen Ciphertext Attack: Attacker chooses the ciphertext to be decrypted.
• Chosen Plaintext and Ciphertext Attack: Attacker chooses any plaintext to be encrypted or ciphertext to be decrypted.

# OTP (One Time Pad)

By XORing message and key, it is almost not possible to decrypt the ciphertext.

Consider the previous attack methods, the breaking results turn out to be

• Ciphertext only: all messages of same length can have possibility.
• KPA/CCA/CPA: only reveal part of the key used during the attack. (Since key means a set of key for XOR)

# Hill Cipher

First we should have a look at the inverse of matrix of $m\times m$ size, consider $m=2$ or $3$:
$$A\equiv\begin{pmatrix}a&b\\c&d\end{pmatrix}, A^{-1}\equiv\dfrac{1}{\mid A\mid}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}\\ A\equiv\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix},A^{-1}\equiv\dfrac{1}{\mid A\mid}\begin{pmatrix}\begin{vmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{vmatrix}&\begin{vmatrix}a_{13}&a_{12}\\a_{33}&a_{32}\end{vmatrix}&\begin{vmatrix}a_{12}&a_{13}\\a_{22}&a_{23}\end{vmatrix}\\\begin{vmatrix}a_{23}&a_{21}\\a_{33}&a_{31}\end{vmatrix}&\begin{vmatrix}a_{11}&a_{13}\\a_{31}&a_{33}\end{vmatrix}&\begin{vmatrix}a_{13}&a_{11}\\a_{23}&a_{21}\end{vmatrix}\\\begin{vmatrix}a_{21}&a_{22}\\a_{31}&a_{32}\end{vmatrix}&\begin{vmatrix}a_{12}&a_{11}\\a_{32}&a_{31}\end{vmatrix}&\begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix}\end{pmatrix}$$
Then by Cramer’s Rule that: Let $A$ be an $m\times m$ matrix, then $\text{Adj}(A)\cdot A=\text{det}(A)I_{m}$, where $\text{Adj}(A)$ donates the adjugate of $A$.

Thus, $A$ must be invertible to get $A^{-1}$ and $\text{Adj}(A)$. ($\text{Adj}(A)=\begin{vmatrix}A\end{vmatrix}A^{-1}$)

Consider the matrix inversion on mod $n$, then by $A\cdot A^{-1}\equiv I_{m}\text{ mod }26$, we can see that $\text{det}(A)$ must be invertible modulo $n$.

Take $A=\begin{pmatrix}1&1&1\\1&2&3\\1&4&9\end{pmatrix}\text{ mod }11$ as example. We can see that $A^{-1}=\dfrac{1}{2}\begin{pmatrix}6&-5&1\\-6&8&-2\\2&-3&1\end{pmatrix}\text{ mod }11$. $6$ is invertible modulo $11$ for $2$, then $A^{-1}=\begin{pmatrix}3&3&6\\8&4&10\\1&4&6\end{pmatrix}\text{ mod }11$.

The key for Hill cipher requires $n\times n$ matrix $K\text{ mod }26$, with $\text{gcd}(\text{det}(K),n)=1$.

# Symmetric and Asymmetric Key

Symmetric scheme use same key for both encrypt and decrypt. Thus the key management problem arises when user number increases: $n$ users means $O(n^2)$ keys.

Asymmetric scheme creates a pair of public and private key. Encrypt with public key and decrypt with private key.

# Double Encryption

Consider symmetric encryption using function $f$ and key $k$:

• Simple encryption: $c=f_{k}(m)$
• Double encryption: $c=f_{k_2}(f_{k_1}(m))$
• Decryption: $m = f_{k_1}^{-1}(f_{k_2}^{-1}(c))$

Assume the KPA setup, then we can setup meet in the middle attack.

• $\forall k\in\lbrace\text{Key}\rbrace$, compute and store the ciphertexts $c_i=f_{k_i}(m)$.
• Compute $m_i=f_{k_i}^{-1}(c)$ and find the matching $c_i$.
• Recover the $k_1$ and $k_2$.

Thus double encryption do not guarantee a multiple instruction complexity, it can only guarantees a plus instruction complexity. (Not $I_1\times I_2$ but $I_1 +I_2$)

# Zero Knowledge Proof

If Bob wants to prove he knows a secret path without revealing it, what should he do?

The strategy is that:

• Alice hides while Bob go L or R.
• Alice randomly asks Bob to exit on L or R.
• If Bob is on the wrong side he uses the secret path or he returns.
• Repeat previous steps many times.

## Graph Isomorphism and Hamiltonian Circuit

Graph Isomorphism is defined on $G_1=(V_1,E_2)$ and $G_2=(V_2,E_2)$ two simple graphs.

If there exists a bijection function $\varphi:V_1\to V_2$ such that the induced map $\varphi_\ast:E_1\to E_2, (a,b)\mapsto(\varphi(a),\varphi(b))$ is bijective. Such $\varphi$ is a graph isomorphism.

Graph isomorphism is not known to be $NPC$ problem, but the best known algorithm has exponential complexity.

Hamilton circuit in $G$ is a simple circuit that passes through every vertex in $G$ exactly once. It is proven to be $NPC$ and best known algorithm has exponential complexity.

In this scenario, we can set the condition as

Bob Alice
A graph $G$ Bob’s graph $G$
Hamiltonian Circuit in $G$

The process goes like:

• Bob generates $H\cong G$ and commits it.
• Alice randomly asks for either isomorphism map or Hamiltonian circuit in $H$.
• Bob show the required result.

The procedure is not related to the security level like $2^{128}$ stuff.