Stay šŸ˜Ž. Be šŸ˜Š. Keep šŸ“š

ćŠćµć‚šŸ› => Bathe in the sea of knowledge.

Understanding SimplePIR & DoublePIR

Notations Database size: N Plaintext modulus:pāˆˆN. In SimplePIR, logā”(p)ā‰¤10. Ciphertext modulus: qāˆˆN. In SimplePIR, logā”(q)=32. LWE Dimension: n=1024 LWE secret vector: sā†’āˆˆZqn. LWE enc factor: Ī”=q/p. LWE Randomized matrix Aā†ZqmƗn, where m is the number of samples you want to encrypt. Plain message vector: Ī¼ā†’āˆˆZpm. In simplePIR, we also write Ī¼i to denote the vector with all zero entries except a single 1 at index i. ...

February 11, 2025

Commitment and Signatures

Definition Commitment Parameters ppā†Gen(1n). comā†Commit(m,r) {0,1}ā†Open(com,m,r). Binding: an adversary canā€™t open the commitment to a different message mā€². Hiding: com does not reveal any information about the message m. One naive approach is to use hash. However, hash is not hiding. Pedersen commitment Gen(1n): group G with order q and random generators g,h. Commit(m,r): pick a random rā†Zq, compute com=gmhr. Open(com,m,r): check if com=gmhr. This scheme is computationally binding: if we express h=gx for some x, then finding mā€²ā‰ m such that gmhr=gm+rx=gmā€²+rā€²x=gmā€²hrā€² is hard by discrete log assumption. ...

December 13, 2024

RSA in pure number theory

Binomial Theorem Given a,bāˆˆR,nāˆˆN, then (a+b)n=āˆ‘k=0n(nk)akbnāˆ’k Proposition Let p be prime. āˆ€a,bāˆˆZ, we have: (a+b)pā‰”ap+bpmodp Proof It suffices to show that (pk)ā‰”0modp if 0<k<p. Observe: pāˆ£p!,pāˆ¤k!,pāˆ¤(pāˆ’k)!, hence pāˆ£(pk). ā—¼ ...

October 29, 2024

Taste of Fully Homomorphic Encryption

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: Enc(m1)ā‹…Enc(m2)=m1eā‹…m2e=(m1ā‹…m2)e=Enc(m1ā‹…m2) FHE supports Addition AND Scalar Multiplicaiton: {Enc(m1)+Enc(m2)=Enc(m1+m2)Enc(m)ā‹…c=Enc(mā‹…c) Fancy! And it exsists! ...

September 18, 2024

Convex Hull in 2D

Definition Problem: Given n points P={p1,ā€¦,pn}āŠ‚R2, compute 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. ...

August 29, 2024

Fast Fourier Transform

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(nlog2ā”3) where n is the number of digits. Another recap: polynomial representation: p(x)=āˆ‘i=0npixi 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(n2) time to compute all the coefficient multiplications. FFT helps us speed up this multiplication. ...

August 29, 2024

Understanding GSW

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

August 23, 2024

Comparisons on Keyword Support Methods

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

July 3, 2024

473 NP

Previous Next     / [Downlaod] View the PDF file here. Reference UIUC CS473 Algorithms Spring 2024 taught by Prof. Michael A. Forbes ...

April 16, 2024

473 Linear Programming IV

Previous Next     / [Downlaod] View the PDF file here. Reference UIUC CS473 Algorithms Spring 2024 taught by Prof. Michael A. Forbes ...

April 9, 2024