رمزگذاری همومورفیک

رمزگذاری همشکل یا همومورفیک یا (homomorphic encryption) نوعی رمزگذاری است که اجازه محاسبات بر داده های رمزگذاری شده , بدون شکستن رمز انها از قبل , را میدهد. کلمه هموموفیک به هم شکلی در جبر اشاره دارد: توابع رمزگذاری و رمزگشایی را می توان به عنوان هم شکلی بین فضاهای متن ساده و متن رمزی در نظر گرفت. محاسبه حاصل نیز در حالت رمز گذاری شده باقی میماند که بعد از رمزنگاری با جواب درست مطابق است.رمزگذاری هممورفیک را می توان به عنوان توسعه ای برای رمزنگاری کلید عمومی در نظر گرفت.

رمزنگاری همومورفیک می تواند تعداد نامعلومی از محاسبات را به طور مستقیم روی اطلاعات رمزگذاری شده بدون آشکار کردن کلید های سری انجام دهد.

با این حال که رمزگاری همومورفیک در برابر حملات کانال جانبی حفاظتی ندارد , میتوان از ان برای نگهداری مطمین از منابع و محاسبات خارجی استفاده کرد.این به داده اجازه این را می دهد که درحالی که رمزنگاری نشده به خدمت سرویس های خارجی گرفته شود.

به عنوان یک مثال : یک عکاس میتواند عکسش را برای سنجش علاقه اسکن کند , کانال های جانبی متوجه میشوند که عکسی در سرور رد و بدل شده اما نمیتوانند محتوای داخل عکس را ببینند. در نتیجه از حمله مهاجمان حین پردازش داده جلوگیری میشود.

## گونه ها
رمزگذاری هممورفیک شامل انواع مختلفی از طرح های رمزگذاری است که می تواند طبقات مختلف محاسبات را روی داده های رمزگذاری شده انجام دهد. محاسبات به صورت مدارهای بولی یا محاسباتی نمایش داده می شوند. برخی از انواع رایج رمزگذاری هممورفیک عبارتند از: رمزگذاری همومورفیک قدری، همومورفیک  حدودی، همومورفیک مسطح و رمزگذاری هممورفیک کامل:

* رمزگذاری همومورفیک قدری شامل طرح‌هایی است که از ارزیابی مدارهایی که فقط از یک نوع گیت تشکیل شده‌اند، مانند جمع یا ضرب، پشتیبانی می‌کنند.

* طرح های رمزگذاری حدودی هم شکل می توانند دو نوع گِیت را ارزیابی کنند، اما فقط برای زیر مجموعه ای از مدارها.

* رمزگذاری همومورفیک کاملا مسطح از ارزیابی مدارهای دلخواه متشکل از انواع مختلف دروازه با عمق محدود (از پیش تعیین شده) پشتیبانی می کند.

* رمزگذاری هممورفیک کامل (FHE) امکان ارزیابی مدارهای دلخواه متشکل از انواع مختلف دروازه با عمق نامحدود را فراهم می کند و قوی ترین مفهوم رمزگذاری همومورفیک است.

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

## تاریخچه
شما های رمزگذاری همومورفیک با استفاده از رویکردهای مختلف توسعه یافته‌اند. به طور خاص، طرح‌های رمزگذاری کاملاً هم شکل اغلب به نسل‌های مربوط به رویکرد اساسی گروه‌بندی می‌شوند.

### '''قبل از FHE'''
مشکل ساخت یک طرح رمزگذاری کاملاً هم شکل برای اولین بار در سال 1978، در عرض یک سال پس از انتشار طرح RSA مطرح شد. برای بیش از 30 سال، مشخص نبود که آیا راه حلی وجود دارد یا خیر. در طی آن دوره، نتایج جزئی شامل طرح‌های زیر بود:

سیستم رمزنگاری RSA (تعداد نامحدود ضرب‌های مدولار)

سیستم رمزگذاری الگامال (تعداد نامحدود ضرب مدولار)

سیستم رمزنگاری Goldwasser–Micali (تعداد نامحدود انحصاری یا عملیات)

سیستم رمزگذاری Benaloh (تعداد نامحدود اضافات مدولار)

سیستم رمزنگاری Paillier (تعداد نامحدود اضافات مدولار)

سیستم Sander-Young-Yung (پس از بیش از 20 سال مشکل مدارهای عمق لگاریتمی را حل کرد)

سیستم رمزنگاری Boneh–Goh–Nissim (تعداد نامحدود عملیات جمع اما حداکثر یک ضرب)

سیستم رمزنگاری Ishai-Paskin (برنامه های انشعاب با اندازه چند جمله ای)

