ข้อใดเล็กที่สุด เป็นวงกลม 3 ทิศทาง โครงสร้างสอดคล้องกันของค่าสุ่มที่สามารถซ่อนไว้ที่เครื่องฝ่ายตรงข้ามได้ (เปรียบเทียบบางส่วน)

หรือทั่วไปกว่าสมาชิกแต่ละคน สามารถ เป็นส่วนหนึ่งของระนาบแบบยุคลิดแบบโลคัล 2 มิติสูงสุด 3 ระนาบโดยแต่ละมิติต่างกัน 2 มิติ

(ระนาบแต่ละอันนั้นเป็นวงกลมในสองทิศทางมุมฉากเหมือนทอรัส)

เมื่อพิจารณาจากสมาชิกเพียงรายเดียวอาจดูเหมือนเครือข่ายโหนด:
(เพียงโหนดเดียวที่แสดงย่านใกล้เคียงบางส่วนเพื่อนบ้านเหล่านั้นมีเพื่อนบ้านอีกครั้งที่ไม่แสดงที่นี่)
(ซ้าย: 1 ระนาบ ขวาตัด 2 ระนาบ)
จุดตัดของ 3 ระนาบ:

แม้ว่าจะต้องมีวิธีการที่กำหนดขึ้นเพื่อแมปพื้นที่ใกล้เคียงของโหนดกับกราฟระนาบที่ระนาบยุคลิด 2 มิติ 3 มิติเหล่านั้น (ที่มีความหนาแน่นของโหนดคงที่) เพื่อนบ้านของโหนดที่อยู่ติดกันจึงมีแนวโน้มที่จะเป็นเพื่อนบ้านเช่นกันและไม่มี $n$-การเติบโตของเพื่อนบ้านที่ต้องการเช่น พื้นที่ไฮเปอร์โบลิกสำหรับการแสดง
เริ่มต้นที่โหนดหนึ่ง $n$ และ (ส่วนใหญ่) ตามทิศทางของความก้าวหน้าจะนำไปสู่โหนดเดิมอีกครั้งหลังจาก (ในกรณีที่ดีที่สุด) $C_n$ ขั้นตอน มันจึงเป็นวัฏจักรกับความยาววัฏจักร $C_n$. ในกรณีที่ดีที่สุด ค่านี้จะเท่ากันสำหรับทุกโหนดในทุกทิศทาง แต่เพื่อให้มีความเข้มงวดน้อยลง การเปลี่ยนแปลงบางอย่างอาจเป็นไปได้เนื่องจากความยาวของวงจรนั้นใกล้เคียงกับโหนดที่อยู่ใกล้เคียง

เป้าหมาย:
ค้นหาโครงสร้างดังกล่าวซึ่งลดความยาวของวงจร $C$ (ดีที่สุด $\le 2^{50}$) และจำนวนโหนดทั้งหมด $N$ (กรณีที่ดีที่สุด $N=C^3$ หรือ $\le 2^{150}$) ในขณะที่ทำให้มันยากที่สุดเท่าที่จะเป็นไปได้ในการคำนวณความสัมพันธ์ระหว่างโหนดสุ่มสองโหนด (ดีที่สุด $\ge O(C^2)$ และ $O(\sqrt[3]{N^2})$ หรือเป็นตัวเลข $\ge 2^{100}$)

เฉพาะสำหรับวิธีการเข้ารหัส:

เท่าที่ฉันรู้ในการเข้ารหัสมีเพียงโครงสร้างที่เฉพาะทางหรือบางส่วนที่กว้างกว่าโครงสร้างดังกล่าวที่อธิบายไว้ข้างต้น
ถ้าเช่น จำนวนเพื่อนบ้านจากโหนดหนึ่งถูกกำหนดเป็นค่าคงที่ 6 เราได้โครงสร้างดังนี้:
(ซ้าย: จุดตัดของระนาบ 3 ระนาบที่โหนด/หมายเลขเดียว ขวา: ทุกโหนด/ตัวเลขมีโครงสร้างนี้ที่นี่)

