Path ORAM: การซ่อนการเข้าถึงหน่วยความจำ

ORAM แบบเส้นทาง ซึ่ง Stefanov, van Dijk, Shi, Fletcher, Ren, Yu และ Devadas เสนอในปี 2013 เป็นรูปแบบ ORAM ที่มีอิทธิพลต่อการใช้งานจริงมากที่สุด โดยจัดระเบียบพื้นที่จัดเก็บบนเซิร์ฟเวอร์เป็นต้นไม้ทวิภาคของถัง แต่ละใบสอดคล้องกับตำแหน่งสำหรับบล็อกข้อมูลหนึ่งบล็อก ORAM แบบเส้นทางมีค่าใช้จ่ายด้านการสื่อสาร O(log^2 N) ต่อการเข้าถึงหนึ่งครั้งในรูปแบบพื้นฐาน และมีโครงสร้างเรียบง่ายพอที่จะนำไปใช้งานได้ด้วยบรรทัดคำสั่งเพียงไม่กี่ร้อยบรรทัด

แผนผังตำแหน่งเป็นโครงสร้างข้อมูลฝั่งไคลเอนต์ที่จับคู่ที่อยู่บล็อกเชิงตรรกะแต่ละรายการกับโหนดใบในต้นไม้ทวิภาค สำหรับฐานข้อมูลที่มีบล็อก N บล็อกและต้นไม้ที่มีความสูง L = log N แผนผังตำแหน่งจะเป็นอาร์เรย์ของดัชนีใบจำนวน N รายการ ก่อนเข้าถึงบล็อก b ไคลเอนต์จะค้นหาใบที่กำหนดไว้ในปัจจุบันจากแผนผังตำแหน่ง แล้วกำหนดใบใหม่แบบสุ่มให้บล็อกนั้น เส้นทางจากใบเดิมจะถูกอ่านจากเซิร์ฟเวอร์และเขียนกลับไปยังเซิร์ฟเวอร์

พื้นที่พักเป็นบัฟเฟอร์ขนาดเล็กฝั่งไคลเอนต์ (โดยทั่วไปมีขนาด 20-40 บล็อก) ซึ่งเก็บบล็อกที่อ่านจากเซิร์ฟเวอร์แล้วแต่ยังไม่ได้เขียนกลับไว้ชั่วคราว เมื่ออ่านบล็อกหนึ่ง บล็อกนั้นจะถูกนำออกจากเส้นทางและใส่ไว้ในพื้นที่พัก หลังจากเข้าถึงและอาจแก้ไขบล็อกนั้นแล้ว บล็อกทั้งหมดในพื้นที่พักที่สามารถวางบนเส้นทางใหม่ได้จะถูกเขียนกลับ บล็อกที่ไม่สามารถวางลงในเส้นทางได้จะยังคงอยู่ในพื้นที่พัก

พื้นที่จัดเก็บบนเซิร์ฟเวอร์เป็นต้นไม้ทวิภาคแบบสมบูรณ์ที่มี L+1 ระดับ (L = log N) แต่ละโหนด (ถัง) เก็บบล็อกได้ Z บล็อก (โดยทั่วไป Z = 5) ใบแต่ละใบสอดคล้องกับตำแหน่งสำหรับบล็อกข้อมูล มีโหนดใบ N โหนด ดังนั้นจึงมีโหนดทั้งหมด 2N-1 โหนด และพื้นที่จัดเก็บบนเซิร์ฟเวอร์ทั้งหมด O(NZ) เส้นทางจากใบถึงรากแต่ละเส้นทางมีโหนด log N โหนด และเก็บบล็อกได้ Z*log N บล็อก จึงมีความจุเพียงพอสำหรับกลยุทธ์การขับบล็อกออกตามเส้นทาง

หากต้องการอ่านบล็อก b ให้ดำเนินการดังนี้: (1) ค้นหาใบปัจจุบัน l ของ b ในแผนผังตำแหน่ง (2) กำหนดใบใหม่แบบสุ่ม l' ให้ b และปรับปรุงแผนผังตำแหน่ง (3) อ่านถังทั้งหมดบนเส้นทางจากใบ l ถึงราก (ถัง log N ถัง) (4) ค้นหาบล็อก b ในเส้นทางที่อ่านมาหรือในพื้นที่พัก (5) เขียนบล็อกทั้งหมดที่สามารถกำหนดให้อยู่บนเส้นทางใหม่ l' กลับไป และเติมช่องถังที่เหลือด้วยบล็อกจำลอง เซิร์ฟเวอร์จะเห็นการอ่านเส้นทางสุ่มทุกครั้ง

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

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