### نسل اول
کریگ جنتری، با استفاده از رمزنگاری مبتنی بر شبکه، اولین ساخت و ساز قابل قبول برای یک طرح رمزگذاری کاملا هممورفیک را در سال 2009 توصیف کرد. طرح جنتری از هر دو عملیات جمع و ضرب در متون رمزی پشتیبانی می کند که از آنها می توان مدارهایی را برای انجام محاسبات دلخواه ساخت. ساخت و ساز از یک طرح رمزگذاری تا حدی هم شکل شروع می شود، که محدود به ارزیابی چند جمله ای های درجه پایین بر روی داده های رمزگذاری شده است. محدود است زیرا هر متن رمزی به نوعی نویز دارد، و این نویز با افزودن و ضرب متون رمزی افزایش می‌یابد تا اینکه در نهایت نویز باعث می‌شود متن رمزی به دست آمده غیرقابل کشف باشد.

سپس جنتری نشان می‌دهد که چگونه می‌توان این طرح را کمی تغییر داد تا قابل راه‌اندازی باشد، یعنی بتواند مدار رمزگشایی خود را ارزیابی کند و سپس حداقل یک عملیات دیگر را ارزیابی کند. در نهایت، او نشان می‌دهد که هر طرح رمزگذاری تا حدی هممورفیک قابل راه‌اندازی را می‌توان از طریق یک خود جاسازی بازگشتی به یک رمزگذاری کاملاً هممورفیک تبدیل کرد. برای طرح "پر سر و صدا" Gentry، رویه bootstrapping با اعمال روش رمزگشایی به صورت هممورفیک، متن رمز را به طور موثر "نوسازی" می کند، در نتیجه یک متن رمزی جدید به دست می آید که همان مقدار قبلی را رمزگذاری می کند اما نویز کمتری دارد. با "بازسازی" متن رمز به طور دوره ای هر زمان که نویز بیش از حد بزرگ شود، می توان تعداد دلخواه جمع و ضرب را بدون افزایش بیش از حد نویز محاسبه کرد.

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

در سال 2010، مارتن ون دایک، کریگ جنتری، شای هالوی و وینود وایکونتاناتان دومین طرح رمزگذاری کاملا هممورفیک را ارائه کردند،  که از بسیاری از ابزارهای ساخت جنتری استفاده می کند، اما به شبکه های ایده آل نیاز ندارد. در عوض، آن‌ها نشان می‌دهند که مولفه تا حدودی هم شکل طرح شبکه‌ای ایده‌آل جنتری را می‌توان با یک طرح بسیار ساده تا حدودی هم شکل که از اعداد صحیح استفاده می‌کند جایگزین کرد. بنابراین این طرح از نظر مفهومی ساده‌تر از طرح شبکه ایده‌آل جنتری است، اما دارای خواص مشابه با توجه به عملیات و کارایی همومورفیک است. مولفه تا حدودی هم شکل در کار ون دایک و همکاران. شبیه به یک طرح رمزگذاری پیشنهاد شده توسط Levieil و Naccache در سال 2008،و همچنین به طرحی است که توسط Bram Cohen در سال 1998 پیشنهاد شد.

با این حال، روش کوهن حتی از لحاظ افزایشی هم شکل نیست. طرح Levieil-Naccache فقط از جمع ها پشتیبانی می کند، اما می توان آن را به گونه ای تغییر داد که از تعداد کمی از ضرب ها نیز پشتیبانی کند. بسیاری از اصلاحات و بهینه سازی های طرح ون دایک و همکاران. در دنباله‌ای از آثار ژان سباستین کورون، تانکرد لپوینت، اورادیپ ماندال، دیوید نکاشه و مهدی تیبوچی پیشنهاد شدند. برخی از این آثار شامل اجرای طرح‌های حاصل نیز می‌شد.

### نسل دوم
سیستم‌های رمزنگاری همومورفیک این نسل از تکنیک‌هایی مشتق شده‌اند که در سال‌های 2011-2012 توسط Zvika Brakerski، Craig Gentry، Vinod Vaikuntanathan و دیگران توسعه یافتند. این نوآوری ها منجر به توسعه سیستم های رمزنگاری بسیار کارآمدتر و کاملاً هممورفیک شد.

امنیت بیشتر این طرح‌ها بر اساس سختی مسئله (Ring) Learning With Errors (RLWE) است، به جز طرح‌های LTV و BLLN که بر یک نوع بیش از حد کشیده شده و از مسئله محاسباتی NTRU تکیه دارند. این نوع NTRU متعاقباً در برابر حملات شبکه زیرفیلد آسیب‌پذیر نشان داده شد، به همین دلیل این دو طرح دیگر در عمل استفاده نمی‌شوند.

همه سیستم‌های رمزنگاری نسل دوم هنوز از طرح اولیه ساختار اصلی جنتری پیروی می‌کنند، یعنی ابتدا یک سیستم رمزنگاری تا حدی همومورفیک می‌سازند و سپس آن را با استفاده از بوت استرپینگ  ( bootstrapping )به یک سیستم رمزنگاری کاملاً هم‌مورفیک تبدیل می‌کنند.

ویژگی متمایز سیستم های رمزنگاری نسل دوم این است که همه آنها دارای رشد بسیار آهسته تر نویز در طول محاسبات همومورف هستند. بهینه‌سازی‌های اضافی توسط کریگ جنتری، شای هالوی و نایجل اسمارت منجر به سیستم‌های رمزنگاری با پیچیدگی مجانبی تقریباً بهینه شد

یکی دیگر از ویژگی‌های متمایز طرح‌های نسل دوم این است که آنها برای بسیاری از برنامه‌ها حتی بدون احضار بوت استرپینگ به اندازه کافی کارآمد هستند، در عوض در حالت FHE تراز شده کار می‌کنند.

### نسل سوم
در سال 2013، کریگ جنتری، آمیت ساهای و برنت واترز ( اختصار سه اسم به GSW) تکنیک جدیدی را برای ساختن طرح‌های FHE پیشنهاد کردند که از یک مرحله گران قیمت «خطی‌سازی مجدد» در ضرب هم‌مورفیک جلوگیری می‌کرد. Zvika Brakerski و Vinod Vaikuntanathan  ناظر بودند که برای انواع خاصی از مدارها، سیستم رمزنگاری GSW دارای نرخ رشد حتی آهسته‌تری از نویز است و در نتیجه کارایی بهتر و امنیت قوی‌تری دارد. Jacob Alperin-Sheriff و Chris Peikert سپس یک تکنیک بوت استرئینگ بسیار کارآمد را بر اساس این مشاهدات وصف کردند.

این تکنیک‌ها بیشتر برای توسعه انواع حلقه‌های کارآمد سیستم رمزنگاری GSW بهبود یافتند: مثل FHEW (2014)  و TFHE (2016). طرح FHEW اولین طرحی بود که نشان داد با تازه کردن متون رمزی پس از هر عملیات، می توان زمان بوت استرپ را به کسری از ثانیه کاهش داد. FHEW روش جدیدی را برای محاسبه گیت های بولی بر روی داده های رمزگذاری شده معرفی کرد که بوت استرپ را تا حد زیادی ساده می کند و گونه ای از روش راه انداز را پیاده سازی می کند.کارایی FHEW توسط طرح TFHE، که یک نوع حلقه از رویه راه‌اندازی  را با استفاده از روشی مشابه روش FHEW پیاده‌سازی می‌کند، بهبود بیشتری یافت.

### نسل چهارم
در سال 2016، چئون، کیم، کیم و سونگ ( به اختصار CKKS )  یک طرح رمزگذاری هممورفیک حدودی را پیشنهاد کردند که از نوع خاصی از محاسبات نقطه ثابت پشتیبانی می‌کند که معمولاً به عنوان محاسبات نقطه شناور بلوکی از آن یاد می‌شود. طرح CKKS شامل یک عملیات تغییر مقیاس کارآمد است که یک پیام رمزگذاری شده را پس از ضرب کاهش می دهد. برای مقایسه، چنین مقیاس‌بندی مجددی نیاز به راه‌اندازی در طرح‌های BGV و BFV دارد. عملیات مقیاس‌گذاری مجدد، طرح CKKS را به کارآمدترین روش برای ارزیابی تقریب‌های چند جمله‌ای تبدیل می‌کند و رویکرد ترجیحی برای اجرای برنامه‌های یادگیری ماشینی حفظ حریم خصوصی است. این طرح چندین خطای حدودی را معرفی می کند، هم غیر قطعی و هم قطعی، که در عمل نیاز به رسیدگی ویژه ای دارند.

مقاله 2020 توسط Baiyu Li و Daniele Miciancio حملات غیرفعال علیه CKKS را مورد بحث قرار می دهد و پیشنهاد می کند که تعریف استاندارد IND-CPA ممکن است در سناریوهایی که نتایج رمزگشایی به اشتراک گذاشته می شود کافی نباشد. نویسندگان این حمله را به چهار کتابخانه رمزنگاری هممورفیک مدرن (HEAAN، SEAL، HElib و PALISADE) اعمال می‌کنند و گزارش می‌دهند که امکان بازیابی کلید مخفی از نتایج رمزگشایی در چندین پیکربندی پارامتر وجود دارد. نویسندگان همچنین استراتژی‌هایی برای  کاهش این حملات را پیشنهاد می‌کنند که شامل یک افشای مسئولیت‌پذیرانه هستند که این  نشان می‌دهد کتابخانه‌های رمزگذاری همومورفیک پیش از اینکه مقاله در دسترس عموم قرار گیرد، اقدامات کاهشی را برای حملات اجرا کرده‌اند. 
## منابع

* ویکی پدیا انگلیسی

رده:رمزنگاری