הצפנת בלום-גולדווסר
ביטחון ויעילות

הצפנת בלום-גולדווסר ידועה כהצפנה אסימטרית בטוחה סמנטית בניגוד לשיטות אחרות כמו RSA ורבין. ההגדרה של ביטחון סמנטי היא שכל מה שניתן ללמוד בזמן ריצה פולינומי מהתבוננות בטקסט המוצפן בהינתן טקסט המקור, ניתן ללמוד גם ללא הטקסט המוצפן. במילים אחרות הסכימה תקרא בטוחה סמנטית אם אינה חושפת כל מידע ולו הקל ביותר אודות טקסט המקור שניתן לגלות בזמן פולינומי. למעשה זוהי גרסה חלשה של סודיות מושלמת, לפי שאנון שיטת הצפנה תקרא מושלמת אם יריב פסיבי אפילו בעל עצמת חישוב בלתי מוגבלת, לא יוכל ללמוד מאומה אודות טקסט המקור בהינתן טקסט-מוצפן בלבד, כיוון שכל טקסט יכול להיות המקור במידה שווה. ביטחון סמנטי לעומת זאת מוגבל ליריב בעל עצמת חישוב מוגבלת בזמן ומקום.
שיטת הצפנה דטרמיניסטית כמו RSA מכילה מטבעה מספר חולשות מהותיות:
היא אינה בטוחה עבור כל מסר במידה שווה (למשל במסרים קטנים מאוד, הצפנת הערך 0 או 1 תניב תוצאה זהה, כך שקל לזהות זאת).
קל לעיתים לחשב מידע חלקי אודות מקור הצופן מתוך הטקסט המוצפן. למשל ב-RSA ניתן לחשב את הסיבית הנמוכה ביותר של המסר על ידי חישוב סימן יעקובי.
הצפנה חוזרת של אותו המסר תניב תמיד תוצאה זהה. אפשר לזהות בקלות תעבורה של מסרים תדירים בעלי אופי מיוחד גם אם לא ניתן לקרוא את תוכנם.
אפשר להפוך כל שיטה דטרמיניסית לבטוחה סמנטית על ידי הוספת אקראיות למסר לפני תהליך ההצפנה. הכנת מסר באופן זה נהוגה למעשה כחלק מתקן מפתח פומבי של RSA ונקראת RSA-OAEP.
מספר בלום; המודולוס ייקרא מספר בלום אם הוא שלם פריק שהוא כפולה של שני ראשוניים שונים השקולים ל-3 מודולו 4. כלומר  \ p\equiv 3\ ({\mbox{mod }}4) אם קיים שלם  \ t כלשהו המקיים  \ p=4t+3. אלגוריתם בלום גולדווסר מיישם גרסה מובנית של המחולל הפסאודו האקראי BBS כאשר הסיביות הנמוכות של השארית הריבועית  \ x_{i}=x_{i-1}^{2}{\mbox{ mod }}n בכל סבב, משלימות את הרצף הפסאודו אקראי לצורך הצפנת המסר. השארית הריבועית האחרונה  \ x_{t+1}=x_{t}^{2}{\mbox{ mod }}n נשלחת באופן גלוי כאמור אל המקבל לצורך שחזור הגרעין ההתחלתי. בהנחה שפירוק לגורמים היא בעיה קשה, ניתן להוכיח כי  \ h הסיביות הנמוכות של  \ x_{t} בטוחות סימולטנית, כלומר אין דרך יעילה לחשב אותם מלבד ניחוש, מה שאומר שהמחולל נחשב לבטוח (כל עוד פירוק לגורמים היא בעיה קשה). כמובן הגדרה זו מוגבלת לביטחון חישובי בלבד.
בדומה לשיטת רבין, הצפנת בלום גולדווסר פגיעה להתקפת מוצפן-נבחר שבה תוקף מנסה לגלות את הגורמים הראשוניים של המודולוס ועל כן לגלות את המפתח הפרטי מתוך המפתח הפומבי. במודל זה ההנחה היא שלתוקף גישה למערכת המבצעת הצפנה ופענוח כקופסה שחורה, אין לו גישה למפתח הסודי עצמו אך באפשרותו לבחור מסרים אותם הוא מעוניין שהמערכת תפענח עבורו ולנתח את התוצאה. סיטואציה כזו אינה בלתי אפשרית במערכות מסוימות ולכן מהווה איום בלתי מבוטל.
הצפנת בלום גולדווסר יעילה מבחינה חישובית כיוון שהטקסט המוצפן המתקבל אינו גדול משמעותית מטקסט המקור, אלא במספר קבוע של סיביות (כגודל השלם  \ x_{t+1} בסיביות). תהליך ההצפנה יעיל ודורש רק הכפלה מודולרית (מודולו  \ n) אחת כדי להצפין  \ h סיביות, כלומר עבור מודולוס בגודל  \ k סיביות ומסר בגודל  \ l סיביות תהליך ההצפנה לוקח  \textstyle O({\frac {lk^{2}}{{\mbox{log}}\ k}}) פעולות בסיסיות. לעומת RSA למשל שדורשת העלאה בחזקה מודולרית מלאה במידה והמעריך נבחר אקראית. ללא אופטימיזציה העלאה בחזקה מודולרית מלאה דורשת בממוצע  \ 3k/2 פעולות כפל מודולריות כאשר  \ k שווה ללוגריתם בבסיס 2 של המודולוס. כמו כן תהליך הפענוח של אלגוריתם בלום גולדווסר דורש (בנוסף בשלב ההכנה) רק שלוש העלאות בחזקה מודולריות ללא תלות באורך המסר, יתר הפעולות דומות להצפנה, כלומר בסה"כ  \textstyle O(k^{3})+O({\frac {lk^{2}}{{\mbox{log}}\ k}}). מה שאומר שעבור מסרים גדולים, שיטת בלום גולדווסר יעילה יותר מ-RSA.