Score:2

มีวิธีการเข้ารหัสใด ๆ หรือไม่ $f,g,h$ กับ $f(g(h(x)))=h(g(f(x)))=g(h(f(x)))$ และการหา $ x$ สำหรับ $c=f^ig^jh^k(x)$ ที่ยากกว่า $O(i+j+k)$?

ธง at

มีวิธีการเข้ารหัสใดบ้าง $f,g,h$ ซึ่งสามารถนำไปใช้ในการสั่งซื้อใด ๆ กับอินพุต $x$ โดยที่ยังคงให้ผลลัพธ์เหมือนเดิม $r$: $$f(g(h(x)))=h(g(f(x)))=ghf(x)=fhg(x)=hfg(x)=gfh(x) = r$$ เหมือนกันสำหรับฟังก์ชันผกผัน: $$f^{-1}(g^{-1}(h^{-1}(r)))=h^{-1}(g^{-1}(f^{-1}(r )))=g^{-1}(h^{-1}(f^{-1}(r))) =...= x$$ ถ้าตอนนี้ $f,g,h,$ นำไปใช้ $i,j,k$- ครั้งในการป้อนข้อมูล $x$ ค้นหา/คำนวณ $x$ สำหรับ $ค$ $$c=f^i(g^j(h^k(x)))$$ ควรจะหนักที่สุดเท่าที่จะเป็นไปได้และใช้เวลามากกว่านี้ $O(|i|+|j|+|k|)$ ขั้นตอน
คอมพิวเตอร์ $f,g,h$ และการผกผันต้องใช้เวลาใกล้เคียงกันสำหรับแต่ละอินพุต (ไม่ขึ้นกับ $i,j,k$).

นอกจากนี้ $f,g,h$ ทำให้เกิดเป็นวัฏจักรเช่น $f(f(....f(x)...)) = x$ ด้วยขนาด $F,G,H$ กับ $F\ประมาณ G \ประมาณ H \gg 1$

และสุ่ม $x$ สามารถสร้างได้โดยปราศจากความรู้เกี่ยวกับพารามิเตอร์ลับจาก $f,g,h$.


เป้าหมาย: สุ่มให้สองครั้ง $x_1,x_2$ กับ $x_2=f^ig^jh^k(x_1)$ คำนวณ/หา $i,j,k$ ควรจะยากที่สุดเท่าที่จะเป็นไปได้ในขณะที่จำนวนที่แตกต่างกัน $x$ ควรมีขนาดเล็กที่สุด
ไม่ชอบ แต่บางชุดของ $x_1,x_2$ อาจไม่มีก็ได้ $i,j,k$

kodlu avatar
sa flag
คุณจะต้องกระตุ้นและแกะซุปตัวอักษรนี้ถ้าคุณต้องการให้ทุกคนดูสิ่งนี้อย่างจริงจัง ประการแรก ทำไมคุณถึงเลือกองค์ประกอบตามลำดับที่คุณทำ มี 3! องค์ประกอบที่เป็นไปได้ และคุณเลือก 3 ในนั้น คุณสมบัติผกผันมีแรงจูงใจ / เกี่ยวข้องอย่างไร สุดท้าย คุณพูดว่า O(i+j+k) เราจะถือว่าคุณกำลังใช้ความซับซ้อนของ f และอินเวอร์ส (f) ฯลฯ เป็นค่าคงที่หรือไม่ โปรดแก้ไขคำถามโดยตรงแทนการตอบในความคิดเห็น
Score:3
ธง ru

อนุญาต $N$ เป็นผลคูณของจำนวนเฉพาะที่แข็งแกร่งขนาดใหญ่สองตัวคือ $N=pq$, $p=2r+1$, $q=2s+1$ กับ $p$, $คิว$, $r$ และ $s$ นายกรัฐมนตรีทั้งหมด เรายังกำหนดให้ต้องการตัวเลข 3 ตัวที่เป็นรากฐานดั้งเดิมสำหรับทั้งคู่ $r$ และ $s$ (ได้รับ mod รากดั้งเดิม $r$ โฆษณา $s$ เราสามารถทำได้โดยใช้ทฤษฎีบทเศษเหลือของจีน) เราจะนำสามตัวเลขนี้เป็น 3, 5 และ 7 ด้านล่าง เราสันนิษฐานว่า $N$ เป็นการยากที่จะแยกตัวประกอบและแก้โมดูโลลอการิทึมแบบไม่ต่อเนื่อง $N$ ก็ยากเช่นกัน