สามารถทำได้ด้วยเครื่องกำเนิดไฟฟ้า 3 เครื่องและเครื่องที่เหมาะสม $\bmod P$ ตามรายการด้านล่าง
สำหรับแต่ละประเภท ฉันจะเพิ่มเหตุผลบางอย่างว่าทำไมมันไม่ทำงาน และเธรดที่เกี่ยวข้อง (ของฉัน) สำหรับรายละเอียดเพิ่มเติม

เปรียบเทียบกับวิธีการเข้ารหัสที่ทดสอบแล้ว:

1. เครื่องกำเนิดไฟฟ้าสามเครื่อง $q,r,s$ กับ $\bmod P = 2\cdot Q \cdot R \cdot S +1$ และ $q^Q \equiv r^R \equiv s^S \equiv 1 \bmod P$ $\text{ } $[1]

   • $-$ $พี$ ต้องใหญ่มากเพื่อหลีกเลี่ยงการแยกตัวประกอบ $\gg 2^{150}$
   • $-$ เมื่อรู้ขนาดรอบก็จะสามารถลดปัญหาได้ง่ายขึ้นมาก อัลกอริทึม PohligâHellman

2. เส้นโค้งวงรีพร้อมเครื่องกำเนิดไฟฟ้า 3 เครื่อง $F,G,H$ และด้วยค่านิยมนี้ $i \cdot F + j \cdot G + k \cdot H$ [1] [2]

   • $-$ ขนาดรอบสำหรับแต่ละทิศทางอยู่ในโดเมนทั้งหมด
   • $+$ ต้องการจำนวนค่อนข้างน้อยเท่านั้น
   • $-$ แต่ยังคงเป็นโดเมน/ไซเคิลของ $2^{200}$ จำเป็น (ขนาดรอบเป้าหมายเท่านั้น $2^{50}$)

3. AES หรือรหัสบล็อกที่คล้ายกัน:

   • $-$ แยกเป็นวงหลายรอบโดยไม่ทราบขนาด ทราบเพียงการแจกแจงเท่านั้น [1]
   • $-$ หนึ่งต่อทิศทาง? $\ลูกศรขวา $ โดเมนของ $2^{300}$ จำเป็นและสามารถลดเป็นปัญหามิติเดียวได้
   • $-$ เชื่อม 3 AES เข้ากับสมาชิกรายเดียวหรือไม่ $\ลูกศรขวา $ ใหญ่ $n$-neighborhood คล้ายกับการใช้ค่าสุ่ม $\ลูกศรขวา $ การแข่งขันที่สลับ AES128 (โหมด ECB) สามารถพบได้ในภายหลัง $\ประมาณ {2^{64}}$ ขั้นตอนของความก้าวหน้า [2]

4. ลำดับ 3 ทิศทาง $s_{ijk} = s_0^{\textstyle \beta^i\gamma^j\delta^k} \bmod (N=P\cdot Q)$ - แก้ยากเพราะ $\phi(น)$ ไม่ทราบ

   • สำหรับ $N=(2\cdot p +1)\cdot (2\cdot q +1)$ กับ gen. $\beta, \gamma, \delta$ รากดั้งเดิมของ $p,q$ [1]
     • $+$ $O(\sqrt[2]{C^3})$ (เท่าที่ฉันรู้)
     • $-$ แต่ถ้า $\phi(น)$ ไม่เป็นที่รู้จัก ในการเข้าถึง $100$บิตความปลอดภัย $N$ ต้องอยู่ใกล้ ๆ $2000$- ขนาดบิตและด้วยสิ่งนี้ $p, q$ และขนาดวงจรก็เพิ่มขึ้นด้วย
   • สำหรับ $N=(2\cdot p_s \cdot p_b +1)\cdot (2\cdot q_s \cdot q_b +1)$ คาดว่าจะ $\frac{(p_s-1)}{2}\cdot \frac{(q_s-1)}{2}$ กับ $\gcd(e,\phi(N)) \ne 1$ แต่ $e$ แยกตัวประกอบได้ยาก [2], $\beta,\gamma,\delta$ เกี่ยวข้องกับอำนาจของ $e$
     • $+$ $O(\sqrt[2]{C^3})$ (เท่าที่ฉันรู้) ถ้า $C$ ไม่ทราบ
     • $-$ เกือบจะทันทีหากความยาวรอบ $C$ เป็นที่รู้จัก (ซึ่งหาค่าเป้าหมายได้ง่าย) $C$ จะต้องเป็น $>2^{100}$

