זכייה של בני אפלבאום ועופר שייביץ ב ERC

קריפטוגרפיה בסיבוכיות נמוכה (בני אפלבאום).

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

תורת האינפורמציה במודלים אינטראקטיביים מוגבלי סיבוכיות (עופר שייביץ).

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