Winning the Arab Miss Israel contest in 2009 was a double-edged sword for Naglaa Suleiman.The daughter of an Egyptian father and Arab-Israeli mother, Suleiman moved to Israel with her family at age five and grew up in Nazareth. The notoriety she gained as Miss Arab Israel at age 16 caught the attention of the Egyptian media which began a smear campaign against her as a dual Egyptian-Israeli national. Proud of her Egyptian identity, she refused to represent Israel in the Miss World pageant. Nevertheless, no Egyptian university would accept her because of her Israeli citizenship.Finally, on Nov. 10, 2015, then Egyptian Prime Minister Sherif Ismail revoked her Egyptian citizenship, ruling that she had failed to gain the proper permission from the Interior Ministry to be a dual national.Although Suleiman’s case as an Egyptian-Israeli beauty queen is unique, the problems she has faced as an Egyptian-Israeli are not.While there is no official count, the head of the community in Nazareth informed me that there are between 3,000 and 7,000 Egyptians living in Israel. Most are married to Muslim or Christian Israelis, with no more than 12 married to Jews. The community breaks down into three groups.The first comprises illegal ex-pats whose main objective is to save as much money as they can before returning to Egypt. The second group consists of permanent residents who pay taxes and enjoy full rights and benefits such as health care, social security, and participating in municipal elections. The third is made up of those who chose to become Israeli citizens despite the stigma surrounding it back in Egypt—including a possible lifetime ban on returning to their native country—primarily due to the advantages of holding an Israeli passport.The Egyptian community in Israel has its roots in the breakthrough peace treaty between Egypt and Israel in 1979, when hundreds of thousands of Israelis poured over the border to visit their southern neighbor. A boon to Israelis of all backgrounds, this was a profound moment for Arab-Israelis in particular, their first opportunity since the establishment of Israel to travel to surrounding Arab countries.Often, love blossomed along the Nile, as Arab Israelis and Egyptians found spouses from among their former adversaries. Some Egyptians married and traveled with their spouses to Israel, while others stayed to live in Egypt. For Arab Israelis to reside in Egypt, the Egyptian government had to grant permits that were renewed every three years. As time went on, the situation became more complicated, as these accommodations were granted for only six months. Eventually, Egyptian security authorities stopped granting visas at all, forcing Israeli spouses to leave the country and their families behind. Ultimately, many Egyptians moved to Israel with their children to reunite the family.Israel offers a hospitable environment. Upon arrival in Israel, Egyptians are granted six months of temporary residency but are not permitted to work. At the end of this period, they receive a temporary identification card, to be renewed every year, and are treated as Israeli citizens with benefits, including a work permit and health insurance. The only restriction: They are barred from voting in national elections.After five years, permanent residency is granted, opening the door to apply for Israeli citizenship. Most prefer not to obtain citizenship, as this would make their return to Egypt impossible and endanger their Egyptian citizenship. As an Egyptian supermarket owner in Nazareth told me, “When we go to the [Egyptian] embassy [in Tel Aviv] to renew our passports, you could feel they hardly accept our presence here, but as long as we did not take the Israeli citizenship they are fine.”Those Egyptians who obtained Israeli citizenship did so mainly because they lost hope of returning to Egypt. One Egyptian-Israeli businessman explained: “Traveling to Egypt from Ben-Gurion Airport is not the issue. Coming back is the problem. Egyptian airport authorities ask us to obtain a travel permit from the security apparatus in the country in order to be able to travel back to Israel.” Travel permits can take from one month to seven years because both the security and intelligence agencies have to sign off.One Egyptian who has an Israeli permanent residency told me, “I go back for two weeks to visit my family and see friends, but the only thing occupying my mind is whether I will be able to travel or not.” He explained: “They do not take into consideration that we have family in Israel who are dependent on us, have a mortgage to pay and other financial obligations that need to be taken care of alongside our wives. There have been cases in our community that people had their parents passed away but they could not go back for the funeral service since they know the authorities would give them a hard time coming back.”As a result of this process, Egyptians living in Israel began to find alternate ways to leave the Cairo airport without causing trouble. Instead of booking a direct flight to Tel Aviv, they would shoulder the extra expense of purchasing a round-trip ticket to Jordan, to convince authorities that they would return to Egypt. From Jordan, they would book flights to Tel Aviv.The problem becomes more complicated for children like Naglaa Suleiman, who receive Israeli citizenship automatically through their Israeli parent. Another man, the son of an Egyptian father and Arab-Israeli mother, was thrown out of Egypt with a 48-hour notice after a court revoked his Egyptian citizenship because he holds dual citizenship. He moved to Israel, leaving behind a wife and children who cannot join him because Egyptian authorities do not allow its citizens to travel to Israel.Despite nearly 40 years of peace, mutual diplomatic representation, and high-level political and security cooperation, the Egyptian government remains reluctant to fully embrace Israel. This attitude is reflected in its position toward Egyptians living in Israel: It remains skeptical of their ties to Egypt at best, and downright suspicious at worst. Is it possible for a dual Egyptian Israeli to be anything but a spy?Ambassador Hussein Haridy, a former assistant to the Egyptian foreign minister, explained this point of view plainly in a recent interview. “Egypt is the first enemy to Israel in the Arab region since it is the biggest and strongest power in the region,” he said. “Israeli thinking will never change and it will always try to weaken Egypt as an Arab power.”Egyptian Israelis, he continued, could be a tool in the Israeli government’s war on Egypt: “According to the Israeli law, the son of an Egyptian who is married to a Jew will become an Israeli citizen; hence, it is a real danger because his loyalty would be to what country? Of course, it would be Israel since he was raised there. On the other hand, we do not know the relationship between the Jew he married and the Israeli security apparatus and the Mossad. The son could come afterward to Egypt as a businessman and obtain all the information he wants against Egypt for Israel.”The Egyptian media, which largely reflects the official government line, has taken up this assault on Egyptians living in Israel, from negative depictions on talk shows to biased stories in the newspapers. For years this campaign suppressed Egyptian public support for the Egyptian community in the Jewish state while many living in Israel were afraid to stand up for their right to move freely between the two countries.But this year the group found its voice. After many years of lobbying the Egyptian government through newspaper ads and letters to the Ministry of Immigration, the Egyptian embassy in Tel Aviv asked the community to formalize its status. In February, the Israeli government approved the creation of a nonprofit, “Algaliyah Almasriya B’israel,” the Egyptian Community in Israel, “to advance the affairs of the Egyptian minority in Israel.” The group’s charter was translated into Arabic and sent to the Egyptian embassy.Can this organization break through the many obstacles between Israel and Egypt to better the lives of Egyptian Israelis? Permitting free travel for this tiny community between the countries is a minor issue compared to the much weightier problems on the Cairo-Jerusalem agenda—everything from ISIS in the Sinai to the future of Gaza to bilateral trade. But as a small step toward warmer relations, it would be a great place to start.