การให้ส่วนที่เป็นเศษส่วนอย่างต่อเนื่อง (เช่น ไม่มีเหตุผล) ของความลับแก่ใครบางคน

ในแผนการแบ่งปันความลับ เรามักจะให้ส่วนที่มีเหตุผลของความลับออกมา เช่น. อลิซได้ความลับ 4/10, บ็อบได้ 7/10, ชาร์ลีได้ 5/10, เดวิดได้ 1/10 และอื่นๆ และคุณต้องมีทั้งหมด 10/10 เพื่อปลดล็อกความลับ

คำถามของฉันคือ มีโครงการที่อนุญาตให้มีการแบ่งส่วนที่ไม่ลงตัวของหุ้นให้กับใครบางคนหรือไม่? เช่น. อลิซได้รับ $\frac{1}{\pi}$ หุ้น Bob ได้รับ $\frac{2}{e}$ หุ้น ฯลฯ ฉันรู้ว่าคุณสามารถประมาณค่าเหล่านี้ด้วยเศษส่วนที่เป็นตรรกยะเพื่อความแม่นยำตามอำเภอใจ แต่ฉันต้องการโครงร่างที่สามารถจัดสรรความลับส่วนอตรรกยะให้กับใครบางคนได้อย่างแท้จริง

ความคิดของฉันคือคำตอบอาจคล้ายกับการใช้คลิปไบนารี 50-50 เหรียญเพื่อจำลองความน่าจะเป็นตามอำเภอใจ $p$ (ชอบ $\frac{1}{\pi}$) โดยพิจารณาจากการขยายตัวแบบไบนารีของ $p$

ประการแรก การเปรียบเทียบการพลิกเหรียญของคุณพร้อมกัน

1. จริงและ
2. ไม่เกี่ยวข้องกับการเข้ารหัส

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

อนุญาต $p\in[0,1]$ ตามอำเภอใจ จากนั้นมีขั้นตอนในการสุ่มตัวอย่างจาก $\mathsf{เบิร์น}(p)$ ที่ใช้ $\leq H(p)+2$ ไบนารี coinflips ในความคาดหวัง, ที่ไหน $H(x)$ คือฟังก์ชันไบนารีเอนโทรปี

นี่มาจากการดึงดูด "Knuth-Yao Sampling" (อย่างน้อยที่สุดก็ได้รับขอบเขตของ $H(หน้า) + 2$). การติดตามกระดาษเริ่มต้นเกี่ยวกับเรื่องนี้ค่อนข้างยาก แต่ iirc อยู่ในผลงานที่รวบรวมไว้บางชิ้นของ Knuth

ส่วนที่สำคัญที่สุดของทฤษฎีบทดังกล่าวคือ ในความคาดหวัง คำแถลง. ในขณะที่ใคร ๆ ก็สามารถยกตัวอย่างก $\mathsf{เบิร์น}(p)$, หนึ่ง ไม่ได้ ตัวอย่างที่สมบูรณ์แบบจากการแจกแจงนี้ถ้ามี กรณีที่เลวร้ายที่สุด ขอบเขตบนของจำนวน coinflips ที่ใช้ เราสามารถสุ่มตัวอย่างจากการประมาณที่ดี (มีเหตุผล) อย่างมากถึง $\mathsf{เบิร์น}(p)$แต่คุณได้กล่าวว่านี่ไม่ใช่สิ่งที่คุณต้องการ

เรื่องนี้หรือไม่? คำตอบคือใช่ --- หากจำนวนของ coinflips ที่เราใช้นั้นผันแปร (โดยหลักการแล้ว) มันอาจเปิดช่องทางด้านข้างขึ้น คนที่สามารถสังเกตได้ว่ามีการใช้ coinflips จำนวนเท่าใดในการสุ่มตัวอย่าง $\mathsf{เบิร์น}(p)$ อาจเปิดเผยข้อมูลที่ไม่สำคัญเกี่ยวกับ ผลลัพธ์ ของ $\mathsf{เบิร์น}(p)$ซึ่งอาจทำลายความปลอดภัยได้ สิ่งนี้ไม่ดี และทำไมผู้คนถึงสุ่มตัวอย่างจาก (คุณภาพสูง) การประมาณ ของการแจกแจงที่ต้องการ แทนที่จะสุ่มตัวอย่างจากการแจกแจงบางส่วน

