Share Dialog

Zama: Part 4.1, Simple Brief to TFHE - Building Blocks

ผู้อ่านควรทราบ arithmetic สำหรับการ programming ในเบื้องต้น (โดยเฉพาะการทำ modulo)

1.1 Torus and its Discretization

Torus หรือสิ่งที่นักคณิตศาสตร์เรียกมันว่าโดนัท เป็นโครงสร้างสุดอัศจรรย์ ที่มีอิทธิพลและมีประโยชน์มากๆสำหรับการศึกษาคณิตศาสตร์ โดยเฉพาะฝั่งของ Lie Group ที่มีคุณสมบัติทั้งในเชิงของเลขคณิต (arithmetic) และเชิงเรขาคณิต (geometric) รวมไว้ด้วยกัน

โดยเหตุผลหลักๆที่ทำให้ Torus ถูกเรียกว่าโดนัท เพราะว่ามีเคสเฉพาะของมันที่เราสามารถมองเป็นรูปโดนัทได้จริงๅ

โดยในฝั่ง cryptography เราจะโฟกัสบน Torus ที่เป็นวงกลม และมองคุณสมบัติเชิง arithmetic ที่ได้เป็นหลัก ซึ่งจะได้ว่า Torus ตัวนี้เป็นเซ็ต/กลุ่มของส่วนที่เป็นทศนิยมของจำนวนจริง

$\mathbb{T} = \mathbb{R} / \mathbb{Z}$

ให้ลองนึกภาพ

$\sqrt(2) = 1.4142…$

จากนั้นเมื่อเราสนใจส่วนที่เป็นทศนิยมของ sqrt 2 นั่นคือการ modulo 1 บนจำนวนจริง และจะได้ว่า

$\sqrt(2) (mod 1) = (1 + 0.4142…) (mod 1)= 0.4142…$

โดย Torus สามารถทำการบวกและคูณ scalar (ที่เป็นจำนวนเต็ม) ได้แต่จะยังไม่สามารถนิยามการคูณระหว่างสมาชิกบน Torus ตรงๆได้ ให้ลองพิจารณา 1/2 = 3/2 บน Torus แต่

$1/2 \times 1/2 = 1/4 \neq 3/4 = 3/2 \times 1/2$

ซึ่ง Torus จะมีสมมติฐาน Decisional Learning With Errors ที่ว่า “ภายใต้ตัวเลือกที่ดีมากพอ เราจะไม่สามารถจำแนกความแตกต่างระหว่างตัวอย่างที่สุ่มมา (จาก Torus) กับตัวอย่างสุ่มที่ถูก encrypted/noise added มาแล้ว” ทำให้การทำ FHE บน Torus จะมีความปลอดภัยที่ถูกการันตีมาแล้ว

ซึ่งการคำนวนบนคอมพิวเตอร์ จะต้องมีการแปลงค่าที่ continuous ให้อยู่ในรูปของ discrete และสามารถกำหนดความแม่นยำ ซึ่งสามารถทำได้ผ่านการทำ Discretization ตัว Torus ยกตัวอย่างตัว sqrt 2 บน Torus ซึ่งสามารถเขียนในรูปของฐาน 10

$\sqrt(2) (mod 1)= 0.4142… = 4 * 10^{-1} + 1 * 10^{-2} + 4 * 10^{-3} +…$

โดยหากต้องการทศนิยมเพียงทศนิยม 3 หลัก

$\sqrt(2) (mod 1) \approx 4 * 10^{-1} + 1 * 10^{-2} + 4 * 10^{-3}$

เราจะสามารถประมาณค่า ผ่าน Discretized Torus ที่ฐาน 10, ทศนิยม 3 หลักได้

$\mathbb{T}_{10^3} = { 0, \frac{1}{1000},…,\frac{1000-1}{1000} = \frac{999}{1000} }$

ซึ่งในการทำงานจริง เราจะทำงานบนฐาน 2 ที่มี bit precision 32, 64 หลัก

$\mathbb{T}_{2^\Omega} = { 0, \frac{1}{2^\Omega},…,\frac{2^\Omega-1}{2^\Omega}}, , \Omega = {32, 64}$

ดังนั้น Discretized Torus (modulo q) จะมีหน้าตา

