Cryptography

Basics RLWE ciphertext $$ \begin{align*} (a, b) &= (a, -as + \Delta m + e)\\ R_q &= \mathbb{Z}_q[x]/(x^d + 1)\\ \Delta &= \lfloor q/p\rfloor \end{align*} $$Key-switching $$ \begin{align*} \mathsf{KS.setup}(s,s')&=[w, -s' \cdot w + s \cdot g_z + e] \to K\\ \mathsf{KS.switch}(K, (a, b)) &= (0, b) + g_z^{-1}(a) \cdot k\\ &= (0, b) + g_z^{-1}(a) \cdot [w, -s' \cdot w + s \cdot g_z + e]\\ &= (g_z^{-1}(a) \cdot w, -g_z^{-1}(a) \cdot w \cdot s'+ g_z^{-1}(a) \cdot s \cdot g_z+g_z^{-1}(a) \cdot e)\\ &=(a', -s'a' + s \cdot g_z^{-1}(a)g_z + e')\\ &=(a', -s'a' + sa + e') + (0, -as + m + e)\\ &=(a', -s'a' + m + e'') \end{align*} $$$K\in R_q^{\ell \times 2}$ is two columns of polys. This is pretty large. Say $q$ is stored in uint64_t, $d = 2048$, then each polynomial in $R_q$ is 16KB. We can use pseudorandom $w$ to save some time, but still quite large. ...

Notations Database size: $N$ Plaintext modulus:$p \in \mathbb{N}$. In SimplePIR, $\log(p) \leq 10$. Ciphertext modulus: $q \in \mathbb{N}$. In SimplePIR, $\log(q) = 32$. LWE Dimension: $n = 1024$ LWE secret vector: $\vec{s} \in \mathbb{Z}_q^{n}$. LWE enc factor: $\Delta = q / p$. LWE Randomized matrix $A \gets \mathbb{Z}_q^{m \times n}$, where $m$ is the number of samples you want to encrypt. Plain message vector: $\vec{\mu} \in \mathbb{Z}_p^m$. In simplePIR, we also write $\mu_i$ to denote the vector with all zero entries except a single $1$ at index $i$. ...

Definition Commitment Parameters $\mathsf{pp} \gets \mathsf{Gen}(1^n)$. $\mathsf{com} \gets \mathsf{Commit}(m, r)$ $\set{0, 1} \gets \mathsf{Open}(\mathsf{com}, m, r)$. Binding: an adversary can’t open the commitment to a different message $m'$. Hiding: $\mathsf{com}$ does not reveal any information about the message $m$. One naive approach is to use hash. However, hash is not hiding. Pedersen commitment $\mathsf{Gen}(1^n)$: group $\mathbb{G}$ with order $q$ and random generators $g, h$. $\mathsf{Commit}(m, r)$: pick a random $r \gets \mathbb{Z}_q$, compute $\mathsf{com} = g^mh^r$. $\mathsf{Open}(\mathsf{com}, m, r)$: check if $\mathsf{com} = g^mh^r$. This scheme is computationally binding: if we express $h = g^x$ for some $x$, then finding $m' \neq m$ such that $g^mh^r = g^{m+rx} = g^{m' + r'x} = g^{m'}h^{r'}$ is hard by discrete log assumption. ...

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 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: ...

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 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. ...