5. การสะท้อนทางเรขาคณิตบนสนามจำกัด (รูปสามเหลี่ยม [1],จัตุรมุข [2] - ทั้งคู่ไม่มีวิธีแก้ปัญหา) หรือสายโซ่ของการคูณเมทริกซ์โดยทั่วไป เพื่อให้ $n$- เพื่อนบ้านที่ไม่เติบโตเร็วเกินไป พวกเขาต้องไม่แปรเปลี่ยนตามลำดับการคูณ จึงสามารถลดลงเหลือ $A^iB^jC^k$ - แต่จนถึงตอนนี้ฉันไม่พบเมทริกซ์ใด ๆ ที่สร้างด้วย $i,j,j$ ยากที่จะกำหนด

   • $-$ มากเกินไป $n$-เพื่อนบ้านหรือง่ายเกินไปที่จะคำนวณดัชนี

คำถาม: สามารถทำได้ดีกว่านี้หรือไม่? ได้น้อยกว่า $N=2^{200}$ ค่าจะกระจายตาม 3 มิติโดยมีขนาดรอบน้อยกว่า $C=2^{65}$ ในขณะที่การค้นหาความสัมพันธ์ระหว่างสมาชิกสองคนใช้เวลาอย่างน้อย $2^{100}$ ขั้นตอนการคำนวณ (สำหรับกรณีส่วนใหญ่)?
สำหรับสิ่งนี้จะต้องยากกว่า $O(\sqrt{N})$ (กับ $N<2^{200}$ และ $C<2^{65}$)

หมายเหตุเพิ่มเติม:

• นอกจาก 3 ทิศทางในทิศทางไปข้างหน้าแล้วผกผันในทิศทางย้อนกลับก็ต้องมีอยู่เช่นกัน ทั้งหมดควรมีเวลาคำนวณเท่ากัน
• ในกรณีที่ดีที่สุด ค่าสุ่มที่ถูกต้องทั้งหมดสามารถสร้างโครงสร้างเดียวกันได้ แต่มีขนาดเล็ก ($<\ประมาณ 10$) ชุดของโครงสร้างที่คล้ายกันซึ่งแยกจากกัน (เช่นใน 4.) ก็เป็นไปได้เช่นกัน
• ในกรณีการใช้งาน ค่าเริ่มต้นแบบสุ่มจะถูกสร้างขึ้นและใช้จ่ายซ้ำกับเพื่อนบ้านที่ใกล้ที่สุด (หลังจากนี้เพื่อนบ้านของเพื่อนบ้านและต่อไปเรื่อยๆ)ในที่สุดพวกเขาก็ส่งผลให้ (หลังจาก (เกือบ) เวลาไม่มีที่สิ้นสุดสำหรับรุ่น) เป็นโครงสร้าง (ความลับ) ที่สอดคล้องกัน ควรจัดลำดับความสำคัญของทิศทางของความก้าวหน้าให้ยากที่สุดเท่าที่จะเป็นไปได้เพื่อให้ถึงค่าเป้าหมายที่แน่นอนเร็วขึ้น ดังนั้นการสร้างคะแนนแบบสุ่มจะไม่ได้ผล ค่าถัดไปที่สร้างขึ้นควรใกล้เคียงกับค่าที่สร้างขึ้นแล้วเสมอ นั่นหมายถึงการสร้าง $i-$ไม่จำเป็นต้องใช้ค่าถัดไป (โดยปกติจะทำกับเครื่องกำเนิดไฟฟ้า) ขั้นตอนเดียวในทิศทางเดียวก็เพียงพอแล้ว (เช่นใน AES/block-cipher)
• ไม่มีฟังก์ชั่นยืดเหมือนนับทุกเท่านั้น $n$-th สมาชิกที่ถูกต้อง (เพื่อเพิ่มความปลอดภัย (ขนาดสมาชิกที่สูงขึ้น $N$) ด้วยขนาดสมาชิกที่แท้จริงคงที่ $\frac{N}{n}$). นี้จะถูกใช้ไปแล้ว ในทางเทคนิคแล้ว เป็นไปได้ (หากมีคนต้องการจริงๆ) เพื่อสร้างวงจรเต็มรูปแบบในทิศทางเดียวบนพีซีมาตรฐานในจำนวน CPU เพียงเล็กน้อย ด้วยวิธีนี้ขนาดรอบจะต้องเล็กกว่า $2^{60}$. แต่การค้นหาความสัมพันธ์ระหว่างค่าเป้าหมายสองค่านั้นน่าจะเป็นไปไม่ได้ในอีก 50 ปีข้างหน้า การหามันสำหรับชุดค่าผสมบางชุดก็ใช้ได้ การมีไว้ก็ยังดี เท่าที่ฉันรู้เกี่ยวกับ $2^{100}$ ขั้นตอนการคำนวณเป็นขอบเขตที่เหมาะสมสำหรับสิ่งนี้
• ขั้นตอนการคำนวณหมายถึงการดำเนินการพื้นฐานใดๆ (+-*/^) ที่ใช้ค่าสองค่า $<N$
• สมาชิกของโครงสร้างเหล่านั้นสามารถเป็นอะไรก็ได้ เช่น ตัวเลข เวกเตอร์ สตริง เมทริกซ์ แม้กระทั่งภาพศิลปะ ASCII ก็ใช้ได้ จำเป็นต้องมีฟังก์ชันบางอย่างเพื่อสร้างค่าสุ่มหลอกโดยไม่ทำให้ข้อมูลที่เกี่ยวข้องกับความปลอดภัยรั่วไหล การสร้างหลายรายการไม่ควรเปิดเผยข้อมูลใด ๆ เกี่ยวกับความสัมพันธ์ระหว่างพวกเขา บางอย่างเช่น $g^r$ ด้วยเครื่องกำเนิดไฟฟ้า $g$ และ $r$ ค่าสุ่มจะไม่ทำงาน การสร้างมันไม่จำเป็นต้องเร็วขนาดนั้น $<20$วินาทีที่พีซีมาตรฐานก็เพียงพอแล้ว
• ในกรณีการใช้งานเป้าหมาย สมาชิกเหล่านี้จะทำหน้าที่เป็นเมล็ดพันธุ์สำหรับ RNG โครงสร้างของสมาชิกเหล่านั้นเป็นโครงสร้างสำหรับเมล็ดเหล่านั้นลำดับตัวเลขสุ่มที่สร้างโดย RNG เหล่านั้นจะดีกว่าลำดับอื่นๆ หากพบว่ามีเพียงรายการเดียวที่ดีมาก ควรเชื่อมต่อให้ยากที่สุดเท่าที่จะเป็นไปได้ (= คำนวณจากอีกรายการหนึ่ง)
• ศัตรูจะเท่ากับผู้ใช้ปกติ เขามีสิทธิ์เข้าถึงซอร์สโค้ด ตัวแปรรันไทม์ คีย์ ตัวแปร และอื่นๆ ทั้งหมด เป็นความยาวรอบเป้าหมาย $C$ ค่อนข้างเล็กเรายังสามารถถือว่าฝ่ายตรงข้ามรู้จัก
• เทคนิคที่ผ่านการทดสอบเพิ่มเติม: เซลลูลาร์ออโตมาตอน (ไม่มีการผกผัน), เทสเซลเลชัน (ไม่สามารถกำหนดได้หรือง่ายเกินไปที่จะแก้ปัญหา), การเข้ารหัสแบบโฮโมมอร์ฟิก (ไม่มีโอเวอร์โฟลว์/วงจร, ไม่ทำงานหากใช้พีซีฝ่ายตรงข้ามทั้งหมด)