$\mathbb{T}_{q} = \frac{1}{q} \mathbb{Z} / \mathbb{Z} = { 0, \frac{1}{q}, ... ,\frac{q-1}{q} }$

ซึ่งเป็น subset ของ Torus แต่ตอนที่ implementation elements บน Discretized Torus จะพิจารณาเซ็ตที่เป็น modulo ของจำนวนเต็ม (หากไม่เห็นภาพให้นึกถึงชั่วโมงในนาฬิกาที่มี 12 เลข พอเป็น 13:00 (บ่ายโมง) ก็จะกลับมาเป็นเลข 1 อีกครั้ง แต่บนเซ็ต modulo 12 จริงๆแล้วจะเริ่มที่ 0 แล้วจบที่ 11 ) ซึ่งคือ

$\mathbb{Z} / q \mathbb{Z} = {0, 1,..., q - 1 }$

เวลาทำงานจริง เพราะ preserve การบวกและการคูณ scalar คล้ายกับคุณสมบัติ (Discretized) Torus ที่มีอยู่แล้ว ซึ่งเป็นการคำนวนที่เกิดขึ้นบนตัวเศษของเศษส่วนบนนั้น (numerator)

1.2 Encryption and Decryption - Secured by Torus

เมื่อเราทำความเข้าใจ Torus และการทำ Discretization แล้ว ขั้นตอนถัดมาจะเข้าสู่ขั้นตอนของการทำ encryption/decryption ผ่านการใช้งาน Torus

โดย space เริ่มต้นของข้อมูล plaintext นั้นจะอยู่บน T_p (Discretized Torus, modulo p) เพื่อที่จะเตรียม encrypt ผ่านฟังก์ชั้น TLWE ไปเป็น ciphertext ที่เป็น n-dimensional tuples บน Discretized Torus, modulo q หรือบน

$\mathbb{T}_q^{n} = \underbrace{(\mathbb{T}_q, \ldots, \mathbb{T}_q)}_{n\ \text{times}}$

โดยที่

1. มี public parameter = {n, \sigma, p, q }

2. \sigma = standard deviation ของ normal distribution ที่ e (noise/error) ถูกหยิบขึ้นมาโดยที่ e < 1/|2p| (สำหรับการทำ decryption)

3. ค่า p หาร q ลงตัว (นั่นคือ set ของ plaintext เป็นซับเซ็ตของ ciphertext หรือตัวส่วน ciphertext มีความละเอียดที่มากกว่า)

4. และมี secret key/private key = s = (s_1,…,s_n) โดยที่ s_i = 0, 1

เราจะสร้างวิธี

1. Encryption

ของ plaintext \mu บน T_p (ซึ่งเป็นค่าบน T_q ด้วย จากการที่ p หาร q ลงตัว) ผ่านการนำ a_1,…,a_n ที่สุ่มมาจาก T_q มาใช้งานกับค่า b ที่ผ่านการ encrypt แล้ว ผ่านสมการ

$Encrypt_{sk}(\mu) = TLWE_s(\mu) = (a_1,…,a_n,b), \ b = \sum_{i = 1}^{n} (s_i \cdot a_i) + \mu + e$

โดยความหมายคือการ encrypt บนตัวแปร b คือการที่ private key s ทำหน้าที่สุ่มปิดค่า a_i ที่จะใช้ (เพราะค่า s_i ที่เป็น 0 จะทำให้ผลคูณ s_i, a_i หายไป) เพื่อนำไปรวมกับ plaintext (\mu) เดิมที่มี noise เข้ามา (e) ด้วย

2. Decryption

สังเกตุจากสมการด้านบนได้ว่า

$\mu + e = b - \sum_{i = 1}^{n} (s_i \cdot a_i)$

สมมติให้

$\mu = \frac{m}{p}$

ได้เพราะ \mu อยู่ใน T_p เมื่อให้สัญลักษณ์ ⌊ x ⌉ แทนการหาจำนวนเต็มที่ใกล้เคียงค่า x ที่สุด จึงได้

$\lfloor p \cdot (\mu + e) \rceil = \lfloor m + p \cdot e \rceil = m + \lfloor p \cdot e \rceil = m$

เพราะ

$p \cdot e < \frac{1}{2} \cdot \frac{p}{|p|} \Rightarrow p \cdot e < \frac{1}{2} , , , p \cdot e > - \frac{1}{2}$

