Happy days + learning cryptography

I'm pretty happy today since I managed to solve 3 problems in codeforces and had the idea for problem D (a binary search based solution) but could not figure out the implementation details in time.

I am trying to learn some cryptography so that I can better understand blockchain technology. I am following Prof. Shafi Goldwasser's (a legend in computer science) lectures to do this. I will use this post to record some notes on the first lecture.

First some important notation is introduced. We define an encryption scheme as a triple $(G,E,D)$ where

• $G(1^k)$ outputs a secret key of length $k$.
• $E(sk, m)$ takes a secret key and a message and outputs ciphertext.
• $D(sk, m')$ takes a secret key and a ciphertext and outputs plaintext.

We also assume a message space $M$ which defines a probability distribution over all possible messages, a key space $K$, and a ciphertext space $C$, which is just a probability distribution which is dependent on $M$ and $K$.

Note that $G$ must be probabilistic in the sense that its output must define a probability distribution. If not our adversary could easily decrypt any ciphertext since there exists only one secret key for each $k$. If we allow $E$ to be probabilistic then we could have many possible ciphertexts for the same message. Similarly, if $D$ is probabilistic, we allow for a ciphertext to have many possible plaintexts. For this to make sense, we demand that w.h.p the decryption is correct.

By correctness, we mean the following: $D(sk, E(sk, m))=m$. Additionally, we need security, i.e. it should be hard for our adversary to decrypt the ciphertext. Usually, this is done by reduction to some "hard" problem.

Shanon secrecy is demanding that $\mathbb{P}[M=m]=\mathbb{P}[M=m \mid C=c]$, where $c=E(sk, m)$. This basically says that the attacker does not learn anything new about the message by looking at the ciphertext.

The notion of perfect indistinguishability is the condition that $\mathbb{P}[C=c \mid M=m]=\mathbb{P}[C=c \mid M=m']$. This says that for any pair of messages, by looking at the ciphertext, we cannot learn/distinguish between which message, $m$ or $m'$, was sent.

It turns out that these two concepts are equivalent. The lecture concludes by giving an example encryption scheme which achieves Shanon secrecy. This scheme is called the one-time pad:

• $G(1^k)$ outputs a random string from $\{0,1\}^k$.
• $E(sk, m)$ outputs $m \oplus sk$.
• $D(sk, m')$ outputs $m' \oplus sk$.

This works because $(m \oplus sk) \oplus sk = m$. Additionally, it can be shown that one-time pads achieve Shanon secrecy, however, a one-time pad can only send one message with the same secret key, if it sends two we no longer have Shanon secrecy.

Some codeforces problem + a little puzzle

We are given some array $a$ of length $n$ which is initially populated with only $0$'s. We also have a pointer which starts pointed at the first element of $a$. Given the pointer is at position $i$, we can make the following moves:

• add $1$ to $a[i]$ and move the pointer one to the right, or
• subtract $1$ to $a[i]$ and move the pointer one to the left.

We are given some target array of length $n$. Can we transform $a$ into the target array such that the pointer also ends at the first element in $a$?

We first note that because the pointer must start and end in the first position of $a$, the target array sum must be $0$. Additionally, if we look at what a move is actually doing on the following example:

$a_1, a_2, a_3, a_4, a_5$

+     +     +     + 

       -     -     -     -

The overlapping + and - just cancel out and so the operation actually has the form +...+_____-

We observe that whenever we have a - we must also have at least one + preceding it by the move's anatomy. Thus the prefix sums must be non-negative. It turns out this condition is also sufficient.

Extra puzzle:

Imagine $n$ glasses upside-down on a table. In one move, we can flip any group of $n-1$ glasses. For which values of $n$ can we turn the glasses up? For these values of $n$ devise an algorithm for doing so in the minimum number of moves.

So first we note that when $n=1$ it is clear that it is impossible. For $n=2$ it is trivially possible. For $n\geq 3$, we need to think a little bit.

In order to flip every glass over, we need to flip each glass an odd number of times. Consider the following procedure.

• number the glasses from $1$ to $n$.
• for every $g=1$ to $n$, flip all glasses except for glass $g$.

Fix any glass $g$, it is flipped $n-1$ times by this procedure. Thus if $n$ is even, all glasses will be turned over. The remaining questions are:

1. What about $n>1$ odd? (Conjecture, it is not possible)
2. Is our algorithm for even $n$ optimal. (Conjecture, yes)

Note that we will never flip the same set of $n-1$ glasses twice. Since the second will undo the effects of the first. Thus if it is possible it is always possible in $\leq n$ moves.

Consider odd $n$. At any given moment there must exist at least one upside-down glass. After $1\leq i<n$ moves suppose WLOG we have excluded $1, 2, ..., i$. Each of these glasses will have been flipped $i-1$ times and all others will have been flipped $i$ times. Thus for all $i<n$ we have glasses which are flipped and unflipped. Thus we need at least $n$ moves and it is impossible for odd $n$.

Line Empire Codeforces

We are given $N$ cities on an integer number line at positions $0<x_1<x_2<...<x_N$, where our capital is initially at position 0. Initially only the capital is conquered. We can make the following moves:

1. Move the capital at $x_i$ to any conquered city at $x_j$ for a price of $a\cdot |x_i-x_j|$,
2. Conquer an unconquered city at position $x_j$ where our capital is at $x_i$ for a price of $b\cdot |x_i-x_j|$ so long as all cities on path between capital and unconquered city are conquered already.

We are looking for the minimum price to conquer all cities. First let's make some observations:

• We are forced to conquer the cities in the order $x_1, x_2, ..., x_N$ because of the condition that all cities on the path from the capital to the unconquered city must be already conquered.
• The first move must be to conquer $x_1$.
• We never want to move the capital left.

Let's play with a scenario.

0 -- X1 -- X2 -- X3 -- X4

Suppose the sequence of moves which minimises the price payed ends with the capital at $X3$. Then, we must pay price $a\cdot X3$ for capital movement. Since the price function is linear, the moments  when we move the capital do not affect the cost payed for capital movement, i.e. if we move the capital from $0$ to $X1$, then to $X3$, this costs the same as moving the capital straight to $X3$ from $0$.

However, since having the capital closer to the right reduces the cost payed for conquering, we always want to move the capital right as soon as we can. Pictorially this is because if we do the conquering first we pay prices as follows

0 -- X1 -- X2 -- X3 -- X4

-------->

-------------->

--------------------->

----------------------------->

********************

Here --> is the conquering cost between the neighboring cities and *** is the capital moving cost. However, if we move the capital as soon as we can, then we have

0 -- X1 -- X2 -- X3 -- X4

------->

******

            ----->

            ******

                     ------>

                     *******

                                ------>

So, as already established the capital moving cost is the same, however, the conquering cost is much less, since we do not repeat the costs as in the first picture. In general, if the capital ends up at $X_i$, the total price payed is therefore 

$$X_i\cdot (a+b) + b\cdot\sum_{j=i+1}^{N}{X_j-X_i}=X_i\cdot (a+b)+b\cdot(S_{N}-S_{i}-(n-i)\cdot X_i)$$

We can precompute prefix sums $S_{i}$ on $X$ in $O(N)$ so that this value is computable in $O(1)$ for any $i$.

We are missing a detail: how do we know where the capital ends up at the end of a sequence of moves which minimises the price? Well we can just try every possible $0\leq i\leq N$ and keep whichever achieves the minimum price.

String equality

Hi, today I will be presenting my thoughts on a recent codeforces problem. In this problem, we are given two strings $s$ and $t$ of length $n$. We want to make $s$ equal $t$ by performing any number of the following moves on $s$:

1. if we see 'ab' we can change it to 'ba',
2. if we see 'bc' we can change it to 'cb'.

We are asked to print YES if $s$ can be made equal to $t$, and NO otherwise. Note that $n\leq 10^5$, so we need $O(n\log{n})$ or better.

Firstly, we note that both moves leave the number of occurrences of each letter in $s$ and $t$ invariant. Thus, we count the number of occurrences of 'a', 'b', and 'c' in $s$ and $t$ and check they are equal.

Obs 1: Move $1$ moves 'b' to the left, and move $2$ moves 'b' to the right.

So moves essentially shift around the 'b' 's.

Obs 2: Let $\text{pos_s}_i$ be the position of the $i$th 'b' from the left of $s$, and let $\text{pos_t}_i$ be the position of the $i$th 'b' from the left of $t$. If $s$ is made equal to $t$, then $\text{pos_s}_i=\text{pos_t}_{i}$ for all $1\leq i\leq \text{cnt}_b$. 

Since $\text{pos_s}_i<\text{pos_s}_{i+1}$, the observation follows.

Once all 'b' 's are correctly positioned (if possible), i.e. $\text{pos_s}_{i}=\text{pos_t}_i$, then we cannot perform any more moves without moving a 'b' to the wrong position. Therefore, it only remains to check that the strings are equal, if so then we return YES, else we return NO.

This can be implemented in $O(n)$.