18. Bootstrapping & CKKS
Bootstrapping Recall that BGV has a limit on the number of operations, so it cannot evaluate a circuit with a large depth. This was because of the growing noise, so we need a way to remove the noi...
Bootstrapping Recall that BGV has a limit on the number of operations, so it cannot evaluate a circuit with a large depth. This was because of the growing noise, so we need a way to remove the noi...
Homomorphisms Definition. Let $(X, \ast), (Y, \ast’)$ be sets equipped with binary operations $\ast$, $\ast’$. A map $\varphi : X \ra Y$ is said to be a homomorphism if \[\varphi(a \ast b) = \...
There are two types of MPC protocols, generic and specific. Generic protocols can compute arbitrary functions. Garbled circuits were generic protocols, since it can be used to compute any boolean c...
A simple solution for two party computation would be to use oblivious transfers as noted here. However, this method is inefficient. We will look at Yao’s protocol, presented in 1986, for secure two...
Secure Multiparty Computation (MPC) Suppose we have a function $f$ that takes $n$ inputs and produces $m$ outputs. [(y_1, \dots, y_m) = f(x_1, \dots, x_n).] $N$ parties $P_1, \dots, P_N$ are try...
The previous 3-coloring example certainly works as a zero knowledge proof, but is quite slow, and requires a lot of interaction. There are efficient protocols for interactive proofs, we will study ...
In 1980s, the notion of zero knowledge was proposed by Shafi Goldwasser, Silvio micali and Charles Rackoff. Interactive proof systems: a prover tries to convince the verifier that some stateme...
중간고사 끝난 것을 기념으로! 근데 첫 문제는 시험 전날에 공부하기 싫어서 잡았다. 30323번 BOJ 30323: Exponentiation 주어진 $\alpha = x + x^{-1}$와 $\beta$에 대하여 $x^\beta + x^{-\beta} \pmod m$을 구하면 된다. 먼 옛날 곱셈 공식의 변형 [x^2 + \frac{...
Ciphertext Indistinguishability By Shafi Goldwasser and Silvio Micali Turing Award in 2012 An adversary should not be able to… (Semantic Security) gain any partial info...
Digital Signatures Definition. A signature scheme $\mc{S} = (G, S, V)$ is a triple of efficient algorithms, where $G$ is a key generation algorithm, $S$ is a signing algorithm, and $V$ is a ver...