ดังนั้นเราจะได้วิธีการ decrypt ผ่านสมการ

$Decrypt_{sk}(c) = \frac{\lfloor p \cdot (b - \sum_{i = 1}^{n} (s_i \cdot a_i)) \rceil \text{ mod p}}{p}$

1.3 Examples

จากตัวอย่างดังกล่าว เราจะมี plaintext ในรูปแบบ

$\mathbb{T}_4 = { 0, \frac{1}{4}, \frac{2}{4}, \frac{3}{4} }$

เป็นวงด้านใน และ ciphertext ในรูปแบบ

$\mathbb{T}_{64} = { 0, \frac{1}{64}, \frac{2}{64}, \frac{3}{64},..., \frac{63}{64}}$

ซึ่งเป็นวงด้านนอก/ละเอียดกว่า ทำให้ plaintext จะสามารถเขียนได้ในรูปแบบ

${ 0, \frac{1}{4}, \frac{2}{4}, \frac{3}{4} } ={ 0, \frac{16}{64}, \frac{32}{64}, \frac{48}{64} }$

โดยที่ noise จะมีค่าได้ตั้งแต่

$e < \frac{1}{|2p|} = \frac{8}{64} \Rightarrow e = -\frac{7}{64},...,\frac{7}{64}$

จะทำให้เมื่อนำ plaintext ไปบวกกับค่า noise แล้วจะไม่ตกช่องสีดำที่ไม่สามารถ decrypt ค่าได้

สมมติค่า private key = 0, plaintext = 1/4, error = 3/64 ทำให้เมื่อทำการ encrypt ตัว plaintext จะได้ค่า b จะเป็น plaintext + error = 19/64 และเมื่อจะดำเนินการ decrypt ค่ากลับ ทำให้สามารถดำเนินการที่ค่า b ได้เลย และจะได้ ⌊4 * (19/64)⌉ mod 4 / 4 = ⌊19/16⌉ mod 4 / 4 = 1/4 ค่าเดิมกลับมา

ท่านผู้อ่านสามารถติดตามได้ในเร็วๆนี้

ผู้อ่านควรทราบ arithmetic สำหรับการ programming ในเบื้องต้น (โดยเฉพาะการทำ modulo)

1.1 Torus and its Discretization

Torus หรือสิ่งที่นักคณิตศาสตร์เรียกมันว่าโดนัท เป็นโครงสร้างสุดอัศจรรย์ ที่มีอิทธิพลและมีประโยชน์มากๆสำหรับการศึกษาคณิตศาสตร์ โดยเฉพาะฝั่งของ Lie Group ที่มีคุณสมบัติทั้งในเชิงของเลขคณิต (arithmetic) และเชิงเรขาคณิต (geometric) รวมไว้ด้วยกัน

โดยเหตุผลหลักๆที่ทำให้ Torus ถูกเรียกว่าโดนัท เพราะว่ามีเคสเฉพาะของมันที่เราสามารถมองเป็นรูปโดนัทได้จริงๅ

โดยในฝั่ง cryptography เราจะโฟกัสบน Torus ที่เป็นวงกลม และมองคุณสมบัติเชิง arithmetic ที่ได้เป็นหลัก ซึ่งจะได้ว่า Torus ตัวนี้เป็นเซ็ต/กลุ่มของส่วนที่เป็นทศนิยมของจำนวนจริง

$\mathbb{T} = \mathbb{R} / \mathbb{Z}$

ให้ลองนึกภาพ

$\sqrt(2) = 1.4142…$

จากนั้นเมื่อเราสนใจส่วนที่เป็นทศนิยมของ sqrt 2 นั่นคือการ modulo 1 บนจำนวนจริง และจะได้ว่า

$\sqrt(2) (mod 1) = (1 + 0.4142…) (mod 1)= 0.4142…$

โดย Torus สามารถทำการบวกและคูณ scalar (ที่เป็นจำนวนเต็ม) ได้แต่จะยังไม่สามารถนิยามการคูณระหว่างสมาชิกบน Torus ตรงๆได้ ให้ลองพิจารณา 1/2 = 3/2 บน Torus แต่

$1/2 \times 1/2 = 1/4 \neq 3/4 = 3/2 \times 1/2$

