Score:1

ปัญหาเกี่ยวกับการลดระดับความลับของ Shamir ในประตูคูณ

ธง in

มีการอธิบายกระบวนการลดระดับการแบ่งปันความลับของ Shamir ในประตูคูณ ลิงค์ต่อไปนี้

จากข้อมูลการแบ่งปันความลับที่ทำโดยพหุนามดีกรีหนึ่ง เราต้องสามารถสร้างความลับขึ้นมาใหม่ได้ นั่นคือ $10$,กับแต่ละ $2$ หุ้นออกจาก $3$ หุ้น $(3, 7, 0)$. อย่างไรก็ตามความลับที่สร้างขึ้นใหม่โดยใช้ $(3, 7)$ ถูกต้อง $10$แต่สร้างความลับขึ้นใหม่โดยใช้ $(3,0)$ คือ 9 และใช้ $(7, 0)$ เป็น $1$. ทำไมถึงเป็นเช่นนี้? ผิดพลาดตรงไหน?

ar flag
ฉันไม่สามารถบอกได้ว่าคุณอาจทำผิดพลาดตรงไหน แต่เพื่อตรวจสอบความเป็นไปได้ที่ชัดเจนอย่างหนึ่ง คุณใช้พิกัด $x$ ที่ถูกต้องสำหรับการแชร์หรือไม่ แต่ละส่วนแบ่งในโครงการของ Shamir เป็นคู่ของตัวเลขจริงๆ $(x,y)$ โดยที่ $x$ ไม่ขึ้นอยู่กับความลับที่ใช้ร่วมกันและสามารถเปิดเผยต่อสาธารณะได้ แต่ต้องไม่ซ้ำกันและ (ในรูปแบบปกติของ Shamir's) ไม่ใช่ -ศูนย์ ในขณะที่ $y$ นั้นเป็นของปลอมและผู้ถือหุ้นต้องเก็บเป็นความลับเพื่อหลีกเลี่ยงการรั่วไหลของหุ้น
Daniel avatar
ru flag
คุณไม่ควรสร้างความลับขึ้นมาใหม่โดยใช้สองในสามส่วนร่วมกัน คุณต้องการหุ้นสามในสามหรืออีกนัยหนึ่งคือคุณต้องการหุ้นทั้งหมด นี่เป็นเพราะพหุนามที่ได้มีดีกรีเป็น $2$ ดังนั้นคุณต้องใช้สามส่วนร่วมกัน
Score:1
ธง ng

ฉันคิดว่าคุณเข้าใจผิดเกี่ยวกับการสร้างส่วนแบ่งใหม่ ส่วนแบ่ง $(ก,ข,ค)$ ในบริบทนี้เป็นสามค่าที่สอดคล้องกับการประเมินพหุนามกล่าวคือ $(\sigma(1), \sigma(2),\sigma(3))$. ปัญหาของการสร้างส่วนแบ่งใหม่คือการใช้

  1. สองค่าใด ๆ ข้างต้นของ $\sigma(i)$, และ
  2. ความรู้นั้น $\sigma(x) = \sigma(0)+ax$ เป็นพหุนามดีกรีเชิงเส้น

การกู้คืน $\sigma(0)$. สามารถทำได้ง่ายๆ บอกว่าเรามี $\sigma(i) = \sigma(0) + ai$ และ $\sigma(j) = \sigma(0) + aj$. เราสามารถลบสิ่งเหล่านี้และ "แก้" สำหรับ $a$ เพื่อให้ได้สิ่งนั้น $a = (i-j)^{-1}(\sigma(i)-\sigma(j))$, ที่ไหน $a^{-1}$ คือโมดูโลผกผัน 11 จากนั้นใช้ค่านี้ของ $a$มันง่ายที่จะกู้คืน $\sigma(0)$.

โปรดทราบว่าค่าที่คำนวณได้ของ $a$ เหมือนกันทั้ง 3 กรณี เมื่อไร $(i,j) = (1,2)$เรามีสิ่งนั้น

$$a = (1-2)^{-1}(3-7) = 4$$

เมื่อไร $(i,j) = (1,3)$ เรามีสิ่งนั้น

$$a = (1-3)^{-1}(3-0) = (-2)^{-1}3 = (-6)3\equiv -18\bmod 11 \equiv 4\bmod 11 $$

ในทำนองเดียวกัน เมื่อ $(i,j) = (2,3)$เรามีสิ่งนั้น

$$a = (2-3)^{-1}(7-0) = -7\equiv 4\bmod 11.$$

ถัดไป สำหรับดัชนีใดๆ $i$เรามีสิ่งนั้น $\sigma(0) = \sigma(i) - ai\bmod 11 \equiv \sigma(i) - 4i\bmod 11$. ง่ายต่อการตรวจสอบสำหรับคู่ใด ๆ $(i, \sigma(i))$กล่าวคือสำหรับ $(1, 3)$, $(2,7)$, หรือ $(3,0)$หนึ่งได้รับ $10\bสมัย 11$ (หรือ $-1\bสมัย 11$ ---มีค่าเท่ากัน)


จากทั้งหมดที่กล่าวมา ฉันไม่พบคำอธิบายของการลดระดับในคำตอบที่เชื่อมโยงนั้นชัดเจนเป็นการส่วนตัว ฉันได้อธิบายไปก่อนหน้านี้แล้ว ที่นี่. อย่างคร่าว ๆ หนึ่งบรรลุการลดระดับโดยการรวมกัน

  1. การดูการแก้ไข / การประเมินส่วนแบ่งเป็น "การเปลี่ยนแปลงพื้นฐาน" และ
  2. ลดจากปริญญา $2t$ พหุนามในระดับหนึ่ง $t$ พหุนามผ่านการฉายลงบนตัวแรก $t$ พิกัด (ในเกณฑ์ที่เหมาะสม)

หากคุณคุ้นเคยกับพีชคณิตเชิงเส้นมากขึ้น สิ่งนี้จะให้ภาพ "เรขาคณิต" ที่ชัดเจนของสิ่งที่เกิดขึ้น แน่นอนว่าขึ้นอยู่กับภูมิหลังของคุณ

โพสต์คำตอบ

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