ผลิตภัณฑ์ของความลับในรูปแบบการแบ่งปันแบบหลายความลับ (หรือที่เรียกว่าแผนการแบ่งปันความลับที่อัดแน่น)

คำถามนี้เกี่ยวข้องกับแผนการแบ่งปันหลายความลับที่อธิบายไว้ในบทความต่อไปนี้:

[FY92] แมทธิว เค. แฟรงคลิน, โมติ ยุง: ความซับซ้อนในการสื่อสารของการคำนวณที่ปลอดภัย (บทคัดย่อเพิ่มเติม) สตช 2535: 699-710 (ลิงค์)

ต่อไปนี้เป็นพื้นหลังบางส่วน อย่างไรก็ตาม หากคุณคุ้นเคยกับบทความดังกล่าว คุณสามารถข้ามไปที่คำถามหลักด้านล่างได้โดยตรง (เน้นด้วยแบบอักษรส่วนหัวที่เป็นตัวหนา)

ก $(t-k+1,t+1;k,n)$-แผนการแบ่งปันหลายความลับ ตามที่กำหนดไว้ใน [FY92] อนุญาตให้ตัวแทนจำหน่ายแบ่งปันได้ $k$ ความลับระหว่าง $n$ ผู้เล่น เช่น ส่วนย่อยใดๆ ของ $t+1$ ผู้เล่นหรือมากกว่านั้นสามารถกู้คืนได้ $k$ ความลับและส่วนย่อยของผู้เล่นที่มีขนาดไม่เกิน $t-k+1$ ไม่สามารถเรียนรู้ข้อมูลใด ๆ เกี่ยวกับ $k$ ความลับ

แผนการแบ่งปันหลายความลับใน [FY92] ใช้พารามิเตอร์การตั้งค่า/ระบบต่อไปนี้:

• อนุญาต $F$ เป็นสนามที่แน่นอน
• อนุญาต $s_1,\cdots,s_n \ใน F$ เป็นความลับของเจ้ามือ
• อนุญาต $\alpha_1,\cdots,\alpha_n$ และ $e_1,\cdots,e_n$ ถูกเลือกไว้ล่วงหน้าองค์ประกอบของ $F$ ที่รู้กันทุกฝ่าย.
• อนุญาต $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$, ที่ไหน $q(x) \in_R F[x]$ กับ $deg(q(x))=(t-k)$, และ $$L_i(x)= \frac{\prod_{j\neq i}(x-e_j)}{\prod_{j\neq i}(e_i-e_j)}$$

เจ้ามือกระจายส่วนแบ่ง $p(\alpha_i)$ ชั้นบนสุด $P_i$, สำหรับ $1\leq ฉัน \leq n$. ชุดย่อยของผู้เล่นทุกขนาด $\geq t+1$สามารถรวมหุ้นเข้าด้วยกันและสร้างพหุนามขึ้นใหม่ $p(x)$แล้วคำนวณความลับ $s_i = p(e_i)$ สำหรับ $1\leq ฉัน \leq n$.

ในทางกลับกัน สำหรับเซตย่อยใดๆ ของ $t-k+1$ หุ้นมีพหุนามเดียว หุ้นเหล่านั้นและใดๆ $k$ ความลับ ดังนั้น เซตย่อยใดๆ ของ $t-k+1$ ผู้เล่นจะได้เรียนรู้ข้อมูลเกี่ยวกับ $k$ ความลับ

การคำนวณส่วนแบ่งของผลิตภัณฑ์ความลับจากส่วนแบ่งของความลับแต่ละรายการ

อนุญาต $(y_1,\cdots,y_n)$ เป็นผู้แบ่งปันความลับมากมาย $(s'_1,\cdots,s'_n)$, และ $(z_1,\cdots,z_n)$ เป็นผู้แบ่งปันความลับมากมาย $(s''_1,\cdots,s''_n)$. [FY92] อธิบายอัลกอริทึมในการคำนวณการแชร์หลายรายการ $(v_1,\cdots,v_n)$ ของผลิตภัณฑ์แห่งความลับ $(s'_1 s''_1,\cdots,s'_n s''_n)$ จากหุ้นหลายตัว $(y_1,\cdots,y_n)$ และ $(z_1,\cdots,z_n)$.

อัลกอริทึมทำงานดังนี้:

