הצפנת בלום-גולדווסר – הבדלי גרסאות

==בטחוןביטחון ויעילות==

'''בטחוןביטחון סמנטי''' (Semantic security); הצפנת בלום-גולדווסר ידועה כהצפנה אסימטרית בטוחה סמנטית בניגוד לשיטות אחרות כמו RSA ורבין. ההגדרה של בטחוןביטחון סמנטי היא שכל מה שניתן ללמוד ב[[זמן ריצה פולינומי]] מהתבוננות בטקסט המוצפן בהינתן טקסט המקור, ניתן ללמוד גם ללא טקסט המקור. במילים אחרות סכימת הצפנה אסימטרית תקרא בטוחה סמנטית אם אינה מדליפה כל מידע ולו הקל ביותר אודות טקסט המקור שניתן לגלות בזמן פולינומי.

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

'''[[מספר בלום]]'''; המודולוס ייקרא מספר בלום אם הוא שלם פריק שהוא כפולה של שני ראשוניים שונים השקולים ל-3 מודולו 4. כלומר <math>\ p\equiv3\ (\mbox{mod }4)</math> אם קיים שלם <math>\ t</math> כלשהו המקיים <math>\ p=4t+3</math>. אלגוריתם בלום גולדווסר מיישם גרסה מובנית של המחולל הפסאודו האקראי BBS כאשר הסיביות הנמוכות של השארית הריבועית <math>\ x_i=x^2_{i-1}\mbox{ mod }n</math> בכל סבב, משלימות את הרצף הפסאודו אקראי לצורך הצפנת המסר. השארית הריבועית האחרונה <math>\ x_{t+1}=x^2_t\mbox{ mod }n</math> נשלחת באופן גלוי כאמור אל המקבל לצורך שחזור הגרעין ההתחלתי. בהנחה שפירוק לגורמים היא בעיה קשה, ניתן להוכיח כי <math>\ h</math> הסיביות הנמוכות של <math>\ x_t</math> בטוחות סימולטנית, כלומר אין דרך יעילה לחשב אותם מלבד ניחוש, מה שאומר שהמחולל נחשב לבטוח (כל עוד פירוק לגורמים היא בעיה קשה). כמובן הגדרה זו מוגבלת לבטחוןלביטחון חישובי בלבד.

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