פרוטוקול פייגה-פיאט-שמיר
פרוטוקול קריפטוגרפי / ויקיפדיה האנציקלופדיה encyclopedia
בקריפטוגרפיה, שיטת פייגה-פיאט-שמיר (Feige-Fiat-Shamir) בקיצור FFS היא סוג של פרוטוקול הוכחה באפס ידיעה מקבילי שפותח על ידי אוריאל פייגה, עמוס פיאט ועדי שמיר ב-1988 לצורך אימות זהויות ברשת, במקום שיטת האימות הקונבנציונלית באמצעות סיסמה. ככל הוכחה באפס ידיעה, פרוטוקול פייגה-פיאט-שמיר מאפשר למשתתף אחד להוכיח בפני המשתתף האחר ידיעת סוד מבלי הצורך לחשוף בפניו אף לא רמז קל בנוגע לסוד עצמו שלא ניתן היה להשיג באמצעים אחרים. גרסה דומה של הפרוטוקול מתאימה גם לצורך חתימה דיגיטלית.
פרוטוקול פייגה-פיאט-שמיר הוא הרחבה של פרוטוקול פיאט-שמיר הבסיסי[1] שפיתחו ב-1986 המיישם את רעיון אפס ידיעה ומשתמש בקושי המשוער שבמציאת שורש ריבועי מודולו שלם פריק, כאשר גורמיו הראשוניים אינם יודעים, שהיא כידוע בעיה מתמטית קשה. השימוש בבעיה זו כבסיס לפרוטוקול אימות כבר עלה כשנתיים קודם לכן על ידי פישר, מכלי ורקוף ביורוקריפט 84[2], אולם פרוטוקול פיאט-שמיר משופר יותר. חסרונו היחידי הוא בכך שבכל סבב מועברת סיבית אתגר אחת בלבד, מסיבה זו כדי להגיע לרמת בטיחות סבירה יש צורך במספר גדול מאוד של סבבים, מה שהופך את האלגוריתם ללא יעיל. לעומתו פרוטוקול זה משתמש במחרוזת סיביות אתגר בו זמנית בכל סבב ועל כן יעיל יותר.
פרוטוקול פייגה-פיאט-שמיר מתאים לשימוש כאמצעי לאימות זהויות המוטמע בכרטיס חכם או כל מתקן נייד אחר המכיל מעבד קטן שמסוגל לבצע חישובים בהיקף מצומצם. אף על פי שהפרוטוקול משתמש באריתמטיקה מודולרית צורך משאבי מחשוב קטנים יחסית ל-RSA ומתאים למימוש במתקנים ניידים.