2. ביני לביני, ביום 1.2.2016 הודיע שר הפנים דאז לזיוד על כוונתו לפעול לביטול אזרחותו על פי סעיף 11(ב)(2) לחוק האזרחות. בהודעה נכתב כי מעשיו של זיוד בוצעו "תוך ניצול חופש התנועה בישראל, אשר התאפשרה ל[ו] כתוצאה מנשיאת תעודת זהות ישראלית". הוועדה המייעצת לשר הפנים לפי סעיף 11(ח) לחוק (להלן: הוועדה המייעצת) המליצה פה אחד ביום 29.3.2016 לפעול לביטול אזרחותו של זיוד, וביום 24.5.2016 אישר היועץ המשפטי לממשלה את הגשת הבקשה, כדרישת סעיף 11(ג) לחוק, בציינו כי הנחה את הפרקליטות "לפעול להגשת הבקשה בהקדם, עובר ליום 1.6.2016, וזאת על מנת שדבר קיומה יעמוד בפני בית המשפט המחוזי בחיפה במועד גזר הדין".
3. ביום 29.5.2016, ימים ספורים לפני מתן גזר הדין בהליך הפלילי, הגיש שר הפנים לבית המשפט לעניינים מנהליים בחיפה את הבקשה לביטול אזרחותו של זיוד. בעקבות הגשת הבקשה, פנו באי כוחו של זיוד ביום 6.6.2016 לשר הפנים וטענו כי הבקשה מעלה חשש לאכיפה בררנית. על כן הם ביקשו לקבל פרטים על אודות כל המקרים שבהם בוטלה אזרחות מטעמים של "הפרת אמונים" על פי נוסחיו השונים של החוק. בתשובת שר הפנים נמסר כי אזרחות ישראלית נשללה בגין הפרת אמונים בשני מקרים בלבד, שניהם בשנת 2002 – במקרה הראשון מדובר היה בחבר בארגון החמאס שהשתתף בביצוע עבירות ביטחון חמורות; ובמקרה השני מדובר היה בפעיל בארגון החיזבאללה שהיה מעורב באופן מתמשך "בייזום פעילות טרור כנגד יעדים ומטרות ישראליות". לא למותר לציין כי באותם מקרים נשללה האזרחות מכוח סעיף 11(ב)(2)
--- סוף עמוד 6 ---
לחוק בנוסחו הקודם, אשר העניק את סמכות הביטול לשר הפנים, והחלטתו בעניינם לא נתקפה בערכאות שיפוטיות. בשנת 2008 נחקק חוק האזרחות (תיקון מס' 9), התשס"ח-2008, ס"ח 810 (להלן: תיקון מס' 9) שהעביר את סמכות ההחלטה על ביטול האזרחות מחמת הפרת אמונים לבית המשפט לעניינים מנהליים, ומאז לא הוגשה אף בקשה מטעם שר הפנים לביטול אזרחות מחמת הפרת אמונים, עד שהוגשו בשנים 2015 ו-2016 שתי הבקשות נושא הערעורים דנן.
לאחר הגשת הבקשה בעניינו של זיוד, תוקן פעמיים סעיף 11(ב)(2) לחוק האזרחות – תיקון מס' 12 לחוק מיום 23.6.2016 קבע כי "הפרת אמונים" תיבחן לפי הגדרת "מעשה טרור" כהגדרתו בחוק המאבק בטרור, התשע"ו-2016 (להלן: חוק המאבק בטרור), חלף ההפנייה להגדרה בחוק שקדם לו – חוק איסור מימון טרור, התשס"ה-2005 (להלן: חוק איסור מימון טרור); ותיקון מס' 13 לחוק מיום 16.3.2017 קבע, בין היתר, כי הסמכות להחליט על סוג רישיון הישיבה שיוענק למי שייוותר חסר אזרחות בשל ביטול אזרחותו תהא בידי שר הפנים, במקום בידי בית המשפט.