Circuit ORAM และประสิทธิภาพในการใช้งานจริง

ORAM แบบวงจร ซึ่ง Wang, Chan และ Shi เสนอในปี 2015 ได้รับการออกแบบเพื่อลดค่าใช้จ่ายด้านแบนด์วิดท์ พร้อมทั้งให้สามารถนำไปใช้งานในกรอบการคำนวณแบบปลอดภัยได้ง่าย (วงจรแบบสับสนและการแบ่งปันความลับ) นวัตกรรมสำคัญคือการลดขนาดถังเหลือ Z = 2 บล็อก (เทียบกับ Z = 5 ใน ORAM แบบเส้นทาง) ซึ่งลดแบนด์วิดท์ลงครึ่งหนึ่งในขณะที่ยังคงความน่าจะเป็นของความล้มเหลวที่น้อยจนละเลยได้ ขั้นตอนการขับบล็อกออกได้รับการออกแบบใหม่ให้เขียนแทนได้ด้วยวงจรบูลีนขนาดเล็ก

ใน ORAM แบบเส้นทางที่มี Z = 5 ความน่าจะเป็นที่พื้นที่พักจะล้นถูกควบคุมด้วยการมีหลายบล็อกในแต่ละถัง เพื่อรองรับการกำหนดบล็อกให้กับเส้นทางแบบสุ่ม ORAM แบบวงจรพิสูจน์ว่า Z = 2 ก็เพียงพอเมื่อใช้ขั้นตอนการขับบล็อกออกแบบกำหนดแน่นอน (การขับออกแบบลึกก่อน) แทนการขับออกแบบสุ่ม วิธีนี้ลดทั้งพื้นที่จัดเก็บบนเซิร์ฟเวอร์และค่าใช้จ่ายด้านการสื่อสารลงครึ่งหนึ่งเมื่อเทียบกับ ORAM แบบเส้นทางที่ใช้พารามิเตอร์ด้านความปลอดภัยเดียวกัน

ORAM แบบวงจรได้รับการออกแบบโดยเฉพาะให้มีขั้นตอนการขับบล็อกออกที่สามารถเขียนแทนได้ด้วยวงจรบูลีนที่มีประสิทธิภาพ ในโพรโทคอลการคำนวณแบบปลอดภัย (วงจรแบบสับสน, SPDZ) การเข้าถึง ORAM เองต้องได้รับการประเมินผลโดยไม่เปิดเผย กล่าวคือ เซิร์ฟเวอร์ที่ดำเนินการคำนวณต้องไม่ทราบว่ามีการเข้าถึงตำแหน่งหน่วยความจำใด วงจรการขับบล็อกออกแบบกำหนดแน่นอนที่เรียบง่ายของ ORAM แบบวงจรมีประสิทธิภาพสูงกว่ามากเมื่อต้องสร้างเป็นวงจรแบบสับสน เมื่อเทียบกับขั้นตอนการขับบล็อกออกของ ORAM แบบเส้นทาง

สำหรับฐานข้อมูลที่มีบล็อก N บล็อก โดยแต่ละบล็อกมีขนาด B ไบต์ ORAM แบบวงจรต้องใช้ข้อมูล 2 * log N * B ไบต์ต่อการเข้าถึงหนึ่งครั้ง (อ่านและเขียนหนึ่งเส้นทาง โดยมี Z = 2 บล็อกต่อถัง) สำหรับ N = 2^20 บล็อกที่แต่ละบล็อกมีขนาด 4KB จะใช้ข้อมูล 160KB ต่อการเข้าถึงหนึ่งครั้ง เทียบกับ 400KB สำหรับ ORAM แบบเส้นทาง (Z=5) ค่าใช้จ่ายด้านแบนด์วิดท์เมื่อเทียบกับข้อมูลข้อความธรรมดาอยู่ที่ประมาณ 40 เท่าสำหรับค่าพารามิเตอร์ทั่วไป ลดลงจาก 100 เท่าสำหรับ ORAM แบบเส้นทาง