แผนผังตำแหน่งแบบพื้นฐานต้องเก็บรายการจำนวน N รายการไว้ที่ไคลเอนต์ ซึ่งทำให้ต้องใช้พื้นที่จัดเก็บฝั่งไคลเอนต์ O(N) หรือมีขนาดเท่ากับฐานข้อมูลทั้งหมด แผนผังตำแหน่งแบบเรียกซ้ำลดพื้นที่จัดเก็บฝั่งไคลเอนต์เหลือ O(log^2 N) ด้วยการจัดเก็บแผนผังตำแหน่งเองไว้ใน ORAM ที่มีขนาดเล็กกว่าแบบเรียกซ้ำ การเรียกซ้ำจะสิ้นสุดเมื่อ ORAM มีขนาดเล็กพอที่จะใส่ในพื้นที่พักได้ นี่เป็นเทคนิคมาตรฐานที่ทำให้ ORAM แบบเส้นทางใช้งานได้จริงกับชุดข้อมูลขนาดใหญ่

ขนาดพื้นที่พักใน ORAM แบบเส้นทางจะเพิ่มขึ้นหากไม่สามารถขับบล็อกออกไปยังเส้นทางที่กำหนดไว้ได้ เนื่องจากเส้นทางขัดแย้งกัน Stefanov และคณะพิสูจน์ว่า พื้นที่พักจะล้น (มีขนาดเกิน R บล็อก) ด้วยความน่าจะเป็นที่ลดลงแบบเอ็กซ์โพเนนเชียลตาม R โดยเฉพาะแล้ว ความน่าจะเป็นจะไม่เกิน 14 * (0.6002)^R การกำหนด R = 40 ทำให้ความน่าจะเป็นของความล้มเหลวอยู่ที่ประมาณ 2^{-38} และผลนี้ใช้ได้กับลำดับการเข้าถึงทั้งหมด รวมถึงลำดับที่ผู้โจมตีเลือกโดยเจตนา

ก่อนมี ORAM แบบเส้นทาง รูปแบบ ORAM ที่ใช้งานได้จริงและมีประสิทธิภาพดีที่สุดมีค่าใช้จ่าย O(log^3 N) (Shi และคณะ 2011, "RAM แบบไม่เปิดเผยที่มีต้นทุนกรณีเลวร้ายที่สุด O((log N)^3)") ORAM แบบเส้นทางลดค่าใช้จ่ายนี้เหลือ O(log^2 N) พร้อมโครงสร้างที่เรียบง่ายกว่ามาก งานวิจัยในเวลาต่อมา (ORAM แบบวงจร, OptORAMa) ปรับปรุงค่าคงที่และขอบเขตเชิงเส้นกำกับให้ดียิ่งขึ้น แต่ ORAM แบบเส้นทางยังคงเป็นรูปแบบที่มีการนำไปใช้งานมากที่สุดเนื่องจากความเรียบง่าย

มีการนำ ORAM แบบเส้นทางไปใช้งานในระบบวิจัยและระบบใช้งานจริงหลายสิบระบบ ZeroTrace (Intel SGX + ORAM แบบเส้นทาง), Obladi (ORAM แบบเส้นทางบนที่เก็บข้อมูลคลาวด์) และ Opaque (ORAM แบบเส้นทางบน Apache Spark) เป็นตัวอย่างการนำไปใช้งานที่โดดเด่น กลุ่มการคำนวณแบบปลอดภัยของ Stanford ดูแลการนำ ORAM แบบเส้นทางในภาษา C++ แบบเปิดซอร์สไว้ AWS นำเสนอ ORAM แบบเส้นทางเป็นส่วนหนึ่งของต้นแบบการวิจัย Nitro Enclaves สำหรับการวิเคราะห์ข้อมูลที่รักษาความเป็นส่วนตัว

แผนผังตำแหน่งมีหน้าที่อะไรใน ORAM แบบเส้นทาง

ORAM แบบเส้นทางจัดระเบียบพื้นที่จัดเก็บบนเซิร์ฟเวอร์เป็นต้นไม้ทวิภาค โดยการเข้าถึงแต่ละครั้งจะอ่านหรือเขียนเส้นทางหนึ่งเส้นทางจากรากถึงใบ แผนผังตำแหน่งติดตามการกำหนดใบปัจจุบันของแต่ละบล็อก ส่วนพื้นที่พักจะเก็บบล็อกที่เพิ่งเข้าถึงไว้ชั่วคราว การเข้าถึงทุกครั้งจะถูกสุ่มด้วยการกำหนดตำแหน่งใบใหม่แบบสุ่ม ทำให้การเข้าถึงทั้งหมดที่เซิร์ฟเวอร์มองเห็นมีการแจกแจงเหมือนกัน ค่าใช้จ่ายด้านการสื่อสารคือ O(Z * log N) ต่อการเข้าถึงหนึ่งครั้ง แผนผังตำแหน่งแบบเรียกซ้ำลดพื้นที่จัดเก็บฝั่งไคลเอนต์เหลือ O(log^2 N) ORAM แบบเส้นทางเป็นรูปแบบ ORAM ที่มีการนำไปใช้งานมากที่สุด