Circuit ORAM والأداء العملي

صُمم Circuit ORAM، الذي اقترحه Wang وChan وShi عام 2015، لتقليل كلفة عرض النطاق الترددي مع الحفاظ على سهولة تنفيذه في أطر الحوسبة الآمنة (الدوائر المموّهة وتقاسم الأسرار). ويتمثل ابتكاره الأساسي في تقليل حجم الحاوية إلى Z = 2 كتلة، مقارنةً بـ Z = 5 في Path ORAM، مما يخفض عرض النطاق الترددي إلى النصف مع الحفاظ على احتمال فشل ضئيل للغاية. وأُعيد تصميم إجراء الإخلاء بحيث يمكن التعبير عنه في صورة دائرة منطقية صغيرة.

في Path ORAM مع Z = 5، يُضبط احتمال امتلاء المخبأ من خلال وجود عدة كتل في كل حاوية لاستيعاب التعيين العشوائي للكتل إلى المسارات. ويثبت Circuit ORAM أن Z = 2 كافٍ عند استخدام إجراء إخلاء حتمي (الإخلاء بدءًا من الأعمق) بدلًا من الإخلاء العشوائي. ويخفض ذلك إلى النصف كلفة تخزين الخادم وكلفة الاتصال مقارنةً بـ Path ORAM ذي المعاملات الأمنية نفسها.

صُمم Circuit ORAM خصيصًا بحيث يكون إجراء الإخلاء فيه قابلًا للتعبير عنه في صورة دائرة منطقية فعّالة. وفي بروتوكولات الحوسبة الآمنة (الدوائر المموّهة وSPDZ)، يجب تقييم عملية الوصول إلى ORAM بطريقة متخفية، إذ يجب ألا يتعلم الخادم الذي يجري الحساب أي موقع في الذاكرة جرى الوصول إليه. وتكون دائرة الإخلاء الحتمية البسيطة في Circuit ORAM أكثر كفاءة بكثير عند تحويلها إلى دائرة مموّهة من إجراء الإخلاء في Path ORAM.

بالنسبة إلى قاعدة بيانات تتكون من N كتلة، حجم كل منها B بايت، يتطلب Circuit ORAM مقدار 2 * log N * B بايت لكل عملية وصول (قراءة مسار واحد وكتابته، مع Z = 2 كتلة لكل حاوية). وبالنسبة إلى N = 2^20 كتلة، حجم كل منها 4KB، يبلغ ذلك 160KB لكل عملية وصول، مقارنةً بـ 400KB في Path ORAM (Z=5). وتبلغ كلفة عرض النطاق الترددي الإضافية مقارنةً بالنص الصريح نحو 40x للمعاملات المعتادة، بعد أن كانت 100x في Path ORAM.

يستخدم Oblix (Misra وSchlegel وSherwood وTsudik، 2018) Circuit ORAM لبناء إصدارات متخفية من هياكل البيانات عالية المستوى، مثل القوائم المرتبطة المتخفية والخرائط المتخفية (جداول التجزئة) وقوائم الأولوية المتخفية. وتتيح هذه الهياكل إجراء حسابات متخفية على بيانات ديناميكية من دون كشف أنماط الوصول. ويعمل Oblix داخل بيئات Intel SGX المعزولة، ويستهدف تقاطع المجموعات الخاص واستعلامات قواعد البيانات الخاصة.

يوسّع TaoStore ‏(Sahin, Zhu, Gunter, Borisov, 2016)‏ نظام Path ORAM ليدعم الوصول غير المتزامن عالي الإنتاجية، وذلك من خلال معالجة طلبات ORAM المتعددة بالتوازي وتجميع عمليات إخلاء المسارات. ومن خلال دمج عمليات الوصول إلى المسار نفسه، يحقق TaoStore إنتاجية أعلى بكثير (من حيث عدد الطلبات في الثانية) مقارنةً بإنشاءات ORAM المتزامنة، مما يجعله مناسبًا لخوادم التخزين السحابي التي يتصل بها العديد من العملاء المتزامنين.

يبني Obladi ‏(Crooks, Park, Alvisi, Iyengar, 2018)‏ نظام تخزين معاملاتي كاملًا فوق Path ORAM. ويدعم Obladi المعاملات المتوافقة مع ACID على وحدة تخزين مشفّرة تخفي نمط الوصول. ويقدّم التنفيذ المؤجل، إذ تُجمّع المعاملات في حقب وتُنفّذ بطريقة تخفي السجلات المحددة التي جرى الوصول إليها ضمن كل حقبة. ويعمل Obladi كوكيل موثوق بين العملاء وواجهة التخزين السحابية غير الموثوقة.

بالنسبة إلى ORAM بحجم 1GB (أي 262,144 كتلة، حجم كل منها 4KB) منشور على AWS، مع وصول عميل إلى الكتل عبر الإنترنت، يبلغ زمن استجابة Path ORAM نحو 50-200ms لكل عملية وصول، ويهيمن عليه زمن الذهاب والإياب اللازم لعمليات الوصول إلى حاويات log N = 18. ويمكن خفض هذا الزمن من خلال جلب الحاويات بالتوازي. أما تطبيقات SGX المحلية التي تحتفظ بـ ORAM في الذاكرة، فيتراوح زمن الاستجابة فيها بين 1 و10ms لكل عملية وصول، وهو زمن مقبول للعديد من تطبيقات الحوسبة الآمنة.

يعتمد الحمل الزائد على النطاق الترددي في ORAM بدرجة كبيرة على أنماط الوصول. ففي ORAM للتخزين السحابي بسعة 1TB وكتل حجمها 1MB، تنقل كل عملية وصول نحو 25MB (أي حمل زائد بمقدار 25x عبر مستويات log N = 25). وبالنسبة إلى الكتل الصغيرة (4KB)، يكون الحمل الزائد لكل عملية وصول أقل من حيث عدد البايتات المطلق، لكنه أعلى نسبيًا. ويجب على المؤسسات التي تنشر ORAM أن تضع في ميزانيتها تضخيمًا للنطاق الترددي بمقدار 20-50x، وأن تتأكد من أن وصلات الشبكة وتكاليف إخراج البيانات من السحابة لديهما القدرة على استيعاب ذلك.

يمثل العتاد الموثوق بديلًا لـ ORAM لحماية خصوصية الوصول: إذ يوفر Intel SGX أو AMD SEV بيئة تنفيذ موثوقة لا يستطيع فيها حتى نظام التشغيل المضيف مراقبة الحسابات أو أنماط الوصول إلى الذاكرة، مع تطبيق وسائل الحماية المناسبة. ومع ذلك، فإن SGX من دون ORAM يسرّب أنماط الوصول على مستوى الصفحات إلى العتاد، ولذلك يلزم استخدام ORAM داخل SGX لتوفير حماية كاملة. وبالمقارنة مع ORAM وحده، يقلل العتاد الموثوق الحمل الزائد على النطاق الترددي، لكنه يتطلب الوثوق بمُصنّع العتاد وسلسلة التوريد.

يكون ORAM مناسبًا عندما يراقب الخصم أنماط الوصول من جانب الخادم (مثل موفر السحابة أو المستأجر المشارك)، وعندما تبرر حساسية البيانات تحمل حمل زائد على النطاق الترددي بمقدار 20-50x، وعندما يكشف نمط الوصول نفسه معلومات حساسة. أما معظم التطبيقات، فيكفيها التشفير القياسي مع إدارة دقيقة للمفاتيح. ويُعد ORAM أداة متخصصة للسيناريوهات عالية الأمان، مثل تحليل البيانات الطبية، والتعلم الآلي الخاص، وأنظمة التداول المالي، وقواعد بيانات جهات إنفاذ القانون.

يقلل Circuit ORAM حجم الحاوية إلى Z=2 (مقابل Z=5 في Path ORAM)، مما يخفض النطاق الترددي إلى النصف من خلال إخلاء حتمي يبدأ من الأعماق أولًا. وقد صُمم للاستخدام داخل الحوسبة الآمنة بالدوائر المبهمة. ويبلغ الحمل العملي نحو 40x من تضخيم النطاق الترددي للمعلمات المعتادة. وتشمل أنظمة الإنتاج Oblix ‏(SGX + هياكل بيانات متخفية) وTaoStore ‏(ORAM مجمّع عالي الإنتاجية) وObladi ‏(ORAM معاملاتية). ويُعد استخدام ORAM داخل SGX ضروريًا لأن SGX وحده يسرّب أنماط الوصول على مستوى الصفحات.