Score:3

PPTs เครื่องแบบและไม่สม่ำเสมอ

ธง in

ขณะอ่านกระดาษ

ฉันสะดุดกับกรณีที่จำเป็นต้องระบุว่าผู้เขียนสันนิษฐานว่าเป็นผู้โจมตีในเครื่องแบบหรือนอกเครื่องแบบ สำหรับสิ่งที่ฉันรู้ PPT ที่ไม่สม่ำเสมอนั้นเป็นลำดับของ PPT ดังนั้น $\mathcal{A}=\{\mathcal{A}_1,\mathcal{A}_2,\dots,\mathcal{A}_n\}$และบนอินพุต $x$ ขนาด $|x| = \แลมบ์ดา$, $\mathcal{A}_\lambda$ ถูกเรียก. ทำไมรุ่นนี้ถึง "แรง" กว่าเครื่องแบบ? ไม่สามารถโจมตีโฆษณา $\คณิตศาสตร์แคล{A}$ เพียงแค่ฝังผู้โจมตีอื่น ๆ ทั้งหมดในคำอธิบายของตัวเองและเรียกผู้ที่เหมาะสม? มีปัญหาที่เรารู้วิธีแก้ไขในโมเดลที่ไม่สม่ำเสมอหรือไม่ (หากไม่ใช่ด้วยการรับประกันที่อ่อนแอกว่า) ในโมเดลที่ไม่สม่ำเสมอ

Score:1
ธง ng

พิจารณาการแจกแจงแบบเอกฐานของเครื่องจักรทัวริงทั้งหมด เช่น เครื่องจักร $M$ แสดงโดย $1^{\lambda_M}$ สำหรับจำนวนเต็มเฉพาะบางตัว $\lambda_M$. ปัญหาการหยุดชะงักนั้นไม่สามารถคำนวณได้ แม้ในการแสดง "เบาบาง" นี้ แต่ไม่สามารถคำนวณได้อย่างสม่ำเสมอ เช่นเดียวกับเครื่องจักรทัวริงแต่ละเครื่อง $M$ หยุดหรือไม่หยุด และเราสามารถ "ฮาร์ดโค้ด" ตัดสินใจสิ่งนี้ในเครื่องจักรทัวริงแต่ละเครื่อง $A_{\lambda_M}$.

หากเราสามารถ "สร้างอย่างเท่าเทียมกัน" ได้ $A_i$'s ความหมายสร้างได้อย่างมีประสิทธิภาพจากคำอธิบายเพียงอย่างเดียวของ $i$คุณจะพูดถูก ในตัวอย่างข้างต้น คุณทำไม่ได้ เพราะคุณไม่รู้ว่าเครื่องจักรทัวริงแต่ละเครื่อง $M$ หยุด

us flag
อีกวิธีหนึ่งในการดูว่าอัลกอริทึมแบบยูนิฟอร์มสามารถทำสิ่งที่อัลกอริทึมแบบยูนิฟอร์มไม่สามารถทำได้: มีอัลกอริธึมแบบยูนิฟอร์มมากมายจนนับไม่ถ้วน แต่มีอัลกอริธึมแบบยูนิฟอร์มมากมายนับไม่ถ้วน
jacobi_matrix avatar
in flag
ขอบคุณสำหรับคำตอบของคุณ ฉันสงสัยว่าเรารู้ปัญหาในทางปฏิบัติที่ง่ายขึ้นในแบบจำลองที่ไม่สม่ำเสมอหรือไม่ การพูดซ้ำ โครงร่างการเข้ารหัส/สัญญาผูกมัด/ลายเซ็น... สามารถให้ความปลอดภัยระดับหนึ่งได้อย่างไร เมื่อเราถือว่าศัตรูที่เหมือนกันแต่มีระดับความปลอดภัยที่ต่ำกว่าเมื่อเทียบกับศัตรูที่ไม่เหมือนกัน หากเราสามารถสร้างฮาร์ดโค้ดของศัตรูที่เหมือนกัน คำอธิบายของตัวเอง (และยังมีขนาดคำอธิบายพหุนาม)
Mark avatar
ng flag
@jacobi_matrix ดูส่วนที่ 4 ของ [another look at tightness 2](https://eprint.iacr.org/2016/360.pdf) สำหรับการอภิปรายเกี่ยวกับสมมติฐานความแข็งที่ไม่สม่ำเสมอ เป็นมูลค่าการกล่าวขวัญว่าแนวคิดที่ค่อนข้างเกี่ยวข้องกับการโจมตี "การประมวลผลล่วงหน้า" (ซึ่งได้รับคำแนะนำเฉพาะอินสแตนซ์) มีตัวอย่างจำนวนมากที่ช่วยได้ (และสามารถนำไปสู่การโจมตีจริง) เช่น [logjam attack]( https://en.wikipedia.org/wiki/Logjam_(computer_security)) หรือปัญหามากมายในการเข้ารหัสแบบ lattice (แม้ว่าระบบ crypto แบบ lattice ส่วนใหญ่จะสร้างอินสแตนซ์ใหม่ทุกครั้ง ซึ่งจำกัดอันตรายของ precomp
Mark avatar
ng flag
@jacobi_matrix ปัญหาคือคุณไม่สามารถสร้างฮาร์ดโค้ดของฝ่ายตรงข้ามที่เป็นรูปแบบเดียวกันลงในคำอธิบายได้ เนื่องจากการสร้าง $A_i$ ตามอำเภอใจอาจไม่สามารถคำนวณได้อย่างมีประสิทธิภาพ (หรือแม้แต่คำนวณไม่ได้เลย ตัวอย่างเช่น "ปัญหาการหยุดชะงักแบบกระจัดกระจาย" อัลกอริทึมที่ไม่สม่ำเสมอในคำตอบของฉัน) ยิ่งไปกว่านั้น คุณไม่สามารถ "เก็บ" พวกมันทั้งหมดไว้ในศัตรูในเครื่องแบบได้ เนื่องจากศัตรูในเครื่องแบบจะมีคำอธิบายที่ใหญ่เกินไป
jacobi_matrix avatar
in flag
สมบูรณ์แบบ! ส่วนที่คุณเชื่อมโยงและตัวอย่างการโจมตี logjam ทำเคล็ดลับได้จริงๆ ปัญหาคือฉันคิดว่า (ผิดอย่างเห็นได้ชัด) ว่าสตริงคำแนะนำต้องเป็นขนาดอินพุตเอง (เช่นเข้ารหัสใน unary) ขอบคุณอีกครั้ง .

โพสต์คำตอบ

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