Stay 😎. Be 😊. Keep 📚

Binomial Theorem Given $a, b \in \mathbb{R}, n \in \mathbb{N}$, then $$ (a + b)^n = \sum_{k = 0}^{n} \binom{n}{k}a^k b^{n-k} $$ Proposition Let $p$ be prime. $\forall a, b \in \mathbb{Z}$, we have: $$ (a+b)^p \equiv a^p + b^p \mod p $$ Proof It suffices to show that $\binom{p}{k} \equiv 0 \mod p$ if $0 < k < p$. Observe: $p \mid p!, p \nmid k!, p \nmid (p-k)!$, hence $p \mid \binom{p}{k}$. $\blacksquare$ ...

The goal of this file is to help understand the GSW scheme and the implementation of GSWCiphertextin OnionPIR code. Let’s start with my understanding of GSW scheme. From TGSW to RGSW RGSW is a ring variation of GSW scheme. I do not see any formal paper defining RGSW. However, I do find this particular paper helpful: Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds. This paper defines TLWE and TGSW. ...

The following is a note for my talk during Ling’s group meeting. What is FHE? Homomorphic encryption allows some computation (addition, scalar multiplication, ct-ct multiplication) directly on ciphertexts without first having to decrypt it. Partially Homomorphic Encryption support only one of those possible operation. RSA is an example: $$ \text{Enc}(m_1) \cdot \text{Enc}(m_2) = m_1^e \cdot m_2^e = (m_1 \cdot m_2)^e = \text{Enc}(m_1 \cdot m_2) $$ FHE supports Addition AND Scalar Multiplicaiton: $$ \begin{cases} \text{Enc}(m_1) + \text{Enc}(m_2) = \text{Enc}(m_1 + m_2)\\ \text{Enc}(m) \cdot c = \text{Enc}(m \cdot c) \end{cases} $$ Fancy! And it exsists! ...

Definition Problem: Given $n$ points $P = \set{p_1, \ldots, p_n} \subset \mathbb{R}^2$, compute $\text{CH}(P) = $ smallest convex set contining $P$. Input: a list of points all the points in $P$. Output: a list of points in $P$ that belongs to this convex set in CCW, starting from the left most point. Applications Given a huge point cloud, convex hull helps find the “shape”. Bounding volume. Makes ray shooting tasks faster. ...

I know this name for a long time. But never learnt it. Now it’s time. Recap Previously, Karatsuba’s algorithm for integer multiplication. It computes the result in $O(n^{\log_2 3})$ where $n$ is the number of digits. Another recap: polynomial representation: $$ p(x) = \sum_{i = 0}^{n}p_ix^i $$ And we can represent this polynomial using an array of size $n$. Evaluations and additions of polynomials are straightforward computation. Can be done in $O(n)$ time. Naive multiplication is slow, however. It takes $O(n^2)$ time to compute all the coefficient multiplications. FFT helps us speed up this multiplication. ...

The goal is to compare three methods for supporting keyword feature in PIR: Key-value filter in ChalametPIR, Sparse PIR, and the Cuckoo hashing method. In the beginning, we don’t want to start by comparing the detailed experimental performances, but we want to list their properties. What they are good / bad at. Metrics Client storage Client computation Online communication Download size Offline communication (if any) Server storage Server computation Ability to support multiple clients Notations: $m$: the number of key-value pairs. ...

⚠️THIS NOTE IS NOT FINISHED YET TODO: stirling number definitions stirling number of the first and the second type bell number Question Can you find a closed formula for the sum of the $p$-th powers of the first $n$ positive integers? That is, we need a closed formulat for the sequence: $$ h_n=a_p n^p+a_{p-1} n^{p-1}+\cdots+a_1 n+a_0, \quad(n \geq 0) $$ Solution The method is to use difference sequences. We already know the following: ...

Example sums of cubes Solve $h_n=h_{n-1}+n^3,(n \geq 1)$ and $h_0=0$. Solution Note that this is not a homegenous recurrence relation. Unrolling gives us: $$ \begin{align*} h_{n-1} &= (n-1)^3 + h_{n-2}\\ \implies h_n &= n^3 + (n-1)^3 + h_{n-2} \end{align*} $$ And we can keep doing this. Using this as the intuition, we guess the closed form: $$ h_n = n^3 + (n-1)^3 + \ldots + 2^3 + 1 $$ To formally prove this, we can use induction! Assume it holds for some $n \geq 1$, we want to show that $h_{n+1} = h_n + (n+1)^3 = 1 + 2^3 + \ldots + (n+1)^3$. ...

Generating Functions Generating functions can be regarded as algebraic objects whose formal manipulation allows us to count the number of possibilities for a problem by means of algebra. Definition Let $h_0, h_1, h_2, h_3, \ldots$ be an infinite sequence of numbers. Its generating function is defined to be the infinite series: $$ g(x) = h_0 + h_1x + h_2x^2 + \cdots + h_nx^n + \cdots $$ Example 1 The generating function of the infinite sequence $1, 1, 1, \ldots$ is: $$ g(x) = 1 + x + x^2 + x^3 + \cdots $$ for $|x| < 1$. This generating function $g(x)$ is the sum of a geometric series with value: $$ g(x) = \frac{1}{1-x} $$ Solution ...

World Coordinates and Image coordinates Pinhole Camera Model $$ x = K \left[ \begin{array}{ll} R & t \end{array} \right] x $$ x: Image Coordinates: $(u, v, 1)$ K: Intrinsic Matrix $(3 \times 3)$ R: Rotation $(3 \times 3)$ t: Translation $(3 \times 1)$ X: World Coordinates: $(X, Y, Z, 1)$ Basically, from the right side to the leftside, it is transforming a point (1) from the world coordinates to camera coordinates, and then project the point (2) from camera coordinates down to the image plane. ...