Trying out math typesetting

Cryptography Misc 2018-08-20

I think I may need maths a lot in my posts so the second step is to set up some math engine. The default math engine suggested by Kramdown is MathJax. That was fairly easy to set up but I found KaTeX a better option because it is faster.

After fumbling with these web stuffs that I was not used to, I finally got KaTeX working by mainataining a local copy of KaTeX and using some JavaScript (See Reference). The KaTeX gem suggested in Kramdown with KaTeX did not work for me. Maybe I made some incorrect configurations. Anyways it is working now, Hooray.

Update
I wanted to use Jekyll plugins that are not supported by Github, so I decided to somehow build my site locally and then push the contents onto github. Then I found an elegant solution using Travis CI for Github Pages Deployment. I cannot believe I used another 3 hours to make Travis CI working. Anyway, it is working again. I reckon I will not have much time to deploy comment systems or RSS feed when next semester starts….

Something meaningful in this blog post.

So here is my solution to Exercise 2.22 ( Bias correction ) in A Graduate Course in Applied Cryptography.

Background

In cryptography, we have various formal models for the definiton of Security which enable analyses of ciphers.
To formalize Semantic Security of a cipher $\mathcal{E} = (E, D)$ over $(\mathcal{M}, \mathcal{C}, \mathcal{K})$ , we define the following game.

Game ( Bit-guessing version of SS )
There are two parties, the challenger ( $C$ ) and the adversary ( $A$ ). We normally think of both of them as probabilistic polynomial time machines. The game proceeds as follows.

$C$ generates a uniform bit $b$ and $k \gets \mathcal{K}$ ;
$A$ chooses two messages $m_0$ and $m_1$ and sends them to $C$ .
$C$ encrypts $c \gets E(k, m_b)$ and sends it to $A$ .
After examining $c$ , $A$ outputs a guess $\hat{b} \in \{0, 1\}$ .

Define the advantage Adv $(A, \mathcal{E})$ as $\left\vert\Pr[\hat{b} = b] - \frac{1}{2}\right\vert$ .
The cipher $\mathcal{E}$ is SS iff for all PPT $A$ , the advantage is negligible (in security parameter $\lambda$ ).

A short description of the problem

In the previous definition we take the absolute value of the advantage. This is a good definition because if our adversary $A$ breaking SS actually has the correct guess with probability of some $\frac{1}{2}-\vert\epsilon\vert$ for $\epsilon$ non-negligible, we can make another adversary $A'$ who always output the opposite of what $A$ outputs. Then $A'$ has sucess probability greater than $\frac{1}{2}$ .

But is the above argument actually valid? Spoiler: NO.
In the problem, we explore how an adversary $A$ who guesses wrong more often (i.e. $\Pr[\hat{b} = b] = \frac{1}{2} - \vert\epsilon\vert$ can be converted into one who guesses right more often, while preserving the non-negligiblilty of the advantage.

Part (a) and (b) of the Problem

Part (a) showed that one can construct an adversary $\tilde{A}$ with success probability $\frac{1}{2} + \epsilon^2$ .
The construction has two phases.

$\tilde{A}$ first acts as a challenger and test $A$ using a randomly generated $k$ and $b$ .
then runs using inputs from the real challenger .
- If in 1. $A$ guessed correctly, $\tilde{A}$ simply outputs whatever bit $A$ output.
- Otherwise, $\tilde{A}$ outputs the opposite of whatever bit $A$ output.

The success probability can be found by direct calculation on some probabilties.

Part (b) raised the question of why one cannot simply construct $B$ that flips the output of $A$ and argue that one of $A$ or $B$ always outputs correct bit with positive $\epsilon$ .

The explanation is kind of tricky but quite interesting in my opinion. One should understand the formal definitions of SS (that one using security parameter $\lambda$ ) to understand the problem.
Spoiler Alert: $\epsilon$ is actually a function in $\lambda$ , so it can be positive or negative (or both).

Part (c) of the problem

First construction

Part (c) asks the reader to give a solution with success probability at least $\frac{1}{2}(1 + \vert\epsilon\vert)$ .
I am not sure about the correctness of my solution because I proved a somehow stronger weird-looking result.

First assume $\epsilon$ is a known non-negligible function, i.e. we know constants $c$ and $a$ such that $\vert\epsilon(\lambda)\vert > \frac{1}{a\lambda^c}$ for infinitely many $\lambda$ .

Let $t = a\lambda^{2c + 1}$ . Let $\bar{A}$ be the following adversary.

Run $t$ indepedent tests of $A$ .
Run using inputs from the real challenger .
- If $A$ guesses right more often in the previous tests, we output whatever $A$ output when faced with the real challenger $C$ .
- Otherwise we output the oppositie of $A$ ’s output.

Analysis

Let $X$ be the number of correct guesses in phase 1. of the algorithm, then

$\begin{aligned} \Pr[\text{majority is wrong} \vert \epsilon(\lambda) > 0] &\le \Pr[(\sum X_i \le (1 - \delta) \mu)] && \text{where } \delta = \frac{2\epsilon}{1 + 2\epsilon}, \mu = \mathbb{E}[X],\\ &\le e^{-\frac{1}{3}\frac{2t\epsilon^2}{1 + 2\epsilon}} = e^{-\frac{2\lambda}{3 + 6\epsilon}} \end{aligned}$

is negligible. Similarly $\Pr[\text{majority is correct} \vert \epsilon(\lambda) < 0 ]$ is negligible.

So if we denote negligible functions with the symbol negl, we have

$\begin{aligned} \Pr[\hat{b} = b] &= (1 - \text{negl})(\frac{1}{2} + \vert\epsilon\vert) + (\text{negl})(\frac{1}{2} - \vert\epsilon\vert)\\ &= \frac{1}{2} + (1 - \text{negl}) \vert\epsilon\vert \end{aligned}$

$t$ is polynomial in $\lambda$ , we can boost it by some polynomial factor of $\lambda$ to make the negligible term arbtrarily small. Thus we have proven there exists a PPT with success probability at least $\frac{1}{2}(1 + \vert\epsilon\vert)$ .

Removing the neccessity of knowing $\epsilon$

In the first construstion we need to know how $\epsilon$ is bounded to construct a concrete adversary. We can actually remove this requirement if we only need to show the existence of such a machine.

The trick is to construct a series of machines $B_i$ for $i = 1, 2, \ldots$ . And make $B_i$ have the same construction as $\bar{A}$ , except it uses $t_i = n^i$ . Then among these PPT we should be able to find one using more tests than $\bar{A}$ . ~~I wish to use the LaTeX environment proof but KaTeX did not seem to support it otherwise I would like to put a box or something here to show I have completed the proof in a single paragraph.~~

Post Script

The proof was not very elegant but the construction was quite straight forward. I wonder if there are better solutions. Do you find cryptography interesting?

Reference

using-katex-in-jekyll (Chinese only)