ซึ่ง Torus จะมีสมมติฐาน Decisional Learning With Errors ที่ว่า “ภายใต้ตัวเลือกที่ดีมากพอ เราจะไม่สามารถจำแนกความแตกต่างระหว่างตัวอย่างที่สุ่มมา (จาก Torus) กับตัวอย่างสุ่มที่ถูก encrypted/noise added มาแล้ว” ทำให้การทำ FHE บน Torus จะมีความปลอดภัยที่ถูกการันตีมาแล้ว

ซึ่งการคำนวนบนคอมพิวเตอร์ จะต้องมีการแปลงค่าที่ continuous ให้อยู่ในรูปของ discrete และสามารถกำหนดความแม่นยำ ซึ่งสามารถทำได้ผ่านการทำ Discretization ตัว Torus ยกตัวอย่างตัว sqrt 2 บน Torus ซึ่งสามารถเขียนในรูปของฐาน 10

$\sqrt(2) (mod 1)= 0.4142… = 4 * 10^{-1} + 1 * 10^{-2} + 4 * 10^{-3} +…$

โดยหากต้องการทศนิยมเพียงทศนิยม 3 หลัก

$\sqrt(2) (mod 1) \approx 4 * 10^{-1} + 1 * 10^{-2} + 4 * 10^{-3}$

เราจะสามารถประมาณค่า ผ่าน Discretized Torus ที่ฐาน 10, ทศนิยม 3 หลักได้

$\mathbb{T}_{10^3} = { 0, \frac{1}{1000},…,\frac{1000-1}{1000} = \frac{999}{1000} }$

ซึ่งในการทำงานจริง เราจะทำงานบนฐาน 2 ที่มี bit precision 32, 64 หลัก

$\mathbb{T}_{2^\Omega} = { 0, \frac{1}{2^\Omega},…,\frac{2^\Omega-1}{2^\Omega}}, , \Omega = {32, 64}$

ดังนั้น Discretized Torus (modulo q) จะมีหน้าตา

$\mathbb{T}_{q} = \frac{1}{q} \mathbb{Z} / \mathbb{Z} = { 0, \frac{1}{q}, ... ,\frac{q-1}{q} }$

ซึ่งเป็น subset ของ Torus แต่ตอนที่ implementation elements บน Discretized Torus จะพิจารณาเซ็ตที่เป็น modulo ของจำนวนเต็ม (หากไม่เห็นภาพให้นึกถึงชั่วโมงในนาฬิกาที่มี 12 เลข พอเป็น 13:00 (บ่ายโมง) ก็จะกลับมาเป็นเลข 1 อีกครั้ง แต่บนเซ็ต modulo 12 จริงๆแล้วจะเริ่มที่ 0 แล้วจบที่ 11 ) ซึ่งคือ

$\mathbb{Z} / q \mathbb{Z} = {0, 1,..., q - 1 }$

เวลาทำงานจริง เพราะ preserve การบวกและการคูณ scalar คล้ายกับคุณสมบัติ (Discretized) Torus ที่มีอยู่แล้ว ซึ่งเป็นการคำนวนที่เกิดขึ้นบนตัวเศษของเศษส่วนบนนั้น (numerator)

1.2 Encryption and Decryption - Secured by Torus

เมื่อเราทำความเข้าใจ Torus และการทำ Discretization แล้ว ขั้นตอนถัดมาจะเข้าสู่ขั้นตอนของการทำ encryption/decryption ผ่านการใช้งาน Torus

โดย space เริ่มต้นของข้อมูล plaintext นั้นจะอยู่บน T_p (Discretized Torus, modulo p) เพื่อที่จะเตรียม encrypt ผ่านฟังก์ชั้น TLWE ไปเป็น ciphertext ที่เป็น n-dimensional tuples บน Discretized Torus, modulo q หรือบน

$\mathbb{T}_q^{n} = \underbrace{(\mathbb{T}_q, \ldots, \mathbb{T}_q)}_{n\ \text{times}}$

โดยที่

1. มี public parameter = {n, \sigma, p, q }

2. \sigma = standard deviation ของ normal distribution ที่ e (noise/error) ถูกหยิบขึ้นมาโดยที่ e < 1/|2p| (สำหรับการทำ decryption)

