חישוב בעיניים עצומות

בימינו, כאשר מכשירים ניידים כמו טלפונים סלולריים חכמים ומחשבי לוח משמשים כמחשבים זמינים בכל עת, השימוש במחשבים שולחניים הולך ופוחת. במקביל, השימוש במיחשוב ענן, שבו הפעולות החישוביות מתבצעות על רשת של שרתים מרוחקים, הולך
וגדל, וצפוי לגדול עוד יותר, עם התגברות הדרישה לכוח חישובי.

מגמות אלה מעלות מספר שאלות חשובות הנוגעות לביטחון מידע. האם נוכל, לדוגמה, לבצע חישובים על נתונים השמורים ברשת האינטרנט, מבלי לאפשר לאף אדם אחר לראות את המידע?
השימוש באמצעי מיחשוב אינטרנטיים, המבוססים על מיחשוב ענן, יוצרים פתח חדש לגניבת מידע, ועד כה לא פותחה שיטה יעילה וישימה להגנה על הנתונים.

"עד לפני מספר שנים אף לא ידעו בוודאות אם ההצפנה הנדרשת לסוג כזה של אבטחת מידע אפשרית בכלל", אומר ד"ר צביקה ברקרסקי, שסיים באחרונה את לימודי הדוקטורט בהנחיית פרופ' שפי גולדווסר, במחלקה למדעי המחשב ומתמטיקה שימושית במכון. הניסיון לבצע חישובים על מידע רגיש אשר מאוחסן על שרתים מרוחקים משאיר את המידע חשוף, כך ששיטות ההצפנה המסורתיות אינן יכולות להגן עליו. הבעיה העיקרית היא, שביצוע פעולות שונות על הנתונים מחייב לפענח את הקידוד שלהם. הפתרון שהוצע לבעיה זו הוא למצוא דרך להצפין את המידע, כך שהשרת יוכל לבצע את הפעולות הנדרשות כשהמידע עדיין מוצפן.

השרת לא יוכל "לראות" את הנתונים האמיתיים, אבל צריכים להיות לו האמצעים כדי לבצע עליהם פעולות חישוב ולהחזיר תוצאה מוצפנת - אותה אפשר יהיה לפענח מאוחר יותר, במקום בטוח. גישה זו מכונה "הצפנה הומומורפית מלאה" (FHE - fully homomorphic encryption). ההוכחה הראשונה להיתכנותה של הגישה הזו התקבלה בשנת 2009, כאשר קרייג ג'נטרי, תלמיד מחקר באוניברסיטת סטנפורד, פירסם את עבודת הדוקטורט שלו. השיטה שפיתח ג'נטרי היא ההדגמה הראשונה של הצפנה הומומורפית מלאה, אבל היא מסורבלת ודורשת זמן רב, ולכן קשה ליישמה. ג'נטרי בנה את המערכת שלו באמצעות מתמטיקה מתוחכמת יחסית, המבוססת על מה שמכונה "סריגים אידיאליים" (ideal lattices), דבר שדרש ממנו להניח הנחות סיבוכיות חדשות ולא מוכרות, כדי להוכיח את ביטחון המידע.

הבחירה של ג'נטרי, שימוש ב"סריגים אידיאליים" להצפנה הומומרפית, נראתה בלתי-נמנעת, ומדענים הניחו כי היא נחוצה לשרתים כדי לבצע פעולות בסיסיות, כמו חיבור וכפל של נתונים מוצפנים. ד"ר ברקרסקי, ביחד ד"ר וינוד וייקונטנטן (גם הוא תלמיד של פרופ' גולדווסר, מהמכון הטכנולוגי של מסצ'וסטס - MIT), הצליחו להפתיע את קהילת המדענים העוסקת באבטחת מידע, כאשר פירסמו השנה שני מאמרים, המתארים מספר שיטות חדשות אשר יאפשרו לייעל במידה ניכרת את ההצפנה ההומומורפית המלאה.