Oblix (Misra, Schlegel, Sherwood, Tsudik, 2018) ใช้ ORAM แบบวงจรเพื่อสร้างโครงสร้างข้อมูลระดับสูงรุ่นที่ไม่เปิดเผยรูปแบบการเข้าถึง ได้แก่ รายการเชื่อมโยงแบบไม่เปิดเผย แผนที่แบบไม่เปิดเผย (ตารางแฮช) และคิวลำดับความสำคัญแบบไม่เปิดเผย โครงสร้างเหล่านี้ช่วยให้คำนวณบนข้อมูลแบบพลวัตได้โดยไม่เปิดเผยรูปแบบการเข้าถึง Oblix ทำงานภายในเอนเคลฟ Intel SGX และมุ่งเป้าไปที่การหาจุดตัดเซตแบบเป็นส่วนตัวและคำค้นฐานข้อมูลแบบเป็นส่วนตัว

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) ขยาย ORAM แบบเส้นทางให้รองรับการเข้าถึงแบบอะซิงโครนัสที่มีอัตรารองรับงานสูง โดยประมวลผลคำขอ ORAM หลายรายการแบบขนานและรวมการขับไล่เส้นทางเป็นชุด การรวมการเข้าถึงเส้นทางเดียวกันทำให้ TaoStore มีอัตรารองรับงาน (คำขอต่อวินาที) สูงกว่าการสร้าง ORAM แบบซิงโครนัสอย่างมาก จึงเหมาะสำหรับแม่ข่ายที่เก็บข้อมูลบนคลาวด์ซึ่งมีลูกข่ายหลายรายทำงานพร้อมกัน

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) สร้างระบบที่เก็บข้อมูลเชิงธุรกรรมแบบเต็มรูปแบบบน ORAM แบบเส้นทาง Obladi รองรับธุรกรรม ACID บนที่เก็บข้อมูลที่เข้ารหัสและปกปิดรูปแบบการเข้าถึง ระบบนี้นำเสนอการดำเนินการล่าช้า โดยรวมธุรกรรมเป็นช่วงและดำเนินการในลักษณะที่ปกปิดว่ามีการเข้าถึงระเบียนใดโดยเฉพาะภายในแต่ละช่วง Obladi ทำงานเป็นตัวกลางที่เชื่อถือได้ระหว่างลูกข่ายกับส่วนหลังของที่เก็บข้อมูลบนคลาวด์ที่ไม่ไว้วางใจ

สำหรับ ORAM ขนาด 1GB (262,144 บล็อก ขนาดบล็อกละ 4KB) ที่นำไปใช้งานบน AWS โดยมีลูกข่ายเข้าถึงบล็อกผ่านอินเทอร์เน็ต เวลาแฝงของ ORAM แบบเส้นทางอยู่ที่ประมาณ 50–200 มิลลิวินาทีต่อการเข้าถึง โดยมีเวลาเดินทางไปกลับสำหรับการเข้าถึงถังจำนวน log N = 18 ครั้งเป็นปัจจัยหลัก การดึงถังแบบขนานช่วยลดเวลานี้ได้ สำหรับแอปพลิเคชัน SGX ภายในเครื่องที่มี ORAM อยู่ใน RAM เวลาแฝงอยู่ในช่วง 1–10 มิลลิวินาทีต่อการเข้าถึง ซึ่งยอมรับได้สำหรับแอปพลิเคชันการคำนวณที่ปลอดภัยจำนวนมาก

ค่าใช้แบนด์วิดท์ของ ORAM ขึ้นอยู่กับรูปแบบการเข้าถึงอย่างมาก สำหรับ ORAM ที่เก็บข้อมูลบนคลาวด์ขนาด 1TB ซึ่งใช้บล็อกขนาด 1MB การเข้าถึงแต่ละครั้งจะถ่ายโอนข้อมูลประมาณ 25MB (มีค่าใช้จ่ายส่วนเกิน 25 เท่า สำหรับระดับ log N = 25 ระดับ) สำหรับบล็อกขนาดเล็ก (4KB) ค่าใช้จ่ายส่วนเกินต่อการเข้าถึงจะน้อยกว่าเมื่อวัดเป็นจำนวนไบต์จริง แต่สูงกว่าเมื่อวัดเป็นสัดส่วน องค์กรที่นำ ORAM ไปใช้งานต้องจัดสรรแบนด์วิดท์เผื่อการขยาย 20–50 เท่า และตรวจสอบให้แน่ใจว่าลิงก์เครือข่ายและค่าใช้จ่ายการส่งข้อมูลออกจากคลาวด์รองรับเรื่องนี้

