Score:3

ฟังก์ชันแฮชการเข้ารหัสที่มีประสิทธิภาพในแคลคูลัส λ คืออะไร

ธง ca

ฟังก์ชันแฮชส่วนใหญ่ได้รับการออกแบบมาให้ทำงานได้รวดเร็วในโปรเซสเซอร์ทั่วไป แต่มีบริบทที่ไม่มีจำนวนเต็มของเครื่อง หรือไม่ใช่ตัวเลือกที่มีประสิทธิภาพสูงสุด ตัวอย่างเช่น วงจร zk-snark ไม่มีสิ่งเหล่านี้ และ brainfuck มีเพียงส่วนเพิ่มและส่วนลด หากคุณต้องการฟังก์ชันแฮชที่รวดเร็วในสภาพแวดล้อมเหล่านี้ ไม่น่าเป็นไปได้ที่ sha2/keccak/blake จะทำงานได้ดีกว่าบางอย่างที่ออกแบบมาสำหรับพวกเขา

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

fgrieu avatar
ng flag
แก้ไขฉันถ้าฉันทำผิด แต่ฉันคิดว่าเราไม่รู้ว่ามีฟังก์ชันการเข้ารหัสเวลาพหุนาม (ปลอดภัย) อยู่ในแคลคูลัสปกติหรือไม่ λ-แคลคูลัส ฟังก์ชันดังกล่าวมีประสิทธิภาพน้อยกว่ามากสำหรับคำจำกัดความที่คมชัดกว่าของประสิทธิภาพ มันจะตามมาด้วยเราไม่สามารถพิสูจน์ได้ว่ามีฟังก์ชันดังกล่าวในข้อจำกัดใดๆ ของ λ-แคลคูลัส ดังนั้น หากเราสามารถตอบคำถามนี้ได้อย่างมั่นใจ นั่นต้องเป็นไปในทางลบ สำหรับสิ่งที่ฉันเข้าใจเพียงเล็กน้อยเกี่ยวกับข้อจำกัดนี้ มันรุนแรงมากจนตามสัญชาตญาณแล้ว ไม่มีอะไรที่น่าสนใจในการเข้ารหัสเลยจริงๆ ที่ได้รับอนุญาต
ca flag
@fgrieu มีฟังก์ชันการเข้ารหัสเวลาพหุนามใน λ -แคลคูลัส แม้ว่า ตามตัวอย่างที่ใช้งานได้จริง ภาษาโปรแกรม [Kind](https://github.com/uwu-tech/kind) ของฉันมีการใช้งาน Keccak และคอมไพล์เป็น λ-แคลคูลัส แน่นอน เมื่อกำหนดเป้าหมายไปที่แคลคูลัส λ- บริสุทธิ์ ประสิทธิภาพของ Keccak นั้นแย่มาก แต่ก็ใช้ได้ผลโดยไม่คำนึงว่า บางทีสิ่งที่ฉันถามอาจจะคุ้นเคยมากกว่าถ้าฉันใช้ถ้อยคำใหม่เป็น: *"เราจะใช้ฟังก์ชันแฮชได้อย่างมีประสิทธิภาพเพียงใด หากเราสามารถใช้เฉพาะประเภทข้อมูล Haskell และ case-of (เช่น ไม่มี ints ดั้งเดิม)" * (นั่นเป็นคำถามที่เทียบเท่ากัน)
fgrieu avatar
ng flag
ฉันหมายถึง: ขาดการสันนิษฐานว่า Pâ NP เราไม่มีหลักฐานการมีอยู่ของฟังก์ชันแฮชเข้ารหัสลับที่ปลอดภัยที่นำไปใช้งานได้บนเครื่องทัวริง อัลกอริทึม PPT) ในกรณีของ Keccak ฉันไม่รู้ข้อพิสูจน์แม้ว่าจะสมมติว่า Pâ NP
ca flag
@fgrieu โอ้ แต่ฉันหมายถึงหนึ่งที่ปลอดภัยเทียบเท่ากับ Keccak, Sha2 และที่คล้ายกัน ฉันไม่เข้าใจแม้ว่า ฉันรู้ว่าไม่มีข้อพิสูจน์ว่าฟังก์ชันเหล่านี้ปลอดภัยจริง แต่เกณฑ์ที่ใช้คืออะไร เป็นเพียง: "ผสมบิตเพียงพอและหวังว่าจะดีที่สุด"? ฟังก์ชันแฮชสมัยใหม่โดยพื้นฐานแล้วเป็นเพียงอัลกอริทึมที่บดบังเพียงพอที่ไม่มีใครรู้วิธีเปลี่ยนกลับ ... หรือยัง
Mark avatar
ng flag
@MaiaVictor มักจะประเมินประสิทธิภาพของการก่อสร้างจากการโจมตีที่รู้จัก มีสิ่งอื่นที่เราสามารถทำได้เช่นกัน (เช่น สร้างแฮชจากฟังก์ชันการบีบอัด และพิสูจน์ว่าหากฟังก์ชันการบีบอัดดี แฮชก็จะดี)
Mark avatar
ng flag
@MaiaVictor คุณสามารถสรุปการดำเนินการ "มาตรฐาน" บางอย่างที่มีประสิทธิภาพในแคลคูลัสแลมบ์ดาบริสุทธิ์ที่ไม่ได้พิมพ์ได้หรือไม่ ตัวอย่างเช่น การดำเนินการที่รู้จักกันดีซึ่งมี "ความซับซ้อนในการจับคู่รูปแบบ" ต่ำ

โพสต์คำตอบ

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