บิตความปลอดภัยสัมพัทธ์ของฟังก์ชันที่ช้ากว่า

ทิ้งข้อสมมติฐานความแข็งของหน่วยความจำไว้ ฟังก์ชันแฮชที่ช้าบางฟังก์ชันจะทำซ้ำเวอร์ชันแฮชแบบเค็มของแฮชการเข้ารหัสแบบปกติ ซึ่งมักจะถูกกำหนดโดย กลม พารามิเตอร์ เช่น ใน PBKDF2 มีเอกสารการเข้ารหัสใด ๆ ที่ระบุถึงคำจำกัดความของบิตความปลอดภัยตามปัจจัยของ รอบ ของการร้องขอที่ต่อเนื่องกันเชิงเส้น (ไม่ใช่แบบขนาน) สำหรับการคำนวณเอาต์พุตหนึ่งรายการ?

เช่น ตัวอย่างที่เป็นรูปธรรม: กำลังทำลายภาพพรีอิมเมจของ sha3(fresh_salt, input_value) ง่ายกว่า sha3(sha3(sha3(sha3(fresh_salt, input_value)))) สำหรับค่าเอนโทรปีต่ำ input_value (เช่น 64 บิต) และถ้าใช่ หลังเสนอความปลอดภัยพิเศษ 2 บิตหรือไม่เนื่องจากผู้โจมตีต้องการความพยายามสัมพัทธ์มากกว่า 4 เท่า? เอกสารการวิจัยใด ๆ ที่กล่าวถึงสิ่งนั้น (ความพยายามของฝ่ายตรงข้ามที่จำเป็นระหว่างฟังก์ชันอิสระหรือฟังก์ชันที่ขึ้นอยู่กับเชิงเส้นเทียบกับบิตความปลอดภัยที่เสนอในทางปฏิบัติ)

• คำถามนี้คล้ายกับ ผลกระทบด้านความปลอดภัยของแฮชที่ออกแบบช้าต่อความปลอดภัยเทียบกับขนาดแฮชแต่ฉันสนใจคำตอบที่เกี่ยวข้องกับการพิสูจน์ความปลอดภัยเป็นส่วนใหญ่

มีแนวคิดที่ละเอียดอ่อนเกี่ยวกับความหมายของโปรโตคอลที่จะมี $\แลมบ์ดา$-บิตของการรักษาความปลอดภัย คนที่รู้จักกันดีที่สุดน่าจะเป็น Micciancio-Walter เกี่ยวกับความปลอดภัยของ Bit ของ Cryptographic Primitives.

แนวคิดเรื่องความปลอดภัยบิตนั้นแตกต่างกันไม่ว่าจะทำงานกับ a

• เกมตัดสินว่ามันอยู่ที่ไหน $\min_A\log_2 \frac{T(A)}{(\mathsf{adv}^A)^2}$เช่น เครื่องชั่ง กำลังสอง ด้วยความได้เปรียบของปรปักษ์หรือ

• เกมค้นหาว่ามันอยู่ที่ไหน $\min_A \log_2 \frac{T(A)}{\mathsf{adv}^A}$เช่น เครื่องชั่ง เชิงเส้น ด้วยความได้เปรียบเสียเปรียบ

เดอะ $\min_A$ กำลังลดจำนวนศัตรูทั้งหมดที่โจมตีแบบดั้งเดิมและ $ที(เอ)$ คือเวลาทำงานของ $A$. โปรดทราบว่าความได้เปรียบสำหรับเกมค้นหา/เกมตัดสินถูกกำหนดแตกต่างกัน (สำหรับเกมค้นหา มันคือความน่าจะเป็นที่จะสำเร็จโดยคร่าว สำหรับเกมตัดสินใจ มันคือ $2\เดลต้า-1$, ที่ไหน $\เดลต้า$ คือความน่าจะเป็นที่สำเร็จ)

อย่างไรก็ตาม ในกรอบนี้ คุณสามารถลองพิสูจน์บางอย่างเช่น

ถ้า $H(\cdot)$ เป็นฟังก์ชันแฮชนั่นคือ $\กัปปะ$ทนภาพพรีบิตแล้ว $H^{\circ k}(\cdot)$, $k$พับองค์ประกอบของ $H$, เป็น $(\log_2(k) + \kappa)$ทนบิตภาพล่วงหน้า

หลักฐานคร่าว ๆ ดังนี้

1. เริ่มกับ $\min_A \log_2 \frac{T(A)}{\mathsf{adv}_H^A}\geq \kappa$, ที่ไหน $\mathsf{adv}^A_H$ เป็นข้อดีของ $A$ ในเกมกำหนดความต้านทานภาพล่วงหน้า