• ผู้เล่นแต่ละคน $P_i$ คำนวณ $w_i = y_i \คูณ z_i$. ส่งผลให้ทูเพิล $(w_1,\cdots,w_n)$ ที่เข้ารหัสความลับ $(s'_1 s''_1,\cdots,s'_n s''_n)$ โดยใช้ก $2t$พหุนามดีกรี
• เนื่องจากการแชร์แบบหลายความลับต้องใช้ a $t$-พหุนามดีกรี, ทูเพิล $(w_1,\cdots,w_n)$ ไม่ใช่ความลับแบบหลายส่วนที่ถูกต้อง แต่จะเรียกว่าการแชร์หลายรายการหลอกแทน
• จำเป็นต้องมีขั้นตอนการลดระดับเพื่อแปลง $(w_1,\cdots,w_n)$ หลอกมัลติแชร์เป็นหลายแชร์ที่ถูกต้อง $(v_1,\cdots,v_n)$คืออันที่ใช้ดีกรี-$t$ พหุนามของแบบฟอร์ม $p(x) = q(x) \prod_{i=1}^{k}(x-e_i) + \sum_{i=1}^{k} s_i L_i(x)$ ตามที่อธิบายไว้ข้างต้น

ขั้นตอนการลดปริญญาและประเด็นหลัก/คำถามของโพสต์นี้

[FY92] ให้สูตรต่อไปนี้สำหรับการคำนวณหลายส่วนแบ่ง $(v_1,\cdots,v_n)$ จากการหลอกหลายแชร์ $(w_1,\cdots,w_n)$. $$(w_1,\cdots,w_n) A = (v_1,\cdots,v_n)$$ ที่ไหน $$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$ และ

• $B_\เอล$ คือเมทริกซ์แวนเดอร์มอนเดซึ่ง $(i,j)$ รายการคือ $(\alpha_j - e_\ell)^{i-1}$
• $สับ_{t-k+1}$ เป็นเมทริกซ์การฉายภาพในอันแรก ${t-k+1}$ เวกเตอร์ของพื้นฐานอวกาศ
• $M_\ell$ เป็นเมทริกซ์ของใคร $(i,j)$ รายการคือ $L_\ell(\alpha_i)$ สำหรับ $i=j$และศูนย์ที่อื่น

คำถามหลักของโพสต์นี้

ผู้เขียนไม่ได้อธิบายว่าพวกเขาได้สูตรมาอย่างไร $$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$

มีคนช่วยฉันหาสูตรนั้นหรือพิสูจน์ความถูกต้องได้ไหม [ฉันไม่สงสัยเลยว่ามันถูกต้อง ฉันแค่อยากรู้ว่าผู้เขียนได้มาอย่างไร]

นี่คือแนวทางบางส่วนที่ฉันได้ลองไปแล้ว

ก่อนอื่น โปรดทราบว่าเราสามารถเขียนพหุนามที่ใช้ร่วมกันเป็นผลรวมของ $k$ เงื่อนไขดังนี้.

$$ \begin{จัดตำแหน่ง*}{2} p(x) &= q(x) \prod_{\ell=1}^{k}(x-e_\ell) + \sum_{\ell=1}^{k} s_\ell L_\ell(x ) \ &= q(x) \ \frac{1}{k} \sum_{\ell=1}^{k} \left(\prod_{\ell=1}^{k}(x-e_\ell)\ ขวา) + \sum_{\ell=1}^{k} s_\ell L_\ell(x) \ &= q(x) \ \sum_{\ell=1}^{k} \left(\frac{(x-e_\ell)}{k} L_\ell(x) \right) + \sum_{\ ell=1}^{k} s_\ell L_\ell(x) \ &= \sum_{\ell=1}^{k} \left(\frac{q(x)(x-e_\ell)}{k} +s_\ell \right) L_\ell(x) \ &= \sum_{\ell=1}^{k} q'_\ell(x) L_\ell(x) \end{จัดตำแหน่ง*} $$ ที่ไหน $q'_\ell(x)=\frac{1}{k}q(x)(x-e_\ell) +s_\ell$ คือ $(t-k+1)$พหุนามดีกรี

ตอนนี้สมมติว่าเรามีความลับสองชุด $(s'_1,\cdots,s'_n)$ และ $(s''_1,\cdots,s''_n)$ แบ่งปันผ่านพหุนาม $p_1(x)$ และ $p_2(x)$. ผลิตภัณฑ์ $P(x)=p_1(x)p_2(x)$ คือ $2t$พหุนามดีกรีซึ่งสามารถเขียนเป็นผลรวมของ $k$ ข้อกำหนดที่แสดงด้านล่าง:

$$ \begin{จัดตำแหน่ง*}{2} P(x) &= p_1(x) p_2(x) \ &= \sum_{\ell=1}^{k} q'_\ell(x) p_2(x) L_\ell(x)\ &= \sum_{\ell=1}^{k} Q_\ell(x) L_\ell(x)\ &= \sum_{\ell=1}^{k} Q'_\ell(x-e_\ell) L_\ell(x)\ \end{จัดตำแหน่ง*} $$ ที่ไหน

