Score:2

ระดับของพหุนามนี้มีความสำคัญต่อการบรรลุความรู้เป็นศูนย์หรือไม่? คำถาม PlonK

ธง in

ฉันกำลังอ่านกระดาษ PlonK และในรอบที่ 1 ของการเรียกร้องเพื่อให้ได้ความรู้เป็นศูนย์โดยการเพิ่มทวีคูณแบบสุ่ม (ของระดับที่หนึ่ง) ของพหุนาม $Z_H = x^n - 1$ ถึงพหุนามลับ

ที่นี่, $H$ เป็นชุดที่มี $n$-th รากของความสามัคคีและอธิบายอย่างเป็นนัยว่า $$H = \{\omega, \dots, \omega^{n-1}, \omega^n = 1\},$$ ที่ไหน $\โอเมก้า$ เป็นแบบดั้งเดิม $n$- รากแห่งความสามัคคี

ดังนั้น การตั้งค่าจะเป็นดังนี้ เรามีพหุนามลับ $s(x)$ ที่เราต้องประเมินในบางจุดแบบสุ่ม $z \in \mathbb{Z}_p$, เริ่ม $z$ และการประเมินผล $s(z)$ ทราบโดยทั่วกัน

เพื่อไม่ให้ความรู้รั่วไหล $s(z)$พวกเขากำหนด: $$s'(x) := (b_1x + b_2)Z_H(x) + s(x),$$ และพวกเขาอ้างว่าเพียงพอแล้วที่จะได้รับความรู้เป็นศูนย์ $s(z)$.

ฉันมีสองคำถาม:

  1. ทำไมหลายของ $Z_H(x)$ มีดีกรีหนึ่งและไม่มี เช่น สี่หรือ 69? ในรอบที่ 2 ของ PlonK พวกเขาใช้กลยุทธ์เดียวกัน แต่มีพหุนามดีกรีสองอีกอันหนึ่ง ทำไม
  2. ทำไมสิ่งนี้ถึงเป็นจริง? ถ้า $z \ใน H$แล้วชัดเจน $s'(x)$ นำข้อมูลเกี่ยวกับ $s(x)$, เช่น $$s'(z) = s(z).$$
Vadym Fedyukovych avatar
in flag
เกี่ยวกับความรู้เป็นศูนย์ คุณหมายถึงอัลกอริทึมจำลองหรือไม่
Bean Guy avatar
in flag
@Vadym ฉันหมายถึงการซ่อนข้อมูลตามทฤษฎี
Vadym Fedyukovych avatar
in flag
คำถามที่ 2: คุณเห็นพหุนามทั้งหมดได้รับการประเมินนอก $H$ ในขณะที่สร้างการพิสูจน์หรือไม่
Bean Guy avatar
in flag
@VadymFedyukovych ในรอบต่อไปใน PlonK พวกเขาประเมินพหุนามเช่น $s'(x)$ นอก $H$ และส่งการประเมินไปยังผู้ตรวจสอบ มิฉะนั้น การประเมิน $s'(x)$ ในองค์ประกอบของ $H$ ก็จะเปิดเผยการประเมินของ $s(x)$ ด้วย
Vadym Fedyukovych avatar
in flag
เราตกลงกันได้ไหมว่า (1) การรั่วไหลของข้อมูลเกี่ยวกับพยานนั้นจำเป็นต้องประเมิน $s'()$ ใน $H$ และ (2) สิ่งนี้เกิดขึ้นด้วยความน่าจะเป็นเล็กน้อย คุณหมายถึงอะไรกับ "อย่างอื่น"? "เล็กน้อย" ข้างต้นใช้กับลายเซ็นและโอกาสในการเดาคีย์ส่วนตัวบางส่วน
Bean Guy avatar
in flag
@VadymFedyukovych ใช่ เราเห็นด้วยอย่างยิ่ง ข้อกังวลของฉันคือสาเหตุที่ระดับของพหุนาม $b(x) = b_1x+b_2$ เป็น $1$ และไม่ใช่ ตัวอย่างเช่น $0$ หรือ $2$
Score:2
ธง kr
  1. ระดับของพหุนามที่ทำให้ไม่เห็นที่คุณคูณกับพหุนามที่หายไป $Z_H$ จะต้องได้รับการสุ่มตัวอย่างจาก $F_d[X]$ กับ $d$ มากกว่าหรือเท่ากับจำนวนการประเมินในโปรโตคอล (ช่องเปิด) การประเมินทุกครั้งให้กับผู้ตรวจสอบจะรั่วไหลของข้อมูลบางอย่างเกี่ยวกับพหุนามของคุณ ดังนั้นคุณต้องป้องกันสิ่งนั้นโดยการสุ่มพหุนามของคุณ โปรโตคอลเมียร์ มีบล็อกโพสต์ที่ดีที่อธิบายว่าทำไมคุณถึงไม่มี $d$ น้อยกว่าจำนวนการประเมิน ความเข้าใจของฉันคือสำหรับพยานคงที่ (พหุนามได้รับการแก้ไขยกเว้นปัจจัยที่ทำให้ไม่เห็น) คุณต้องการฟังก์ชัน bijective ระหว่างค่าสัมประสิทธิ์ที่ทำให้ไม่เห็นและช่องเปิด เพื่อพิสูจน์ว่า พิสูจน์ว่าหน้าที่ของคุณเป็นการคาดเดาและพูดแทรก

  2. ความน่าจะเป็นนั้น $z \ใน H$ ไม่สำคัญ แต่คุณสามารถออกแบบโปรโตคอลที่ป้องกันไม่ให้คุณมี $z \ใน H$ ฉันเชื่อ.

Bean Guy avatar
in flag
ฉันไม่รู้ว่าทำไมพวกเขาไม่พิสูจน์ว่านี่เพียงพอที่จะบรรลุความรู้เป็นศูนย์ในโปรโตคอล PlonK อย่างน้อยพวกเขาก็สามารถชี้ไปที่กระดาษที่มีแนวคิดเป็นพื้นฐาน (ฉันคิดว่าเกี่ยวข้องกับกระดาษบางชิ้นจาก Groth แต่ฉันไม่พบ)

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา