پرس و جو روی داده های رمز شده

پرس و جو روی داده های رمز شده

اسلاید 1: پرس و جو روی داده های رمز شدهعلی هادویخرداد 88درس امنیت پایگاه داده

اسلاید 2: مقدمهروش‌هاي کنترل دسترسي برای محافظت از داده ها کافي نيستندسرقت رسانه محتوی دادهعدم اعتماد به اعمال کننده خط مشی های کنترل دسترسیامکان دور زدن مکانیزم های کنترل دسترسی توسط مهاجمینمطرح شدن ایده Database as A Service و سیستم های کارگزار غیرقابل اعتماد

اسلاید 3: مدل پایگاه داه به عنوان خدمتپایگاه داده به عنوان خدمت (Database as A Service) به عنوان رویکردی جدید در برون‌سپاری پایگاه‌ داده‌هادر دسترس بودن داده ها توسط کارگزار تضمین می شود.کلیه اعمال مدیریت داده را کارگزار فراهم می کند. کارگزار از نظر نگهداري داده‌ها و عدم ارسال عمدي پاسخ اشتباه مورد اعتماد است. کارگزار در مورد محرمانگي داده‌ها مورد اعتماد نيست. کارگزار درستکار ولی کنجکاو است (Honest but curious).

اسلاید 4: مدل پایگاه داده به عنوان خدمتچالش اصلی در این مدل تأمین امنیت داده‌های برون‌سپاری شده است.راه حل اولیه رمزنگاری داده های برون‌سپاری شده است. برای حفظ محرمانگی مالک داده، داده خود را رمز کرده و آن را در پایگاه داده رمز شده در سمت کارگزار ذخیره می کند. ریزدانگی رمزنگاری به خط مشی های محیط برای سطح دسترسی، امنیت و کارایی بستگی دارد. بیشتر فعالیت ها ریزدانگی را در سطح چندتایی تعریف کرده اند.

اسلاید 5: عناصر مدل DASمالک داده‌ها: فرد يا سازمان است که داده‌ها را ايجاد و آن را برون‌سپاري مي‌کند.کاربر: پرس‌وجو‌ها را به سيستم ارائه مي‌کند.کارخواه: پرس‌وجوهاي کاربر را به پرس‌وجوهاي قابل اجرا روي داده‌هاي رمزشده تبديل مي‌کند.کارگزار: محل ذخيره‌ي داده‌هاي رمز شده است و پرس‌وجوهاي ارسالي از سمت کارخواه را روي داده‌هاي رمزشده اجرا کرده و نتيجه را به کارخواه ارائه مي‌دهد.

اسلاید 6: سناریوی پرس و جو در مدل DASکاربر پرس و جوی Q را با توجه به اسکیمای پایگاه داده ی رمز نشده B از طریق کارخواه وارد می کند. برون سپاری داده می تواند از دید کاربر شفاف باشد. کارخواه پرس و جوی کاربر را به دو بخش Qs و Qc تقسیم می کند. Qsپرس و جوی اعمال شده بر روی داده های رمز شده در سمت کارگزار و Qc پرس و جوی اعمال شده در سمت کارفرما بر روی داده های برگشتی از کارگزار به کارخواه است. کارخواه ساختار پایگاه داده عادی و رمز شده را می داندکارگزار پرس و جوی Qs را روی داده رمز شده اجرا و نتایج (مجموعه ای از چندتایی های رمز شده) را به کارخواه بر میگرداند. کارخواه نتایج را رمزگشایی کرده و چندتایی های اضافی را با اعمال Qc به نتایج اولیه حذف می کند. نتایج نهایی به کاربر ارائه می شود.

اسلاید 7: سناریوی پرس و جو در مدل DAS

اسلاید 8: ملاحظات رمزنگاری در برون سپاری دادهروش هایی که بتوانند به طور مستقیم با داده های رمز شده کار کند باید ملاحظات زیر را درنظر بگیرند:میزان اعتماد به کارگزاردر مدل DAS امکان رمزگشایی توسط کارگزار نامطمئن وجود ندارد.کارایی روش اجرای پرس و جورمزگشایی کل داده های قبل از اجرای پرس و جو کارا نیست.تمرکز اجرای اعمال در سمت کارگزارسربار قابل قبول برای ذخیره سازی و ارتباطات بین کارفرما و کارگزارریزدانگی رمزنگاریاگر رمزنگاری بصورت درشت‌دانه باشد امکان بهینه‌سازی پرس‌وجو کم می شود رمزنگاری به صورت ریز دانه نیز کارایی را کمتر و در شرایطی به ممکن است به مهاجم اجازه استنتاج از داده‌ها را بدهد. کنترل دسترسی در سیستم های چند کاربره

اسلاید 9: ملاحظات رمزنگاری در برون سپاری داده (2)مقاومت در برابر حملات حمله متن رمزشده معلوم: به طور کلي فرض مي‌شود که مهاجم به داده رمزشده دسترسي دارد. هدف در اين حمله شکستن متن رمزشده خاص يا پيدا کردن کليد است. حمله متن اصلی معلوم: مهاجم به تعدادي متن اصلي و معادل رمزشده آن‌ها دسترسي دارد که از آن براي به دست آوردن بقيه‌ي متون رمزشده يا پي بردن به کليد رمز استفاده مي‌کند.حمله متن اصلی انتخابي: مهاجم مي‌تواند معادل رمزشده متن اصلي دلخواه خود را به دست بياورد. اين حمله، نوع قويتري نسبت به حمله‌ي متن اصلی معلوم است. حمله متن رمز شده انتخابی: مهاجم می‌تواند رمزگشایی شده معادل متن رمزشده دلخواه را بدست آورد.حملات تحلیل فرکانسی: ممکن است مهاجم (server) اطلاعات اولیه‌ای راجع به دامنه مقادیر و فرکانس رخداد داده‌های رمزنشده داشته باشد و از آن برای نفوذ به پایگاه داده استفاده کند. حملات مبتنی بر اندازه: ممکن است مهاجم اطلاعاتی راجع‌به ارتباط طول متن اصلی و متن رمزشده داشته باشد. بنابراین اگر مهاجم مجموعه‌ای از داده‌های اصلی و متن رمز شده معادل را داشته باشد می‌تواند به پایگاه داده حمله کند.

اسلاید 10: ملاحظات رمزنگاری در برون سپاری داده (3)پشتیبانی از انواع پرس و جوپرس و جو روی داده های عددیپرس و جو با شرط تساوی پرس و جوی بازه ایپرس و جو روی داده های رشته ایپرس و جو با شرط تساویپرس و جو های تطبیق الگوییپرس و جوهای شامل توابع تجمعی

اسلاید 11: روش های جستجو روی داده های رمز شدهجستجوی مستقیم روی داده های رمز شدهجستجوی مبتنی بر شاخصروش های مبتنی بر حفظ ترتیبروش های مبتنی بر توابع همریخت اختفایی

اسلاید 12: جستجوی مستقیم روی داده های رمز شدهداده به گونه ای رمز می شود که جستجو بتواند دقیقاً روی همان داده رمز شده به صورت مستقیم صورت گیرد. سانگ روشی را بر اساس این ایده برای جستجو روی داده های رشته ای ارائه داده است.

اسلاید 13: روش Song - معرفیجستجوی کلمات روی اسناد رمز شده (تمرکز بر DB نیست)کاربرد مفهوم دریچهکارگزار می‌تواند با گرفتن اطلاعات کوچکي در مورد هر کلمه (دريچه)، جستجو را بدون اطلاع از کلمات ديگر متن انجام دهد.توابع مبتنی بر دریچه توابعی هستند که محاسبه‌ي معکوس آنها بدون داشتن اطلاعات خاصی به نام دریچه مشکل است.در رمزنگاري مبتني بر دريچه، رمزگشايي با داشتن دريچه امکان‌پذير است. در اين روش‌ها، به همراه هر کلمه‌اي که کارخواه جستجوي آنرا تقاضا کرده است، دريچه‌ي آن نيز ارسال مي‌شود. بدين شکل کارگزار فقط مي‌تواند کلمه درخواست شده را رمزگشايي کند.

اسلاید 14: روش Song - رمزگذاریمتن اصلی به تعدادی کلمه w با طول یکسان (n بیت) تقسیم می شود.اسناد اصلی پس از رمزشدن به روش شرح داده شده، به سمت کارگزار ارسال و در آنجا ذخیره می‌شوند.کارگزار با دريافت دريچه‌اي از طرف کارخواه می تواند کلمه‌ی مورد نظر کاربر را جستجو کند. پارامترهای رمزنگاری S : مولد اعداد شبه تصادفیF وf : توابع شبه تصادفیK’: کلید تابع f (برای تمام کلمات متن ثابت است)دریچه هر کلمه: کلید تابع F: f k’(first n-m bits of Ek’’(wi))

اسلاید 15: روش Song – رمزگذاری(2)رمزگذاری در دو سطح انجام می شود.سطح اول: هر کلمه با یکی از الگوریتم‌های رمزنگاري متقارن و کلید (k) رمز می شود. کارگزار در هنگام اجراي پرس‌وجو از کلمه‌ي درخواست شده کارخواه مطلع نمی شود. سطح دوم: مولد شبه‌ تصادفيS ، دنباله‌اي از اعداد شبه تصادفي si با طول n-m بیت به تعداد کلمات متن اصلي ايجاد مي‌کند. اعداد شبه تصادفی تولید شده si با استفاده از تابع F درهم‌سازي شده و خروجی m بیتی تولید می شود. (رمزشده‌ي لایه‌ي اول هر کلمه (Ek(wi))) با ( si و حاصل درهم‌سازی شده‌ در مرحله قبل)، XOR می‌شود. نتیجه‌ی لایه‌ي دوم رمزنگاریِ کلمه‌ي wi به عنوان iامین کلمه‌ي متن رمزشده (ci) در سند رمزشده قرار می‌گیرد.15

اسلاید 16: روش Song- رمزگذاری(3)

اسلاید 17: روش Song - اعمال پرس و جوکارخواه برای جستجوی یک کلمه (w) در اسناد رمزشده، معادل رمز شده‌ي لایه‌ي اول کلمه (Ek(w)) به همراه دریچه‌ي آن (fk(w)) را به کارگزار ارسال می‌کند. کارگزار با دریافت (Ek(w)) کلمات تمام اسناد را با آن XOR می‌کند. اگر کلمه‌ي Pام سندی با کلمه‌ي درخواست شده برابر باشد، حاصل XOR (Tp) باید ساختاری به شکل <Sp, Ff (k’(w)) (sp)> داشته باشد. برای بررسی وجود ساختار فوق برای کلمه‌ي pام متن رمزشده، حاصل تابع F روی n-m بیت پرارزش Tp به دست آورده می‌شود. اگر مقدار به دست آمده با m بیت باقی‌مانده‌ي Tp برابر باشد، ساختار برقرار بوده و کلمه‌ي Pام متن رمزشده به همراه سندی که به آن متعلق است در مجموعه‌ي جواب ارسالی به کارخواه قرار می‌گیرد. تابع F یک تابع درهم‌ساز دارای برخورد است. بنابراین امکان وجود اشتباه مثبت در نتایج ارسالی به کارخواه وجود دارد. در سمت کارخواه پس از رمزگشایی سند، مقدار اصلی کلمه‌ي پیدا شده با کلمه‌ي درخواست شده‌ي کاربر مقایسه می‌شود تا نتایج درستی به کاربر برگردانده شود.

اسلاید 18: روش Song - رمزگشاییبرای رمزگشایی کلمه‌ي iاُم سند رمزشده (ci)، ابتدا n-m بیت پرارزش ci باsi ، XOR می‌شود و n-m بیت پر ارزش Ek(wi) به دست می آید. از مقدار فوق برای ساختن دریچه‌ي wi استفاده می‌شود. اعمال دریچه بدست آمده و n-m بیت پر ارزش si به تابع F، m بیت نتیجه دارد که با XOR کردن با m بیت کم ارزش ci، m بیت کم ارزش Ek(wi) حاصل می شود. بدین ترتیب تمام بیت‌های Ek(wi) به دست می‌آیند.Ek(wi) رمزگشایی شده تا مقدار اصلی wi حاصل شود. 18

اسلاید 19: ویژگی های روش Songکارگزار نمی تواند در مورد متن اصلی تنها با استفاده از متن رمز شده اطلاعاتی بدست آورد.سربار ذخیره سازی و ارتباطاتی آن کم است.نتیجه حاوی مکان هایی از سند است که W در آن ظاهر شده است و ممکن است دارای اشتباهات مثبت باشد.اشتباهات مثبت با مقدار m مرتبط است. هر جواب اشتباه با احتمال 1/2m رخ می دهد. بنابراین برای سندی با طول l کلمه انتظار l/2m جواب اشتباه وجود دارد.متن باید تقسیم به کلماتی با طول مساوی شود که با توجه به ساختار زبان، روش مناسبی نیست.

اسلاید 20: ویژگی های روش Song (2)امکان جستجو با هر طول دلخواه وجود ندارد. فقط مي‌توان کلمات با طول n يا ضريبي از n بیت را جستجو کرد. گروه محدودي از الگو‌ها قابل جستجو است. الگوهايي به شکلab[a-z] با تبديل به aba, abb, abc, …, abz قابل جستجو هستند؛ جستجوي الگوهايي به شکل ab*” مشکل است. زيرا تعداد رشته‌هاي توليدي بسیار زياد خواهند شد.در الگوريتم سانگ، براي يافتن هر کلمه بايد کل محتويات تمام اسناد جستجو شود. زمان جستجو نسبت به طول متن خطی است. بنابراین در قابل مقیاس بزرگ (مانند پایگاه داده) کارا نیست.یک روش افزایش سرعت بکارگیری شاخص های از پیش تعریف شده است.

اسلاید 21: جمع بندی - جستجوی مستقیم روی داده رمز شدهفضای ذخیره سازی نسبت به ذخیره سازی داده اصلی تفاوت زیادی ندارد.معمولاً احتمال اجرای حملات فرکانسی نسبت به روش مبتنی بر شاخص کمتر است. در برخی روش ها کلمه ای که چندین بار بکار رفته، هر بار به شکل جدیدی رمز می شود (بسته به جایگاه کلمه در متن)بیشتر اجرای پرس و جو در سمت کارگزار است. تنها رمزنگاری کلمه مورد پرس و جو در سمت کارخواه انجام می شود.نسبت به روش های مبتنی بر شاخص دارای جواب اشتباه کمتری است. پیچیدگی محاسباتی بالایی دارند و زمان جستجو در آن ها خطی است. بنابراین در مقیاس بزرگ قابل استفاده نیست. این روش ها بیشتر برای ابزارهایی با جستجوی در مقیاس کوچک (مانند تلفن همراه) مناسب است. پرس و جوهای با شرایط تطبیق دقیق را پاسخ می دهند. پرس وجوی شامل شرایط بازه ای و جستجوی الگوها بر روی داده های رشته ای در این روش سخت است.پرس و جو شامل توابع تجمعی امکان پذیر نیست.

اسلاید 22: جستجوی مبتنی بر شاخصاطلاعاتی با نام شاخص همراه با داده رمز شده در سمت کارگزار ذخیره می شود. جستجوی داده با استفاده از شاخص ذخیره شده انجام می گیرد.برای هر عنصر که بخواهد جستجو بر مبنای آن انجام شود، باید یک شاخص تعریف کرد. شاخص نباید اطلاعاتی در مورد داده اصلی را فاش نماید.روش های مختلف تولید شاخص باید از یک سو کارایی پرس و جو و از سوی دیگر عدم سوءاستفاده کارگزار از مقدار شاخص در استنتاج داده اصلی را در نظر بگیرند.

اسلاید 23: جستجوی مبتنی بر شاخص(Ai1, Ai2, …, Ain) Ri در پایگاه داده رمز نشده به Rki (Counter, Etuple, I1, I2, . . ., In) در پایگاه داده رمز شده نگاشت می شود. Counter کلید اصلی جدول رمز شده، Etuple رمز شده چندتایی معادل در پایگاه داده رمزنشده، I1 تا In شاخص های متناظر با Ai1 تا Ain هستند.

اسلاید 24: روش های اصلی مبتنی بر شاخصBucket Based IndexHash Based IndexB+ Tree Index24

اسلاید 25: شاخص مبتنی بر Bucket- معرفیهاسيگموس و همکارانش مبتنی بر افزودن شاخص مبتنی بر باکت، روشی برای پرس و جو روی داده رمز شده ارائه دادند.رديف‌هاي هر جدول به طور جداگانه و به کمک يکي از الگوريتم‌هاي رمزنگاري متقارن، رمز مي‌شوند. به ازاي هر مشخصه‌ که جستجو روي آن انجام مي‌شود، يک مشخصه به نام شاخص به جدول اضافه مي‌گردد. YearAuthorTitleID2001Alfred J. MenezesHandbook of Applied Criptography123IYIAITIIDEnc_TupleΨΦΠΣ4%n+!~kl?7klm||fcapkmvk380($%

اسلاید 26: نحوه تعریف شاخص در روش Bucketبندیبراي ايجاد شاخص امن، بازه‌ي داده‌هاي هر مشخصه به تعدادي زيربازه تقسيم مي‌شود. بازه ها نباید اشتراک داشته باشند. ايجاد بازه‌ها مي‌تواند با استفاده از انواع روش‌هاي تقسيم‌بندي صورت گیرد.طول برابرتعداد اعضاي برابر به هرکدام از بازه‌ها مقداري تعلق مي‌گيرد.می توان از یک تابع توليد اعداد شبه تصادفي استفاده کرد. به اين ترتيب به ازاي تمام داده‌هايي که در يک زيربازه قرار مي‌گيرند، مقدار تعلق گرفته به زيربازه‌ی آنها در شاخص رمزشده قرار داده مي‌شود.

اسلاید 27: مثال – بازه بندی و اعطای شاخص

اسلاید 28: پرس‌وجو در شاخص دهی مبتنی بر Bucketپرس‌وجو در دو مرحله صورت مي‌گيرد: کارگزار سعي مي‌کند تا آنجا که امکان دارد پاسخ درستي برگرداندکارخواه نتيجه‌ي ارسالي کارگزار را رمزگشايي کرده و آنرا پردازش مي‌کند. در SQL یک پرس و جو می تواند با درخت‌هاي متفاوت که از نظر نتيجه يکسان هستند، نمايش داده شود. هاسیگموس جداسازی پرس و جو را (بخشی در سمت کارگزار و بخشی در سمت کارخواه) را با استفاده از درخت پرس‌وجو انجام داده است.

اسلاید 29: پرس و جو در شاخص دهی مبتنی بر Bucket (2)در روش هاسيگموس، درخت نمايشِ هر پرس‌و‌جو به دو قسمت تقسيم مي‌شود. بخش زیر عملگر رمزگشایی: کلیه اعمالی که می تواند در سمت کارگزار انجام شود. بخش بالای عملگر رمزگشایی: اعمالی که باید در سمت کارخواه انجام شوند. اَعمال جبر رابطه‌اي وقتي به زير عمل رمزگشايي برده مي‌شوند، بايد به اَعمال جديدي که روي داده‌هاي رمزشده قابل اجرا هستند، تبديل شوند. هاسيگموس جبر رابطه‌اي جديدي را براي اِعمال روي داده‌هاي رمزشده تعريف کرد.29

اسلاید 30: بهینه سازی اجرای پرس و جوπnameBooks.keeper = Keeper.idσTitle = “Cryptography”DKeeperSDBooksS فقط عملگر‌هایی که در زیر عملگر رمزگشایی هستند قابل اجرا در سمت کارگزار هستند در این اجرا هیچ عملگری قابل اجرا به روی کارگزار نیست. سربار ارتباطي و محاسباتي در سمت کارخواه بالا است. براي افزايش کارآيي بايد سعي کرد تا حد امکان، عملگرهاي رابطه‌اي را به زير عملگر رمزگشايي منتقل کرد.

اسلاید 31: اجرای بهینه پرس و جواَعمال تا حد امکان باید در سمت کارگزار انجام شود. رابطهSELECTION روي جدول Books به زير عملگر رمزگشايي برده شده است. براي بردن اين عملگر به زير عملگر رمزگشايي بايد آنرا تبديل به sσ که در جبر جديد هاسيگموس براي SELECTION روي جداول رمزشده و مشخصه‌هاي شاخص تعريف شده است، تبديل کرد. این اجرا از پرس‌وجو به دلیل اجرای برخی از عملگرها در سمت کارگزار اجرای کارایی است. DπnameσTitle = “Cryptography” Λ Books.keeper = keeper.idBookss.keepers = Keepers.idsKeeperSσsTitle = 0BooksS

اسلاید 32: مزایا و معایب روش باکت بندی برای تولید شاخصروش های مبتنی بر Bucket برای اجرای شروط تساوی مناسب هستند. Aij = v  Ij = βپرس و جوهای بازه ای نیز با کمی تغییر در این روش شاخص دهی قابل اجرا است. (Ij = β1 or β2 or …or βk ) Aij> v  مثال: شرط Salary>50000 در جدول صفحات قبل باید به شکل زیر تبدیل شود: Salarys=2 OR Salarys=10 OR Salarys=3 عدم امکان اجرای توابع تجمعی مانند SUM، MIN، MAX، Avg و ...هاسيگموس اين روش را تعميم داد و با استفاده از يک تابع همريخت اختفائی اجراي توابعي مثل جمع و ضرب را فراهم کرد.

اسلاید 33: مزایا و معایب روش باکت بندی برای تولید شاخص (2)وجود مقدار زیادی از داده های اضافی در نتایج کارگزار (به ویژه اگر اعمالی مانند پیوند در پرس و جو وجود داشته باشد)روش‌هايي براي بهبود و کاهش اشتباه‌هاي مثبت در روش هاسيگموس ارائه شده است.اين روش بيشتر براي داده‌هاي عددي کاربرد دارد و به کارگیری روش براي داده‌هاي رشته‌اي يا متني که دامنه‌ي داده‌ها بزرگ است، چندان مناسب نیست.در تعریف بازه برای داده‌های رشته‌ای، ممکن است تعداد زیادی داده‌‌ در یک بازه قرار گیرد که این خود به معنای ارسال تعداد زیادی داده‌ي اضافی در پاسخ به يک پرس‌وجو و در نتیجه سربار ارتباطي و محاسباتي بالا است.اگر بازه ها طوری ساخته شوند که مثلاً در هر بازه یک مقدار قرار بگیرد امکان تحلیل فرکانسی وجود دارد.33

اسلاید 34: شاخص مبتنی بر توابع درهم سازاز مفهوم توابع درهم ساز برای ساختن شاخص استفاده می شود. براي ساختِ شاخص در این روش، داده‌ها توسط یک تابع درهم‌سازِ دارای تصادم دسته‌بندی می‌شوند. مزيت این نوع شاخص دهی نسبت به روش باکت بندی این است که دسته‌بندي روي داده‌هاي پشت سر‌هم انجام نمي‌شود که این مي‌تواند باعث افزايش امنيت گردد.

اسلاید 35: شاخص مبتنی بر توابع درهم ساز (2)اکر ri رابطه ای با اسکیمای Ri(Ai1, Ai2, . . . , Ain) و rkiرابطه متناظر رمز شده آن باشد، برای هر صفت Aij در Ri که بخواهیم برای آن شاخص تعریف کنیم، تابع درهم ساز یک طرفه h: Dij  Bij تعریف می شود که Dij دامنه Aij و Bij دامنه شاخص Ij متناظر با Aij است. for all x, y in Dij; if x = y then h(x)= h(y)برد h از دامنه آن کوچکتر است .امکان برخورد وجود دارد.برای هر دو مقدار تصادفی متفاوت ولی نزدیک به هم x و y در دامنه Dij (| x − y |< ε) ، توزیع احتمالی h(x) − h(y) یکنواخت است. تابع درهم ساز ترتیب خصیصه در دامنه را حفظ نمی کند.

اسلاید 36: شاخص مبتنی بر توابع درهم ساز – ویژگی هااجرای پرس و جوهای تساوی (مانند روش های شاخص دهی مبتنی بر bucket) ممکن است.هر شرط Aij=v به شرط Ij=h(v)، که Ij شاخص متناظر با Aij در جدول رمز شده است، تبدیل می شود.برخورد در توابع درهم ساز باعث ارسال چندتایی های اضافی به سمت کارخواه می شود. تابع درهم ساز فاقد برخورد مشکل ارسال نتایج زیادی به کارخواه را رفع می کند ولی احتمال تحلیل های فرکانسی را افزایش می دهد.مشکل اصلی روش های شاخص دهی مبتنی بر توابع درهم ساز عدم پشتیبانی از پرس و جوهای بازه ای است.دامياني و همکارانش براي اضافه ‌کردن قابليت انجام جستجوي بازه‌اي به این روش از شاخص مبتنی بر درخت B+ در کنار این نوع شاخص دهی استفاده کردند. 36

اسلاید 37: شاخص مبتنی بر درخت B+یکی از روش های شاخص دهی استفاده از ساختار داده ای درخت B+ است. در درخت B+، گره های داخلی به طور مستقیم به چندتایی ها در پایگاه داده اشاره نمی کنند بلکه به سایرگره ها در ساختار اشاره می نمایند. گره های برگ مستقیماً به چندتایی هایی در پایگاه داده با مقادیر مشخص برای صفت شاخص اشاره می کنند درخت B+ می تواند برای هر صفت Aij در اسکیمای Ri که در شروط پرس و جو ظاهر می شود، تعریف شود.شاخص توسط کارخواه روی مقادیر رمز نشده صفت ساخته شده و سپس روی کارگزار همراه با پایگاه داده رمز شده ذخیره می گردد. ساختار درخت B+ به جدولی با دو صفت شناسه گره و محتوای گره تبدیل می شود. این جدول برای هر گره یک ردیف دارد.

اسلاید 38: مثال38

اسلاید 39: روش ارزیابی پرس و جو در درخت B+فرض کنيد، کارخواه اجراي پرس‌وجويي با شرط A > v را درخواست کرده که v يک مقدار ثابت است. کارخواه بايد درخت B ذخيره شده روي کارگزار را براي يافتن محل v، پيمايش کند. کارخواه درخواستي براي دريافت ريشه‌ي درخت B انجام مي‌دهد.(ريشه‌ي درخت، رديفِ با شماره‌ي 1 است.) اين رديف به کارخواه ارسال و در آنجا رمزگشايي و پردازش مي‌شود. با توجه به مقدار v، گره‌ي بعدي‌ که بايد پيمايش شود انتخاب شده و درخواستی مبني بر ارسال آن گره به کارگزار فرستاده مي‌شود. اين روند تا پيدا کردن برگ حاوي v ادامه پيدا مي‌کند. پس از پيدا شدن v، تمام برگ‌هاي بعد از آن به سمت کارخواه ارسال مي‌شوند. اين گره‌ها در سمت کارخواه رمزگشايي شده و شماره‌ي رکورد‌هاي مورد نظر پيدا شده به سمت کارگزار ارسال مي‌شود.

اسلاید 40: شاخص مبتنی بر درخت B+- ویژگی هادرخت B+ در پاسخ به پرس و جو، چندتایی اضافی به سمت کارخواه نمی فرستد. هزینه ارزیابی شرایط پرس و جو برای کارخواه نسبت به روش های مبتنی بر باکت و توابع درهم ساز بسیار بیشتر است. به همین دلیل معمولاً درخت B+ را در کنار یکی از روش های شاخص دهی مبتنی بر باکت یا توابع در هم ساز بکار برده و از درخت B+ تنها در هنگام ارزیابی بازه ها در پرس و جو ها استفاده می نمایند. با توجه به این که محتوای درخت B+ در سمت کارگزار رمزنگاری شده است، این روش در برابر حملات استنتاجی نیز مقاوم است.40

اسلاید 41: جستجوی مبتنی بر شاخص در داده های رشته ای روشی مبتنی بر شاخص برای پرس و جو روی داده های رشته ای توسط Wang ارائه شده است (2004). با استفاده از روش وانگ، مي‌توان به جستجوي الگوهاي دلخواه در داده‌هاي رمزشده پرداخت.ریزدانگی رمزنگاری در روش Wang، در سطح فیلد است.

اسلاید 42: مراحل رمزنگاری به هر رشته S که از n کاراکتر c1c2…cn تشکيل شده است، مقدار شاخصی به طول m بيت اختصاص داده مي‌شود. هر رشته‌ی S = c1c2…cn به رشته‌ی S= s1s2…s2n-2 که در آن si = cici+1 است، بسط داده می‌شود. با استفاده از تابع درهم‌ساز h، مقداري بین 0 تاm براي هر کدام از si ها به دست مي‌آيد. اگر مقدار h(si) برابر با k باشد. در آن صورت بيت شماره kام در شاخص مربوطه برابر با يک مي‌شود.42

اسلاید 43: مثالS1= (abcehklst) m=16تابعی در هم ساز دوتایی های ab، bc، ...، و st را به عددی بین 0 تا 15 نگاشت می کند. S2=Index(abcehklst)= (0010100010101001)2هشت رشته 2 تایی وجود دارد در حالیکه 6 بیت یک در S2 دیده می شود. یعنی برخی از کاراکترهای دوتایی به یک مقدار توسط h نگاشت می شوند. 43

اسلاید 44: روش جستجومقدار رشته‌ای موجود در الگوی رشته ای مورد پرس و جو بسط داده می‌شود و مقادیر اختصاص داده شده توسط تابع h به هر دو حرف متوالی آن به دست می‌آید. پرس و جو روی مقدار رشته ای به پرس و جو روی شاخص (رشته بیتی) تبدیل می شود.مقادیر به دست آمده، مکان بیت‌هایی از مقادیر شاخص را که باید 1 باشند تا شرط پرس‌وجو ارضاء شود، مشخص می‌کند. این مقادیر به سمت کارگزار ارسال می‌شوند. کارگزار به ازای هر مقدار شاخص، مقادیر بیت‌های آن در مکان‌های ارسال شده را بررسی می‌کند، اگر همه دارای مقدار 1 بودند، مقدار شاخص را به عنوان یکی از جواب‌ها به سمت کارخواه برمی گرداند. در جواب های ارسال شده ممکن است نتایج اضافی وجود داشته باشد که باید توسط کارخواه مجدداً پردازش شده تا جواب دقیق به دست آید.

اسلاید 45: حالت های مختلف پرس و جوی رشته ایتطبیق دقیقشرط attribute=value روی جدول رمز نشده تبدیل می شود به = index (value) aS که aS مقدار رمز شده attribute در سمت کارگزار است. تطبیق الگوییشرط attribute LIKE value روی جدول رمز نشده:a like c0c1…ck => ((as)H(c0c1)=1 AND (as)H(c1c2)=1 AND … AND (as)H(ck-1ck)=1) پرس و جوی با شرایط بولی(attribute=value 1) OR (attribute=value 2), (attribute like value 1) AND (attribute like value 2), (attribute like value 1) AND NOT (attribute like value 2)از حالت اول و دوم قابل استنتاج است.

اسلاید 46: مثالselect eid, age from employee where did like ‘chess’Transforms toselect * from employeeE where (didsH(ch)=1) and (didsH(he)=1) and (didsH(es)=1) and (didsH(ss) =1)46

اسلاید 47: تحلیل روشدر این روش، در صورتي که طول m بزرگ انتخاب شود، حمله متن اصلی معلوم محتمل است. هر زوج کاراکتر به مقدار یکتایی در شاخص منتسب می شوند و امکان تحليل فرکانسي و شکستن شاخص وجود دارد.در صورت کوچک بودن m، تعداد زیادی داده اشتباه به سمت کارخواه ارسال خواهد شد.در جدول رمز شده فیلد اضافه ای برای شاخص باید در نظر گرفته شود که حجم آن به اندازه شاخص (m) وابسته است. در صورتی که n فیلد نیاز به رمز شدن داشته و طول شاخص به طور متوسط m بیت باشد، میزان فضای اضافی مورد نیاز m*n بیت برای شاخص است. 47

اسلاید 48: جمع بندی روش ها ی مبتنی بر شاخصتحقیقات زیادی روی این گونه روش ها صورت گرفته و دارای زمینه تئوریک قوی می باشند. حتی دارای جبر رابطه ای مخصوص می باشند. بیشتر فرایند اجرای پرس و جو بر روی کارگزار متمرکز است. هزینه ذخیره سازی تقریباً دو برابر ذخیره سازی معمولی است. زیرا غیر از مقدار رمز شده ذخیره، مقدار شاخص نیز ذخیره می گردد.امکان استنتاج و افشای اطلاعات وجود دارد که میزان آن وابسته به تعریف شاخص است. Evdokimov و همکارانش اثبات کرده اند که تقریباً تمام روش های مبتنی بر شاخص ذاتاً امن نیستند. به ویژه روشهایی که در پاسخ به پرس وجو چندتایی های اضافی تولید نمی کنند، در معرض تهدید افشای اطلاعات قرار دارند.پرس و جوهای شامل پیوند در این روش قابل اعمال است. پرس و جوهای تساوی، و الگویی برای داده های عددی و رشته ای قابل انجام است.امکان اجرای پرس و جوهای بازه ای بسته به تعریف شاخص دارد.امکان اجرای پرس و جوهای شامل توابع تجمعی وجود ندارد.چون با تغییر توزیع داده ها نیاز به دسته بندی مجدد داده ها برای تعریف شاخص وجود دارد، این روش بیشتر برای داده های فقط خواندنی مناسب است.

اسلاید 49: روش های مبتنی بر کاربرد توابع همریخت اختفاییتوابع همریخت اختفایی نوعی توابع برای رمزنگاری است.در روش رمزنگاری همريخت اختفایی (privacy homomorphism)، حاصل انجام يک عمل روي داده‌هاي رمزشده، معادل رمزشده حاصل عملي ديگر روي داده‌هاي اصلي است. β(xE , yE) = (α(x,y))E E(x) . E(y) = E(x+y)بوسيله‌ي توابع رمزنگاري همريخت اختفائی مي‌توان برخي از عمليات مانند جمع و ضرب را به طور مستقيم روي داده‌هاي رمزشده انجام داد. فیلدهایی را که روی آنها پرس و جوی تجمعی اجرا می شود، با استفاده از رمزنگاری همریخت رمز می کنند.

اسلاید 50: روش هاسیگموسهاسيگموس با استفاده از يک تابع رمزنگاري همريخت اختفائی که دو خاصيت جمعي و ضربي را پشتیبانی می کند، توابع جمع و ضرب را روي داده‌هاي رمزشده اجرا کرد. خواص تابع رمزنگاری همومورفیسم استفاده شده:کلید رمزنگاری K=(p, q) که p و q به وسیله کاربر تعیین می شوند. n = p.q که به کارگزار داده می شود qq-1 =1 (mod p) pp-1 = 1 (mod q)Ek(a mod p, a mod q)

اسلاید 51: مثالp = 5 , q = 7n = p.q = 35 k = (5, 7)می خواهیم a1 = 8 و a2 = 12 را جمع کنیمE(a1) = (3,1) E(a2) = (2,5)E (a1) + E (a2) = (3+2, 1+5) = (5, 6)D (5, 6) = 5*qq-1 + 6*pp-1 (mod 35) = (5*7*3 + 6*5*3) (mod 35) =195 (mod 35) = 20

اسلاید 52: مشکل استنتاجاستفاده از تابع رمزنگاري همريخت اختفائیِ معرفي شده کاملاً امن نيست و کارگزار مي‌تواند مقدار اصلي برخي از مقادير رمزشده را به دست آورد. فرض کنيد، x و y دو عدد باشند که به صورت (xp,xq) و (yp,yq) رمز شده‌اند. اگر z=x.y باشد، رابطه‌ي (zp,zq)=(xp,xq).(yp,yq) نيز بين مقادير رمزشده اين متغيرها وجود دارد. در چنين حالتی کارگزار مي‌تواند مقادير اصلي اين متغيرها را به دست آورد. کارگزار شروع به جمع کردن (xp, xq) با خودش مي‌کند و اين کار را آنقدر ادامه مي‌دهد تا نتيجه آن با (zp, zq) برابر شود. تعداد اين جمع کردن‌ها برابر با عدد y است.هاسيگموس با اضافه کردن نويز تصادفي به مقادير رمزشده، مشکل را حل می کند. R(x) يک تابع شبه تصادفي است.نويز در هنگام رمزگشايي از داده‌ها حذف مي‌شود.

اسلاید 53: روش های رمزنگاری مبتنی بر حفظ ترتیبدر روش های رمزنگاری با حفظ ترتیب (Order Preserving) داده ها به گونه ای رمز می شوند که ترتیب داده ها پس از رمز شدن با ترتیب داده های اصلی یکسان باشد. این نوع رمزنگاری برای اجرای پرس و جو های بازه ای مناسب است. آگراوال برای رمزنگاری داده های عددی و اجرای پرس و جوهای بازه ای روی آنها از این روش استفاده کرده است. فرض کنيد، داده‌هاي اصلي داراي توزيع اوليه A هستند. اين داده‌ها به نحوي رمز مي‌شوند، که علاوه بر حفظ ترتيب از توزيع دلخواه A تبعيت کنند. ابتدا داده‌ها به توزيع يکنواخت f نگاشت شده و سپس توزيع f به توزيع هدف A نگاشت مي‌شود.

اسلاید 54: مراحل رمزنگاریOPES در سه مرحله کار مي‌کند.(Order Preserving Encryption Scheme)مدل کردن: داده‌هاي اصلي به تعدادي دسته تقسيم مي‌شوند و توزيع داده‌هاي هر دسته مدل مي‌شود. روش هایی برای تعیین تعداد دسته ها و طول هر دسته وجود دارد.افزايش دسته‌ها منجر به افزايش هزينه‌هاي مدل مي‌شود.مسطح کردن: داده‌های اصلي P به داده‌های مسطح F به قسمي تبديل شود که مقادير F داراي توزيع يکنواخت باشند. در مرحله‌ي مسطح کردن براي هر دسته، يک تابع نگاشت M ايجاد مي‌شود. تابع ‌M هر دسته را به دسته‌اي با توزيع يکنواخت نگاشت مي‌کند.دو مقدار متفاوت در داده های اصلي هميشه به دو مقدار متفاوت از فضاي مسطح شده نگاشت شوند.تغيير: داده‌های مسطح F به داده‌های رمزشده C تبديل مي‌شود، به قسمي که مقادير C داراي توزيع نهايي که براي داده‌هاي رمزشده در نظر گرفته شده بود، باشند.

اسلاید 55:

اسلاید 56: ویژگی های روش رمزنگاری با حفظ ترتیباجرای پرس و جوها در این روش چندتایی های اضافی به سمت کارخواه ارسال نمی کند. امنیت در این روش زمانی تامین می شود که کارگزار/حمله کننده اطلاعاتی در مورد پایگاه داده اصلی و یا دامنه صفت ها نداشته باشد. این روش در مقابل حمله متن اصلی معلوم آسیب پذیر است.56

اسلاید 57: پایان57