2. สร้างขอบเขตความได้เปรียบบางอย่าง $\mathsf{adv}_{H^{\circ k}}^A \leq \mathsf{adv}_H^A$ติดตามเวลาทำงานของศัตรูใหม่ $B$ หนึ่ง (โดยปริยาย) สร้างเป็นส่วนหนึ่งของสิ่งนี้เพื่อความง่าย สมมติว่า $\mathsf{adv}_{H^{\circ k}}^B \leq \mathsf{adv}_H^A$, และ $T(B) = กิโลตัน(A)$ --- ฉันไม่ชัดเจนสำหรับฉันว่านี่เป็นความจริง แต่ฉันคิดว่าข้อสันนิษฐานนี้มีนัยในคำถามของคุณ

3. จากนั้นเรามีสิ่งนั้น $\min_B \frac{T(B)}{\mathsf{adv}_{H^{\circ k}}^B} \geq \min_A\frac{kT(A)}{\mathsf{adv}_{ H}^A} = \log_2 k + \kappa$.

ตามที่ #2 ข้างต้นชี้ให้เห็น สิ่งนี้ช่วยลดการแสดงข้อได้เปรียบ (แบบดั้งเดิม) ขอบเขตของแบบฟอร์ม

สำหรับศัตรูใด ๆ $B$ ต่อต้าน $SHA3^{\circ k}$มีศัตรู $A$ ต่อต้าน $SHA3$ กับ

• $T(B) = กิโลตัน(A)$, และ
• $\mathsf{adv}^B_{SHA3^{\circ k}} \leq \mathsf{adv}^A_{SHA3}$.

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

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

สิ่งแรกเกี่ยวกับความปลอดภัย เมื่อเราบอกว่ามีรูปแบบการเข้ารหัส $λ$ บิตของความปลอดภัย สิ่งที่เรามักหมายถึงคือวิธีเดียวที่จะทำลายมันได้คือการบังคับข้อมูลของประตูกลอย่างดุร้ายและเพื่อพยายาม $2^λ$ การรวมกัน แน่นอนว่าเราไม่ได้พิจารณาการโจมตีประเภทอื่น การโจมตีช่องทางด้านข้าง ฯลฯ หลังจากนั้น เราจะพิจารณารูปแบบฝ่ายตรงข้ามเช่น มีขอบเขตทางการคำนวณ และถ้าเราพิสูจน์ได้ว่าแผนการนี้ปลอดภัยต่อศัตรูนี้ เราก็บอกว่ามี $λ$ บิตของความปลอดภัย

เนื่องจากคุณกำลังอ้างถึงความปลอดภัยทางทฤษฎี คำตอบคือ ไม่. มันอาจจะใช่ถ้าคุณหมายถึงความปลอดภัยเชิงปริมาณ ฉันจะพยายามเสนอตัวอย่างตัวนับที่ใช้งานง่ายมาก

แทนที่จะพิจารณาฟังก์ชันแฮช ลองพิจารณา Textbook RSA ด้วยการเติมที่เหมาะสม เป็นต้น มากำหนดความปลอดภัยในแง่ของความปลอดภัยเชิงความหมายเท่านั้น ดังนั้นจึงปลอดภัย และด้วยเหตุนี้เราจึงกล่าวว่ามี $1^λ$ บิตของความปลอดภัยถ้ามี $พีพีที$ ฝ่ายตรงข้าม (ในพารามิเตอร์ความปลอดภัย) คู่ของข้อความที่มีความยาวเท่ากัน $m_1, m_2$, ciphertexts ที่เป็น corespoding นั้นไม่สามารถแยกความแตกต่างทางการคำนวณได้ หากข้อสันนิษฐานของ RSA เป็นจริง เราทราบดีว่า RSA มีความปลอดภัยทางความหมาย

พิจารณาโครงร่างใหม่โดยที่ $c=Enc_k(Enc_k(x))$. หากรูปแบบการเข้ารหัสล่าสุดมีความปลอดภัยมากกว่ารูปแบบแรก นี่หมายความว่าฝ่ายตรงข้ามจะสามารถบรรลุข้อได้เปรียบที่ไม่อาจละเลยได้ในเกมซึ่งจะได้รับข้อความเข้ารหัสสองรายการ ซึ่งแต่ละรายการเข้ารหัสด้วยรูปแบบทั้งสอง เช่น การกระจายจะต้องปิดอย่างไม่ละเลย จากข้อสันนิษฐานของ RSA ไม่เป็นเช่นนั้น