חידות מרקל – הבדלי גרסאות

נניח <math>N=2^n</math>, מהפרוטוקול עולה שהמאמץ הדרוש לאליס להכנת כל החידות הוא <math>O(N)</math>, כמו כן המאמץ הדרוש לבוב לפיענוח חידה אחת גם הוא <math>O(N)</math>. אולם עבור המצותת איב המאמץ הדרוש לפתרון חידה אחת הוא <math>2^n</math> וישנן <math>N</math> חידות, במקרה הממוצע עליה לפענח לפחות מחצית מהן, כלומר <math>1/2N\cdot O(N)</math> שזה <math>O(N^2)</math>. כלומר הוכח שקיים פער ריבועי של פקטור העבודה בין המשתתפים בפרוטוקול לבין המצותת, אך לא יותר מזה. מסיבה זו הפרוטוקול אינו יעיל, כיוון שלכל היותר מושג ביטחון ריבועי. למשל אם <math>N=2^{32}</math> ביטחון המערכת הוא רק <math>2^{64}</math>, שזה מעט ולא מצדיק את ההשקעה הדרושה מצד אליס ובוב. למרות זאת, עדיין אפשר לראות בשיטה כחלוצה ראשונה של תפישת המפתח הפומבי. רלף מרקל פיתח את שיטת החידות שלו כשהיה סטודנט ב[[אוניברסיטת ברקלי|ברקלי]], וכבר אז צפה את הפוטנציאל הטמון במערכת מפתח פומבי, אולם לא הכול עמדו על חשיבותה. מאוחר יותר, כאשר [[פרוטוקול דיפי-הלמן|דיפי והלמן]] פרסמו את עבודתם בנושא הצפנת מפתח ציבורי, ציינו שהרעיון של מרקל היווה בין היתר השראה עבורם לפיתוח מה שנודע לאחר מכן כפרוטוקול דיפי-הלמן שהוא כידוע, תגלית דרמטית שהשפיעה כמעט יותר מכולמאוד על הקריפטוגרפיה המודרנית.