Score:-1

Shamir Secret Sharing และกู้คืนฟังก์ชันพหุนามจากการแชร์

ธง co

ฉันได้ทำงานส่วนแรกของโครงร่าง SSS ดังนั้นฉันจึงสามารถใช้หมายเลขลับเป็นอินพุตและสร้างฟังก์ชันพหุนามแบบสุ่มและสร้างการแชร์อย่างง่ายเป็นคู่ (xi, yi)

ภารกิจคือจะสร้างความลับขึ้นมาใหม่จากการแชร์ได้อย่างไร เราทุกคนรู้ว่าเราต้องเดาทางคณิตศาสตร์อย่างชาญฉลาดเพื่อหาค่า coeffs ตัวเลือกหรืออัลกอริทึม / วิธีการค้นหา coefs คืออะไร? ข้อดีข้อเสียของแต่ละคนคืออะไร? มันแตกต่างกันอย่างไรในเขตข้อมูล จำกัด ?

kelalaka avatar
in flag
ยินดีต้อนรับสู่ Cryptgraphy.SE SSS จะต้องทำงานในฟิลด์ที่จำกัด คุณต้องการที่จะอธิบายให้เรากู้คืนความลับที่ได้รับส่วนแบ่ง? เขียนไว้อย่างดีใน [วิกิพีเดีย](https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing#Computationally_efficient_approach) หากมีอะไรไม่ชัดเจน คุณสามารถถามได้
Macko avatar
co flag
ฉันต้องการทราบโดยเฉพาะอย่างยิ่งในวิธีการแบบคลาสสิก วิธีการหา coeffs ของพหุนามซึ่งใช้ในขณะที่สร้างหุ้นครั้งแรก ฉันรู้ว่ามีอยู่ แต่มีข้อเสียบางประการในการนำไปใช้ - ฉันหมายถึงเกาส์เซียน
poncho avatar
my flag
ทำไมคุณสนใจเกี่ยวกับค่าสัมประสิทธิ์? สิ่งเดียวที่คุณสนใจในการกู้คืนคือความลับไม่ใช่หรือ
Macko avatar
co flag
แน่นอนว่ามีมากกว่านั้น เช่น ง่ายต่อการติดตั้ง การดำเนินการที่รวดเร็ว และไม่เสี่ยงต่อการถูกโจมตี (จังหวะเวลา) ขั้นตอนต่อไปคือวิธีบรรเทาปัญหาในแนวทาง Shamir แบบคลาสสิก เช่น ผู้ให้บริการแชร์ที่ชั่วร้ายสำหรับการสร้างใหม่ (วิธีเข้ารหัสการแชร์เพื่อไม่ให้เกิดการปลอมแปลง)
kelalaka avatar
in flag
ทำไมคุณต้องโจมตีเวลา? สร้างความลับบนคอมพิวเตอร์ออฟไลน์ในเครื่องหรือไม่ มีงานวิชาการเกี่ยวกับ SSS ที่ไม่มีตัวแทนจำหน่าย [Shamir secret sharing with no dealer](https://crypto.stackexchange.com/q/84143/18298) และ [Duckduckgo](https://duckduckgo.com/?q=shamir +ความลับ+การแบ่งปัน+ไม่มี+ตัวแทนจำหน่าย&t=canonical&ia=เว็บ)
Macko avatar
co flag
ดังนั้นฉันจึงลืมพูดถึงแนวคิดหลัก: การรู้ว่า coefs นั้นสำคัญเพราะฉันต้องการสร้างส่วนแบ่งเพิ่มเติมจากการออก
kelalaka avatar
in flag
แบ่งกันคนละหุ้นกับ SSS?
Macko avatar
co flag
ถ้าฉันแบ่งแต่ละหุ้นอีกครั้งด้วย SSS และใช้หุ้นบางส่วนจากกลุ่มที่สร้างขึ้นครั้งแรกและบางหุ้นที่แบ่งแล้ว หมายความว่าฉันสามารถสร้างความลับของฉันใหม่ได้ ?
poncho avatar
my flag
หากคุณมีหุ้น $t$ (โดยที่ $t$ เป็นเกณฑ์) ก็ตรงไปตรงมาที่จะสร้างหุ้นเพิ่มโดยไม่ต้องกังวลกับการคำนวณค่าสัมประสิทธิ์ภายใน
Macko avatar
co flag
ว้าว โปรดอธิบายให้ง่ายที่สุด เพราะวิธีเดียวที่ฉันรู้คือการแก้สมการเชิงเส้น
poncho avatar
my flag
คุณทราบดีว่าตรรกะการสร้างความลับมาตรฐานใช้ชุดของส่วนแบ่ง $(x_1, y_1), (x_2, y_2), ..., (x_t, y_t)$ และส่งคืนความลับที่ใช้ร่วมกันซึ่งเป็นพหุนามที่ประเมินที่ 0. ดังนั้น เพื่อสร้างส่วนแบ่งที่ x พิกัด $x'$ เรานำหุ้นเทียม $(x_1 - x', y_1), (x_2 - x', y_2), ..., (x_t - x', y_t)$ และมอบสิ่งนั้นให้กับตรรกะการสร้างใหม่อย่างลับๆ ซึ่งให้ค่าพหุนามดั้งเดิมที่ประเมินที่ $x'$ นั่นคือ พิกัดที่สอดคล้องกัน $y'$ - ส่วนแบ่งใหม่คือ $(x', y')$ . ล้างและทำซ้ำสำหรับส่วนเพิ่มเติมทั้งหมดที่คุณต้องการ
Macko avatar
co flag
โดยทั่วไปสูตรการแก้ไขนี้ใช้งานได้ แต่ที่น่าสนใจคือถ้าฉันสร้างการแบ่งปันที่ xi อยู่ในช่วง [1..10] มากกว่าการรวมกันของสิ่งอันดับการแบ่งปันทั้งหมดฉันสามารถหาค่าลับได้ สิ่งนี้ก็เป็นจริงเช่นกันเมื่อฉันสร้างส่วนแบ่งมากขึ้น [15...20] แต่ส่วนที่น่าสนใจคือเมื่อฉันผสมคู่จาก 2 ซีรีส์นี้กว่าที่ xi ที่อยู่ห่างไกลจะให้คำตอบผิดในการแก้ไข ดังนั้นฉันจึงมีข้อบกพร่องในรหัสของฉัน (ซึ่งฉันไม่คิดอย่างนั้น) หรือ Lagrange มีข้อ จำกัด มากในการแก้ไข
Macko avatar
co flag
ดังนั้นความคิดใด ๆ ที่จะแทนที่การแก้ไข Lagrange ?
Macko avatar
co flag
@poncho การสร้างใหม่ไม่ทำงานตามที่คาดไว้: ฉันเตรียมเกณฑ์จำนวนคะแนน (หุ้น) ที่พวกเขาสร้างขึ้นเมื่อเริ่มต้น มากกว่าที่ฉันสร้างคะแนนใหม่ (xn-x' ,yn) มากกว่าที่ฉันใส่ไว้ในฟังก์ชันการแก้ไขและคำนวณที่ x '. การแชร์ใหม่มี xi ใหม่ที่ถูกต้อง แต่เอาต์พุตจากการแก้ไขให้ค่าเท่ากันทั้งหมด กรุณาระบุตัวอย่าง?
poncho avatar
my flag
@Macko: "ฉันวางไว้ในฟังก์ชันการแก้ไขและคำนวณที่ x'"; ไม่ คำนวณการประมาณค่าที่ 0 (นั่นคือ ทำอย่างแม่นยำด้วยตรรกะการสร้างความลับแบบมาตรฐาน)
Macko avatar
co flag
@poncho สุดยอด! ใช่! มันใช้งานได้อย่างมีเสน่ห์ :) และไม่มีการใช้เลขคู่ ไม่มีการแก้สมการ นี่คือสิ่งที่ฉันต้องการ :) ขอบคุณมาก ...
Score:1
ธง sd