ראשית, הם הצליחו ליצור מערכת העובדת בשיטות אריתמטיות פשוטות, אשר מקצרות את הזמן הנדרש לעיבוד המידע. בנוסף, השיטה המשופרת שלהם אינה דורשת שימוש בסריגים אידיאליים, או בקביעת הנחות סיבוכיות חדשות, כדי להוכיח את בטיחות המידע.

"ג'נטרי השתמש ב'טריקים' שונים כדי לבצע מניפולציות בחומר המוצפן", אומר ד"ר ברקרסקי, "אבל הם בעייתיים". כך, לדוגמה, באחד מהטריקים, המדומה לפעילות המעגלית של אדם המושך את עצמו למעלה באמצעות שרוכי הנעליים, ומכונה bootstrapping, המידע עובר "פיענוח וירטואלי", ומוצפן מחדש בכל שלב של החישוב.

הדרישה מ"פיענוח וירטואלי" שכזה היא שהפיענוח האמיתי יהיה פשוט - דבר שאפשר להשיג באמצעות "טריק" אחר, המכונה "מעיכה" (squashing). אבל כך הופכת ההצפנה בה בעת למסובכת יותר ולבטוחה פחות."המאמר הראשון שכתבנו", מסביר ד"ר ברקרסקי, "עדיין התבסס על 'bootstrapping' ועל מעיכה, אבל בנוסף השתמשנו במספר 'טריקים' כדי לשלוט טוב יותר בגודל. חלק מהתהליכים של ג'נטרי מבוססים על גיאומטריה מסובכת, ואילו אנחנו הצלחנו לבצע את אותם תהליכים באמצעות אלגברה פשוטה".

במאמר השני הראו המדענים, כי למעשה אפשר לוותר לחלוטין על המעיכה. ממצאים אלה התקבלו בעקבות תגלית מפתיעה: אפשר לפשט את המבנה המתמטי המשמש ליצירת מפתח הצפנה מבלי להתפשר על בטיחות המידע המוצפן. הסריגים האידיאליים, בהם השתמש ג'נטרי, מורכבים מאוסף של נקודות שאותן אפשר לחבר זו לזו - כפי שקורה בסריגים רגילים (לא אידיאליים) - אבל אפשר גם להכפיל זו בזו.

המחקר הראה, כי אין הכרח להשתמש דווקא בסריגים אידיאליים, דבר שמפשט את המבנה המתמטי עד למצב שבו "מעיכה" אינה נדרשת כלל. "העובדה שמבנה כזה עובד הייתה בגדר קסם, והיא איתגרה את ההנחה המוקדמת שלנו בדבר הצורך בסריג אידיאלי בהצפנה הומומורפית", אומר ד"ר ברקרסקי.תוצאות אלה עשויות לסלול את הדרך לשימוש מעשי בהצפנה הומומורפית. גרסאות משופרות של המערכת החדשה עשויות להיות מהירות עשרות מונים - ואף אלפי מונים - מהמערכת הראשונית שפיתח ג'נטרי.

ואכן, בהמשך, הצליחו ד"ר ברקרסקי וד"ר וייקונטנטן לפתח את התיאוריה שעומדת בבסיס שיטת ההצפנה ההומומורפית שלהם עד לנקודה ממנה יוכלו מהנדסי מחשבים לפתח יישומים. בנוסף לשמירת מידע המצוי ברשת האינטרנט, או בענן מיחשוב, מעיניים לא רצויות, עשויה הצפנה הומומורפית מלאה לאפשר פעולות חדשות במידע, שהיו בלתי-אפשריות עד כה, כמו, לדוגמה, עיבוד בטוח של מידע רפואי רגיש. חולים יוכלו "לחשוף" מידע רפואי כשהוא מוצפן, וכך אפשר יהיה לבצע מחקרים רפואיים נרחבים לגבי הנתונים בצורה מוצפנת, מבלי לאפשר גישה למידע הרפואי של אנשים בודדים