• $Q_\ell(x)= q'_\ell(x) \ p_2(x)$ คือ $(2t-k+1)$-ดีกรีพหุนาม เช่นนั้น $Q_\ell(e_\ell)=s_\ell$ ($s_\ell = s'_\ell s''_\ell$ เป็นผลิตภัณฑ์ของความลับที่เราต้องการคำนวณ)
• พหุนาม $Q'_\ell(x)$ ได้มาจาก $Q_\ell(x)$ ผ่านการเปลี่ยนแปลงของตัวแปร เช่นนั้น $Q'_\ell(x-e_\ell) = Q_\ell(x)$. โดยเฉพาะอย่างยิ่ง, $Q'_\ell(0) = Q_\ell(e_\ell) = s_\ell$.

อนุญาต $H_\ell=(h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0)$ หมายถึงเวกเตอร์ขนาด $n$ ซึ่งมีค่าสัมประสิทธิ์ของ $Q'_\ell$. โดยเฉพาะอย่างยิ่งเรามี $h_{0,\ell} = s_\ell$.

อนุญาต $(w_1,\cdots,w_n)$ เป็นความลับแบบหลอกหลายส่วน $(s_1,\cdots,s_n)$. จากนั้นเราก็มี $$ \begin{จัดตำแหน่ง*}{2} (w_1,\cdots,w_n) &= (P(\alpha_1),\cdots,P(\alpha_n))\ &= \sum_{\ell=1}^{k} H_\ell \ กระดิ่ง \ . ม_\เอล \end{จัดตำแหน่ง*} $$ ที่ไหน $B_\เอล$ คือเมทริกซ์ขนาดแวนเดอร์มอนด์ $n$ ของใคร $(i,j)$ รายการคือ $(\alpha_j-e_\ell)^{i-1}$, และ $M_\ell$ เป็นเมทริกซ์ขนาดกำลังสอง $n$ ของใคร $(i,j)$ รายการคือ $L_\ell(\alpha_i)$ สำหรับ $i=j$, และ $0$ ที่อื่น

ในทางกลับกันให้ $(v_1,\cdots,v_n)$ เป็นความลับหลายส่วน $(s_1,\cdots,s_n)$ และปล่อยให้ $R(x)$ เป็นระดับที่สอดคล้องกัน -$t$ พหุนาม จากนั้นเราก็มี $$ \begin{จัดตำแหน่ง*}{2} (v_1,\cdots,v_n) &= (R(\alpha_1),\cdots,R(\alpha_n))\ &= \sum_{\ell=1}^{k} H_\ell \ Chop_{t-k+1} \ . กระดิ่ง \ . ม_\เอล \end{จัดตำแหน่ง*} $$

ข้างต้นใช้ได้เพราะพหุนาม $R(x)$ ที่กำหนดไว้ด้านล่างนี้เป็นระดับ -$t$ พหุนามเช่นนั้น $R(e_\ell) = s_\ell$ สำหรับทุกอย่าง $1 \leq \ell \leq k$. $$ \begin{จัดตำแหน่ง*}{2} R(x) &= \sum_{\ell=1}^{k} Q''_\ell(x-e_\ell) L_\ell(x)\ \end{จัดตำแหน่ง*} $$ กับ $Q''_\ell(x-e_\ell)$ ก $(t-k+1)$-ดีกรีพหุนามเช่นนั้น $Q''_\ell(0)=s_\ell$ สำหรับทุกอย่าง $1 \leq \ell \leq k$.

เนื่องจาก $Q''_\ell(0)=Q'_\ell(0)=h_{0,\ell}=s_\ell$ สำหรับทุกอย่าง $1 \leq \ell \leq k$ทูเพิลต่อไปนี้เป็นชุดของสัมประสิทธิ์ที่ถูกต้องสำหรับ $Q''_\ell(x)$:

$$ \begin{จัดตำแหน่ง*}{2} นรก \ . Chop_{t-k+1} &= (h_{0,\ell},\cdots,h_{2t-k,\ell},0,\cdots,0) \ Chop_{t-k+1}\ &= (h_{0,\ell},\cdots,h_{t-k,\ell},0,\cdots,0) \end{จัดตำแหน่ง*} $$

ตอนนี้จากการแสดงออกทั้งสองของ $(w_1,\cdots,w_n)$ และ $(v_1,\cdots,v_n)$ ด้านบนเราต้องไปที่สูตร $$(w_1,\cdots,w_n) A = (v_1,\cdots,v_n)$$ กับ
$$ A = \sum_{k=1}^{\ell} B_\ell^{-1} Chop_{t-k+1} B_\ell M_\ell$$

ความคิดหรือข้อเสนอแนะ?