ลองใช้รูปร่างเกณฑ์ (, ) เพื่อแชร์ค่าลับ - 1 จำนวนเต็มแบบสุ่ม 1, 2, ..., â 1 ถูกเลือกในขณะที่ 0 = ขึ้นอยู่กับสิ่งเหล่านี้เป็นปัจจัย พหุนามจะถูกสร้างขึ้น เอฟเอ็กซ์....

จากสิ่งนี้ เราได้รับคะแนนสุ่ม (, ()) ⶠâ 0 แต่ละคะแนนจะถูกสื่อสารไปยังหนึ่งในนั้น ผู้เข้าร่วม. สำหรับส่วนย่อยของจุดใดๆ สามารถสร้างพหุนามขึ้นใหม่ได้โดยใช้การแก้ไขแบบลากรองจ์ มีพหุนาม () สำหรับค่า = 0 เราจะได้ค่า (0) = 0 ที่เป็นความลับ

โปรดทราบว่าเพื่อการรักษาความลับที่เหมาะสม การดำเนินการทั้งหมดจะทำกับองค์ประกอบของเขตข้อมูลจำกัดที่มีขนาดโดยที่หมายเลขแรก ซึ่งมากกว่าค่าสัมประสิทธิ์ทั้งหมดของพหุนาม เช่นเดียวกับค่า t และ n

Macko avatar
co flag
การแก้ไข Lagrange ดีกว่าการกำจัดเกาส์เซียนในการหาค่าสัมประสิทธิ์พหุนามหรือไม่? สามารถอธิบายวิธีการแก้ไขตัวอย่างโดยใช้ Lagrange เพื่อค้นหา coefs ได้อย่างไร
Pegasus avatar
sd flag
อนุญาต เป็นพหุนามของดีกรี t: f (x) = a0 + a1x + ··· +atxt สามารถสร้างใหม่จาก t + 1 จุด (xi, f (xi)) ด้วยส่วนต่างๆ (ในลักษณะเฉพาะ) , มีพหุนามดีกรีไม่สิ้นสุดของ t ผ่านจุดดังกล่าว
Macko avatar
co flag
คุณสามารถให้ข้อจำกัดทั้งหมดเมื่อสร้างการแชร์ใหม่สำหรับความลับที่กำหนด เช่น เกณฑ์ไม่น้อยกว่า 2 ได้หรือไม่ เป็นต้น
Pegasus avatar
sd flag
สามารถเพิ่มหุ้นใหม่ได้อย่างง่ายดายโดยไม่ต้องเปลี่ยนหุ้นเก่า: คำนวณคะแนนใหม่ หมายเหตุ สามารถมีได้มากกว่า 1 หุ้น และสามารถแก้ไขพหุนามได้โดยไม่ต้องเปลี่ยนรหัสลับ

โพสต์คำตอบ

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