อัปเดต: เกี่ยวข้องกับความคิดเห็นของ fgrieu:

เราต้องการกราฟที่เชื่อมต่อแบบไม่มีทิศทางของโหนด N [?โดยมีจุดยอด n เป็นพิกัดสามส่วน (พิกัดคือจำนวนเต็ม?)?]

ใช่ แต่พิกัดเหล่านั้นไม่มีจุดกำเนิดทั่วโลก หากเราต้องการค้นหาเส้นทางจาก $n_1$ ถึง $n_2$ เราเริ่มต้นที่ $n_1$ และคำนวณเป็นย่าน เหล่านั้นมีพิกัดที่เกี่ยวข้องกับ $n_1$. เช่น. $(0,1,0)$ อาจหมายถึงเราเริ่มต้นที่ $n_1$ และใช้ความก้าวหน้าสำหรับมิติที่ 2 หนึ่งครั้ง
โหนดชดเชยระหว่าง $n_1$ และ $n_2$ มีความสมมาตรและไม่แปรผันสำหรับทุกๆ $n_i$ เรากำลังเริ่มต้นจาก
เนื่องจากเป็นวัฏจักรในแต่ละมิติ การชดเชยจึงเป็นได้เท่านั้น $+/-$ ขนาดครึ่งรอบ (ในปริภูมิแบบยุคลิด) สำหรับแต่ละพิกัด
จำนวนเต็มไม่จำเป็น จำนวนจริงยังใช้งานได้เมื่อคอมพิวเตอร์ขนาดยาวสามารถประมาณค่าเหล่านี้ได้ดีพอที่จะแยกความแตกต่างระหว่างโหนดต่างๆ
ตาข่ายอยู่ที่ 3-ทอรัส ดังนั้นเราจึงสามารถตีความออฟเซ็ตเป็นความต่างของมุมได้เช่นกัน

เพื่อให้ชัดเจน การสร้างพิกัดแบบสุ่มไม่ได้ผล พวกเขาจำเป็นต้องใกล้เคียงกับที่สร้างไว้แล้วเสมอ ข้อยกเว้นเพียงอย่างเดียวคือโหนดเริ่มต้น สิ่งเหล่านั้นจะต้องสร้างขึ้นโดยการสุ่ม เมื่อพิจารณาจากโหนดเริ่มต้น 2 โหนด (และตัวแปรภายในทั้งหมด) จึงไม่ควรมีคำใบ้เกี่ยวกับทิศทางความก้าวหน้าที่ดีที่สุด

ควรมีขั้นตอนบางอย่างในการย้ายจากโหนดหนึ่งไปยังอีกโหนดหนึ่งตามขอบกราฟ ซึ่งเมื่อวนซ้ำจะนำไปสู่วัฏจักรของความยาว $C_n$ เมื่อเริ่มต้นจาก n

เริ่มต้นที่ $n$ และ (ส่วนใหญ่) ก้าวไปข้างหน้าในทิศทางเดียว (และเช่น ไม่กลับมาอีกหลายครั้ง) ที่เราจะไปถึงได้ $n$ อีกครั้งหลังจากนั้น $C_n$ ขั้นตอน สิ่งนี้จะต้องเป็นไปได้สำหรับทิศทางมุมฉากอย่างน้อย 2 ทิศทางและไม่เกิน 3 ทิศทาง (ไปข้างหน้าและข้างหลังอย่างละอย่าง)

เมื่อพิจารณาจากจุดยอดสุ่มสองจุด มันน่าจะยากที่จะหาเส้นทางระหว่างสองจุด ซึ่งต้องใช้ความพยายามในการปรับแต่ง $\Omega(\sqrt[3]{N^2})$

