อนุญาต $g$ เป็นตัวสร้างม็อดกลุ่มการคูณ $p$ นายกรัฐมนตรี
สมมติว่าเรารู้ $$g^{a+km_1}\bmod p$$ $$g^{b-km_2}\bmod p$$ $$g^{a+k'm_3}\bmod p$$ $$g^{b-k'm_4}\bmod p$$ ที่ไหน $m_2m_3-m_4m_1=\phi(p)$ ที่ไหน $\phi$ คือ Totient และ $a,b,k,k'$ เป็นสิ่งเดียวที่ไม่รู้จักและทั้งหมด $a$ ผ่าน $m_4$ มีขนาด $\sqrt p$ (พวกเรารู้ $m_1$ ผ่าน $m_4$ เกิน $\mathbb Z$) เราสามารถระบุได้ $g^a$, $g^b$ ในเวลาพหุนาม?
เราได้รับอนุญาตให้ถือว่า Diffie Hellman oracle?
ข้อสังเกตอย่างหนึ่งที่ชัดเจนก็คือ ถ้าเราเรียกค่าที่เปิดเผยทั้งสี่ $C_1, C_2, C_3, C_4$ (ดังนั้น $C_1 = g^{a+km_1}$), แล้ว:
$$C_1^{-m_4} \cdot C_2^{m_3} \cdot C_3^{m_2} \cdot C_4^{-m_1} = (g^a)^{m_2-m_4} \cdot (g^b)^ {m_3-m_1}$$
สิ่งนี้สามารถใช้เพื่อแยกแยะการเดาของ $g_a, g_b$ จากค่าที่ถูกต้อง ดังนั้นหาก "ระบุได้" หมายถึง "แยกแยะได้" ก็ใช่ เราสามารถทำได้
ฉันไม่รู้ว่ามีวิธีเพิ่มการสังเกตครั้งที่สองหรือไม่ ซึ่งจะช่วยให้คุณสามารถกู้คืน $g^a, g^b$ ค่า
ผมคิดว่าไม่. หากเราสามารถขยายโครงสร้างดังกล่าวไปยังกลุ่มกล่องดำได้ ก็จะให้ $q^{1/4}$ วิธีการแก้ลอการิทึมที่ไม่ต่อเนื่องในกลุ่มนั้น โปรดทราบว่าหากขนาดจำกัด $a$, $ข$, $k$ และ $k'$ ถูกลบออก ปัญหาไม่ชัดเจน (อาจมีวิธีแก้ปัญหาหลายอย่างแม้ในกรณีที่มีข้อจำกัด ฉันไม่แน่ใจ)
โดยทั่วไป เราสามารถพิจารณาไอโซมอร์ฟิคนี้กับปัญหาพีชคณิตเชิงเส้นในเลขชี้กำลัง พวกเราเขียน $c_1=a+km_1$, $C_i=g^c_i\mod p$ และอื่น ๆ โดยการคูณเงื่อนไข $C_iC_j$ หรือเงื่อนไขยกกำลัง $C_i^d$ เราสามารถเพิ่ม $c_i+c_j$ หรือคูณเลขยกกำลังที่ไม่รู้จักด้วยค่าคงที่ $dc_i$เพื่อให้เราสามารถหา $ก^x$ ที่ไหน $x$ คือผลรวมเชิงเส้นโดยพลการของสิ่งเหล่านี้ $c_i$ (Diffie-Hellman oracle จะทำให้เราสร้างได้ $g^y$ ที่ไหน $y$ เป็นนิพจน์พหุนามตามอำเภอใจใน $c_i$). การจำกัดตัวเองให้อยู่ในชุดค่าผสมเชิงเส้นดังกล่าว (เช่นเดียวกับกรณีของกลุ่มกล่องดำ) ปัญหาจะกลายเป็นการหาชุดค่าผสมเชิงเส้นของเรา $c_i$ ซึ่งเท่ากับ $a$ หรือ $ข$.
เรามีระบบ $$\left(\matrix{1&0&m_1&0\ 0&1&0&-m_2\ 1&0&m_3&0\ 0&1&0&-m_4}\right)\left(\matrix{a\ b\ k\ k'}\right)=\left (\matrix{c_1\ c_2\c_3\c_4}\right)\pmod{\phi(p)}$$ ถ้าเราเขียน $M$ สำหรับเมทริกซ์ 4x4 และ $\mathbf c$ สำหรับเวกเตอร์ขวามือ เราอาจหวังว่าจะพบผลรวมเชิงเส้นจาก $M^{-1}\mathbf c$. แต่เราเห็นว่า $$\mathrm{det}(M)=m_1m_4-m_2m_3\equiv 0\pmod{\phi(p)}$$ เพื่อให้เมทริกซ์ของเราไม่กลับด้าน
พีชคณิตเชิงเส้นระดับมัธยมศึกษาตอนปลายบอกเราว่าเราไม่มีคำตอบหรือคำตอบมากมาย ข้อเท็จจริงที่ว่าการก่อสร้างของเรากำหนดทางออกเดียวบอกเราว่ามีทางออกมากมาย การลดแถวเล็กน้อยบอกเราว่า $m_2c_1+m_1c_2-m_3c_3-m_1c_4\equiv 0\pmod{\phi(p)}$. โดยเฉพาะอย่างยิ่งถ้าเช่น $m_1$ เป็นโคไพร์ม $\phi(p)$เราสามารถกำหนดได้ $C_4$ ที่ให้ไว้ $C_1$, $C_2$ และ $C_3$ ดังนั้นสมการที่ 4 จึงไม่มีข้อมูลเพิ่มเติม ในกรณีที่ไม่มีความเสื่อมโทรมต่อไป ตัวอย่างเช่น เราสามารถเลือกได้ตามอำเภอใจ $g^a$ แล้วหา $g^k\equiv(C_1/g^a)^{1/m_1}\pmod p$, $g^b\equiv C_2(g^k)^{m_2}\pmod p$ และ $g^{k'}\equiv(C_3/g^a)^{1/m_3}$ ที่ก่อให้เกิด $C_1$, $C_2$, $C_3$ และ $C_4$ ที่เรานำมาเสนออย่างไรก็ตาม $a$, $ข$, $k$ และ $k'$ ที่เกี่ยวข้องกับสิ่งเหล่านี้ไม่จำเป็นต้องเป็นไปตามข้อจำกัดด้านขนาด
ตอนนี้ สมมติว่าเราสามารถขยายตัวแก้ดังกล่าวไปยังกลุ่มการคูณกล่องดำ สมมติว่าเราได้รับปัญหาลอการิทึมแบบไม่ต่อเนื่องสำหรับเครื่องกำเนิด $g$ ของการสั่งซื้อ $คิว$ และองค์ประกอบ $C_1$ เป็นกลุ่มดังกล่าว เราเลือกโดยพลการ $m_1$ และโดยการนับอาร์กิวเมนต์มีความเป็นไปได้สูงที่ $c_1$ สามารถเขียนในรูป $c_1\equiv a+km_1\pmod q$ กับ $a,k\le q^{1/2}$. เขียน $d=[q^{1/2}]$. ตอนนี้เราโทรหาผู้แก้ปัญหาของเราด้วย $C_1=C_1$, $C_2=g^d/C_1$, $C_3=C_1g^{m_1}$ และ $C_4=g^d/C_3$ และ $m_1=m_2=m_3=m_4$ (สอดคล้องกับค่า $b=d-a$ และ $k'=k+1$ ซึ่งเป็นไปตามข้อจำกัดด้านขนาด) ตัวแก้ของเราจะกลับมา $g^a$ ซึ่งเราสามารถกู้คืนได้ $a$ โดยใช้วิธีการแบบบันไดเด็ก/ก้าวยักษ์ใน $O(\root 4\of q)$ ขั้นตอน ในทำนองเดียวกันเราสามารถกู้คืนได้ $g^k=(C_1/g^a)^{1/m_1}$ และ $k$ ในอีก $O(\root 4\of q)$ ขั้นตอน ทำให้เราสามารถคำนวณ $c_1$ กับ $O(\root 4\of q)$ การดำเนินการของกลุ่มซึ่งเป็นไปไม่ได้สำหรับกลุ่มกล่องดำ
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