3. ค่า p หาร q ลงตัว (นั่นคือ set ของ plaintext เป็นซับเซ็ตของ ciphertext หรือตัวส่วน ciphertext มีความละเอียดที่มากกว่า)

4. และมี secret key/private key = s = (s_1,…,s_n) โดยที่ s_i = 0, 1

เราจะสร้างวิธี

1. Encryption

ของ plaintext \mu บน T_p (ซึ่งเป็นค่าบน T_q ด้วย จากการที่ p หาร q ลงตัว) ผ่านการนำ a_1,…,a_n ที่สุ่มมาจาก T_q มาใช้งานกับค่า b ที่ผ่านการ encrypt แล้ว ผ่านสมการ

$Encrypt_{sk}(\mu) = TLWE_s(\mu) = (a_1,…,a_n,b), \ b = \sum_{i = 1}^{n} (s_i \cdot a_i) + \mu + e$

โดยความหมายคือการ encrypt บนตัวแปร b คือการที่ private key s ทำหน้าที่สุ่มปิดค่า a_i ที่จะใช้ (เพราะค่า s_i ที่เป็น 0 จะทำให้ผลคูณ s_i, a_i หายไป) เพื่อนำไปรวมกับ plaintext (\mu) เดิมที่มี noise เข้ามา (e) ด้วย

2. Decryption

สังเกตุจากสมการด้านบนได้ว่า

$\mu + e = b - \sum_{i = 1}^{n} (s_i \cdot a_i)$

สมมติให้

$\mu = \frac{m}{p}$

ได้เพราะ \mu อยู่ใน T_p เมื่อให้สัญลักษณ์ ⌊ x ⌉ แทนการหาจำนวนเต็มที่ใกล้เคียงค่า x ที่สุด จึงได้

$\lfloor p \cdot (\mu + e) \rceil = \lfloor m + p \cdot e \rceil = m + \lfloor p \cdot e \rceil = m$

เพราะ

$p \cdot e < \frac{1}{2} \cdot \frac{p}{|p|} \Rightarrow p \cdot e < \frac{1}{2} , , , p \cdot e > - \frac{1}{2}$

ดังนั้นเราจะได้วิธีการ decrypt ผ่านสมการ

$Decrypt_{sk}(c) = \frac{\lfloor p \cdot (b - \sum_{i = 1}^{n} (s_i \cdot a_i)) \rceil \text{ mod p}}{p}$

1.3 Examples

จากตัวอย่างดังกล่าว เราจะมี plaintext ในรูปแบบ

$\mathbb{T}_4 = { 0, \frac{1}{4}, \frac{2}{4}, \frac{3}{4} }$

เป็นวงด้านใน และ ciphertext ในรูปแบบ

$\mathbb{T}_{64} = { 0, \frac{1}{64}, \frac{2}{64}, \frac{3}{64},..., \frac{63}{64}}$

ซึ่งเป็นวงด้านนอก/ละเอียดกว่า ทำให้ plaintext จะสามารถเขียนได้ในรูปแบบ

${ 0, \frac{1}{4}, \frac{2}{4}, \frac{3}{4} } ={ 0, \frac{16}{64}, \frac{32}{64}, \frac{48}{64} }$

โดยที่ noise จะมีค่าได้ตั้งแต่

$e < \frac{1}{|2p|} = \frac{8}{64} \Rightarrow e = -\frac{7}{64},...,\frac{7}{64}$

จะทำให้เมื่อนำ plaintext ไปบวกกับค่า noise แล้วจะไม่ตกช่องสีดำที่ไม่สามารถ decrypt ค่าได้

สมมติค่า private key = 0, plaintext = 1/4, error = 3/64 ทำให้เมื่อทำการ encrypt ตัว plaintext จะได้ค่า b จะเป็น plaintext + error = 19/64 และเมื่อจะดำเนินการ decrypt ค่ากลับ ทำให้สามารถดำเนินการที่ค่า b ได้เลย และจะได้ ⌊4 * (19/64)⌉ mod 4 / 4 = ⌊19/16⌉ mod 4 / 4 = 1/4 ค่าเดิมกลับมา

ท่านผู้อ่านสามารถติดตามได้ในเร็วๆนี้

<100 subscribers

<100 subscribers