นอกจากนี้ยังอาจยากขึ้น แต่ฉันคิดว่าไม่สามารถทำได้ในโครงสร้างการเข้ารหัสแบบปกติที่มีพื้นที่ใกล้เคียงคงที่ โดยทั่วไปตาข่ายอาจทำได้ยากกว่า ปัญหาหลักคือการค้นหาสิ่งที่ไม่สามารถลดทอนให้เป็นปัญหาขนาดมิติเดียวได้ $C$ เนื่องจากค่าเป้าหมายน้อยเกินไปสำหรับสิ่งนั้น นั่นก็หมายความว่า $C$ เป็นที่รู้จักของฝ่ายตรงข้าม (เนื่องจากสามารถทดสอบได้อย่างรวดเร็ว)
แต่ถ้าฉันไม่ผสมสัญกรณ์ก็ควรจะเป็น $o(C^2+C)$ (สำหรับพื้นที่ใกล้เคียงที่แน่นอน การตัดกันของเส้น-ระนาบเป็นไปได้เสมอ) และ $\Omega(\sqrt{N})$ และ $\โอเมก้า(C^{1.5})$ (จำนวนก้าวเฉลี่ย) อื่น ๆ $N,C$ ต้องใหญ่เกินไป

$C_n$ จะต้องอยู่ในการปรับแต่งของ $O(\sqrt[3]{N})$ [แต่นั่นคือขอบเขตบนหรือขอบเขตล่างสำหรับ Cn?]

ทั้งคู่. ไม่เหมือนกับวิธีการแสดงโดยใช้ EC โดยที่ $N\ประมาณ C_n$ และไม่เหมือนวิธีการใช้ AES สองตัวตรงไหน $C_n$ อาจจะเป็น $1$.
อาจมีบางอย่างเช่น $O(\sqrt[3]{N}\cdot f(\log(N)))$. เป้าหมายหลักคือการได้รับ $\max(C_n) < 2^{65}$ (และ $\min(C_n) \ge 2^{50}$ (อย่างอื่นง่าย afaik)) กับ $N<2^{200}$ และหาจากการสุ่ม $n_1$ ถึง $n_2$ ควรใช้เวลา (ในกรณีส่วนใหญ่) เป็นอย่างน้อย $2^{100}$ ขั้นตอนของความก้าวหน้า (แต่เป็นไปได้ถึง $\ประมาณ 10$ ชุดย่อยก็โอเค)

ความคิดเห็นของ JAAAY ที่เกี่ยวข้อง:

พื้นที่แบบยุคลิดหรือระนาบไฮเบอร์โบลิก

กล่าวอีกนัยหนึ่งการเติบโตของพื้นที่ใกล้เคียงต้องไม่เร็วเกินไป
ด้วย (เวลาว่างมาก) เราสามารถวาดโครงสร้างย่านบนแผ่นกระดาษ (=ระนาบยุคลิด)
เราสามารถวัดระยะทาง (แบบยุคลิด) ระหว่างโหนดด้วยไม้บรรทัดของเรา ไม่ว่าเราจะวาดเพื่อนบ้านของเพื่อนบ้านกี่หลัง ระยะห่างเฉลี่ยระหว่างโหนดควรอยู่ (ประมาณ) เท่ากัน
หากเราติดขอบกระดาษสองด้านที่อยู่ตรงข้ามกัน เราสามารถจำลองคุณสมบัติของวงจรสำหรับทิศทางเดียวได้ เมื่อพิจารณาจากตัวเลือกนี้ ระยะทาง (นาที) ระหว่างสองโหนดจะเท่ากันเสมอ ไม่ว่าเราจะเริ่มวาดโครงสร้างนี้ก็ตาม (หลังจากวาดครบทั้ง 2 ทิศทางแล้ว เราต้องตัดกระดาษให้ได้ขนาดที่เหมาะสม ที่ขอบ เราวัดต่อไปที่ขอบตรงข้ามของกระดาษ)

หนึ่งโหนดสามารถอยู่บนชีตได้สูงสุด 3 แผ่นเท่านั้น หากตัวเลขหลายตัวอยู่บนกระดาษสองแผ่นที่แตกต่างกัน (2-tori) ตัวเลขทั้งหมดจะวางอยู่บนบรรทัดเดียว (1-torus) - เหมือนที่จุดตัดของ 2-tori สองแผ่น