สำหรับการแบ่งปันความลับคำตอบคือไม่ เหตุผลที่ง่ายที่สุดคือเหตุผลที่ "น่าเบื่อ" แม้ว่าฉันจะคาดเดาเหตุผลที่น่าตื่นเต้นกว่านี้เล็กน้อยว่าทำไมคำตอบจึงน่าจะเป็น "ไม่" รูปแบบการแบ่งปันความลับถูกกำหนดพารามิเตอร์อย่างเป็นทางการด้วยตัวเลขสองตัว

1. $t$เกณฑ์สำหรับการสร้างหุ้นใหม่และ
2. $n$, จำนวนหุ้นทั้งหมด.

บางครั้งมีพารามิเตอร์ที่สาม (สำหรับแนวคิดบางอย่างเกี่ยวกับการแบ่งปันความลับ "โดยประมาณ") แต่ฉันจะไม่กล่าวถึงที่นี่ ก $(เ,n)$รูปแบบการแบ่งปันความลับถูกกำหนดโดยสองพารามิเตอร์ จำนวนธรรมชาติ พารามิเตอร์ $(เสื้อ, n)$. จากนั้นเศษส่วนที่จำเป็นสำหรับการสร้างใหม่ถ้า $\frac{t}{n}$ซึ่งเป็น (เล็กน้อย) เกณฑ์เชิงเหตุผล เนื่องจาก $t, n$ จะได้รับเป็นจำนวนธรรมชาติเสมอ มีอุปสรรคสำคัญในการนำแนวคิดของคุณไปใช้ มันค่อนข้างน่าเบื่อเพราะมันบอกว่าคำจำกัดความของการแบ่งปันความลับในปัจจุบันทำให้ความคิดของคุณไม่สามารถทำงานได้

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

หนึ่ง การเข้ารหัส เป็นฟังก์ชั่นฉีด $\phi : A\ถึง B$.

เราต้องการเข้ารหัสสิ่งต่าง ๆ เพื่อนำไปสู่การเข้ารหัสที่แตกต่างกัน เช่น $a\neq b\implies \phi(a)\neq\phi(b)$ซึ่งเป็นความหมายของคำว่า "injective"

อย่างไรก็ตาม

อนุญาต $X$ เป็นเซตจำกัด แล้วสำหรับชุดอื่นๆ $A$การเข้ารหัสใด ๆ $\phi : A\ถึง X$ มี $|A|\geq |X|$.

สิ่งนี้มักเรียกว่า "หลักการหลุมหลบภัย" อย่างไรก็ตาม ผลลัพธ์นี้อาจกล่าวได้ว่าถ้าเราต้องการให้การเข้ารหัสของเราอยู่ในเซตจำกัด $X$เราสามารถมี "สิ่งที่ต้องเข้ารหัส" ได้มากเท่านั้น $A$. ซึ่งหมายความว่าถ้าเราใช้จำนวนอตรรกยะด้วยเหตุผลบางประการ $\alpha$ ในการเข้ารหัสของเรา เราสามารถพิจารณาได้เฉพาะจำนวนที่แตกต่างกันเท่านั้น เมื่อมีใครกำหนดข้อจำกัดนี้ มันไม่ชัดเจนว่าสิ่งต่าง ๆ แตกต่างจากสถานการณ์มาตรฐานอย่างไร (มีจำนวนธรรมชาติหลายคู่ เช่น จำนวนตรรกยะ)

ทำไมเราถึงต้องการ $X$ จะสิ้นสุด? ด้วยเหตุผลเดียวกับที่เราไม่สามารถสุ่มตัวอย่างจาก $\mathsf{เบิร์น}(p)$. ถ้า $X$ เป็นอนันต์ แล้วความยาวของสิ่งที่เข้ารหัสแต่ละอย่าง $\varphi(x)$ จะต้องเป็นอย่างใดอย่างหนึ่ง

1. "ความยาวไม่สิ้นสุด" (เช่น ไม่สามารถใช้กับคอมพิวเตอร์จริงได้) หรือ
2. ความยาวตัวแปร.

แต่ถ้าการเข้ารหัสมีความยาวผันแปรได้ ก็จะรั่วไหลของข้อมูลเกี่ยวกับสิ่งที่ถูกเข้ารหัส ซึ่งไม่เหมาะสำหรับการเข้ารหัส