ชี้แจง
วิธีที่ฉันเข้าใจคำถามของคุณคือ:
- ผู้เข้าร่วมจะทำงานร่วมกันเป็นชุดๆ $(P_1, P_2, \ldots)$ ของ $t+1$ ผู้เข้าร่วมแต่ละคนและสร้างความลับขึ้นใหม่
- พวกเขาจะทำเช่นนี้ไปเรื่อย ๆ จนกว่าผู้เข้าร่วมทุกคนจะได้เรียนรู้ความลับ (อย่างน้อยหนึ่งครั้ง)
- คำถามคือการหาขอบเขตสำหรับจำนวนชุดเฉพาะที่ต้องการ $P_i$. ในคำพูด: "ต้องมีผู้เข้าร่วมกี่กลุ่ม (อย่างน้อยที่สุด / มากที่สุด) เพื่อให้ผู้เข้าร่วมทุกคนได้เรียนรู้ความลับ"
ขอบล่าง
จะมีทั้งหมดอย่างน้อย $\lceil\frac{n}{t+1}\rceil$ ชุดของ $t+1$ ผู้เข้าร่วมแต่ละคนสร้างความลับขึ้นใหม่ อย่างน้อยสองชุดเหล่านี้จะมีทางแยกที่ไม่ว่างเปล่า เว้นแต่ $t+1$ แบ่ง $n$ในกรณีนี้ การแยกส่วนแยกออกจากกันแบบคู่จะเป็นไปได้
ขอบเขตบน
ในทางกลับกัน ขอบเขตบนสำหรับจำนวนชุดที่แตกต่างกันของ $t+1$ ผู้เข้าร่วมแต่ละคนเพื่อให้ผู้เข้าร่วมทุกคนได้เรียนรู้ความลับอย่างน้อยหนึ่งครั้งจะได้รับจาก $n - (t + 1) + 1$.
นอกเหนือ
แน่นอนว่าหลักฐานนั้นมีประโยชน์ในการใช้งานอย่างน่าสงสัย การสร้างใหม่แบบไร้เดียงสาจะทำงานได้เฉพาะในสภาพแวดล้อมที่ไม่มีศัตรูที่แข็งขัน ซึ่งในกรณีนี้ คุณอาจมีกลุ่มแรกที่สร้างมันขึ้นมาใหม่เพื่อเผยแพร่ความลับ