อนุญาต $x$ เป็นรูปสี่เหลี่ยมจัตุรัสใดๆ $\mathbb Z/N\mathbb Z$ (เช่น เลือกองค์ประกอบแบบสุ่มแล้วจัดกำลังสอง) ตอนนี้ปล่อยให้ $f(x)=x^3\mod N$, $g(x)=x^5\mod N$ และ $h(x)=x^7\mod N$. บันทึก $f(g(h(x)))=x^{105}\mod N$ และเช่นเดียวกันสำหรับการสั่งซื้ออื่นๆ มีความสัมพันธ์ที่คล้ายกันของการผกผัน (แม้ว่าการคำนวณผกผันจะยากพอๆ กับถอดรหัส RSA)

การคำนวณอย่างรวดเร็วของ $f^ig^jh^k(x)$ จะช่วยให้เราสามารถเข้ารหัส RSA ระดับยักษ์ซึ่งเชื่อว่ายากเว้นแต่เราจะรู้ปัจจัยของ $N$.

แอปพลิเคชั่นวนซ้ำในที่สุด $f$, $g$ และ $h$ สร้างวงจรความยาว $\mathrm{lcm}((r-1),(s-1))$ เว้นเสียแต่ว่า $x$ เป็นอย่างใดอย่างหนึ่ง $r$th หรือ $s$th พาวเวอร์โมดูโล $N$ (ซึ่งไม่น่าจะหายไป)

J. Doe avatar
at flag
ดูน่าสนใจ จะทำแบบทดสอบ/คิดก่อนทำเครื่องหมายเป็นคำตอบ เช่น. สิ่งที่ผกผันเป็นเอกลักษณ์หรือไม่? เช่น. สแควร์รูทของ $5 \mod 11$ อาจเป็น $4$ และ $7$ ด้วยวิธีนี้ จำนวนขั้นตอนในการคำนวณ $f,g,h$ ที่จำเป็นในการหา $i,j,k$ สำหรับ $x_1,x_2$ ที่กำหนด ไม่สามารถฉายภาพได้? $N$ ไม่จำเป็นต้องมีขนาดใหญ่มากเพื่อหลีกเลี่ยงการแยกตัวประกอบหรือไม่ เล็กกว่า mod a prime [$N = 2 pqr+1$](https://crypto.stackexchange.com/questions/70282/how-safe-is-a-prime-with-p-2-cdot-q- cdot-r-cdot-s-cdot-t1-for-discrete-lo)?
Daniel S avatar
ru flag
การผกผันจะไม่ซ้ำกันหากเรายึดติดกับเลขยกกำลังที่เป็นรากดั้งเดิมสำหรับทั้ง $r$ และ $s$ "การฉายภาพ" ควรจะเป็นไปได้ก็ต่อเมื่อรู้ลำดับของกลุ่ม ซึ่งเทียบเท่ากับการแฟคตอริ่ง $N$ และใช่ $N$ จะต้องมีขนาดใหญ่ และคุณเป็นปฏิปักษ์ไม่ควรมีความสามารถทางควอนตัม หากใช้ไพรม์แทนคอมโพสิท ก็เป็นไปได้ที่สเต็ปยักษ์เพราะทราบลำดับกลุ่ม
J. Doe avatar
at flag
ดูเหมือนว่าจะได้ผล น่าสนใจมาก ขอบคุณอีกครั้งสำหรับการตอบ ข้อเสียเพียงอย่างเดียวคือขนาดใหญ่ $N$ เท่าที่ฉันรู้อย่างน้อย 1,000 บิตจำเป็นต้องหลีกเลี่ยงการแยกตัวประกอบ ในกรณีที่ทราบการแยกตัวประกอบ การฉายภาพและขั้นตอนขนาดยักษ์เป็นไปได้ และด้วยขั้นตอน $\ ประมาณ 2^{250}$ นี้จำเป็นต้องแก้ปัญหานี้ (ค้นหา $i,j,k$ สำหรับการสุ่ม $x_1$ ถึง $x_2$) ซึ่งเป็นไปไม่ได้ การเปลี่ยนเป็นสิ่งที่สมเหตุสมผลมากขึ้น เช่น $2^{128}$ จะทำให้การแยกตัวประกอบของ $N$ เป็นจำนวนบิต $512$ เป็นไปได้อีกครั้ง สำหรับกรณีการใช้งานเป้าหมายจริง ฉันกำลังมองหาค่าที่แตกต่างกันในจำนวนที่น้อยกว่า ($

โพสต์คำตอบ

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