ทางเลือกหนึ่งของ ORAM สำหรับการรักษาความเป็นส่วนตัวของการเข้าถึงคือฮาร์ดแวร์ที่เชื่อถือได้ โดย Intel SGX หรือ AMD SEV จัดเตรียมสภาพแวดล้อมการทำงานที่เชื่อถือได้ ซึ่งแม้แต่ระบบปฏิบัติการของแม่ข่ายก็ไม่สามารถสังเกตการคำนวณหรือรูปแบบการเข้าถึงหน่วยความจำได้ เมื่อมีกลไกป้องกันที่เหมาะสม อย่างไรก็ตาม SGX ที่ไม่มี ORAM ยังคงเปิดเผยรูปแบบการเข้าถึงระดับหน้าให้ฮาร์ดแวร์ทราบ ดังนั้นจึงต้องใช้ ORAM ภายใน SGX เพื่อการปกป้องอย่างสมบูรณ์ เมื่อเทียบกับ ORAM ล้วน ฮาร์ดแวร์ที่เชื่อถือได้ช่วยลดค่าใช้แบนด์วิดท์ส่วนเกิน แต่ต้องไว้วางใจผู้ผลิตฮาร์ดแวร์และห่วงโซ่อุปทาน

ORAM เหมาะสมเมื่อฝ่ายตรงข้ามสามารถสังเกตรูปแบบการเข้าถึงฝั่งแม่ข่ายได้ เช่น ผู้ให้บริการคลาวด์หรือผู้เช่าร่วม ความอ่อนไหวของข้อมูลคุ้มค่ากับค่าใช้แบนด์วิดท์ส่วนเกิน 20–50 เท่า และรูปแบบการเข้าถึงนั้นอาจเปิดเผยข้อมูลที่ละเอียดอ่อนได้ สำหรับแอปพลิเคชันส่วนใหญ่ การเข้ารหัสมาตรฐานร่วมกับการจัดการกุญแจอย่างรอบคอบก็เพียงพอแล้ว ORAM เป็นเครื่องมือเฉพาะทางสำหรับสถานการณ์ที่ต้องการความปลอดภัยสูง เช่น การวิเคราะห์ข้อมูลทางการแพทย์ การเรียนรู้ของเครื่องที่รักษาความเป็นส่วนตัว ระบบซื้อขายทางการเงิน และฐานข้อมูลของหน่วยงานบังคับใช้กฎหมาย

ORAM แบบวงจรลดขนาดถังเหลือ Z=2 (เทียบกับ Z=5 ของ ORAM แบบเส้นทาง) และลดแบนด์วิดท์ลงครึ่งหนึ่งด้วยการขับไล่แบบลึกก่อนที่กำหนดแน่นอน ระบบนี้ออกแบบมาเพื่อใช้งานภายในการคำนวณที่ปลอดภัยด้วยวงจรที่ทำให้สับสน ค่าใช้จ่ายส่วนเกินในทางปฏิบัติคือการขยายแบนด์วิดท์ 40 เท่าสำหรับพารามิเตอร์ทั่วไป ระบบที่ใช้งานจริงประกอบด้วย Oblix (SGX + โครงสร้างข้อมูลแบบปกปิดการเข้าถึง), TaoStore (ORAM แบบรวมชุดที่มีอัตรารองรับงานสูง) และ Obladi (ORAM เชิงธุรกรรม) การใช้ ORAM ภายใน SGX เป็นสิ่งจำเป็น เพราะ SGX เพียงอย่างเดียวยังคงเปิดเผยรูปแบบการเข้าถึงระดับหน้า