По данным отдела по связям с общественностью крымской милиции, Киргизский национальный университет, на который ссылался М. Бен-Наим при заполнении анкеты на получение гражданства Украины, «не подтвердил факт обучения и выдачи диплома на данного гражданина под всеми известными милиции фамилиями, которые использовал Бен-Наим на протяжении своей жизни и яркой правозащитной деятельности». Кроме того, крымские оперативники, которые сейчас работают в Москве, «не обнаружили ни одного учреждения или предприятия, где бы М. Бен-Наим работал юристом». Как сообщало агентство е-Крым, в начале ноября крымская милиция объявила о начале сбора материалов для лишения гражданства Украины крымского правозащитника Марка Бен-Наима. По данным правоохранителей, в мае 2005 года при заполнении анкеты на получение гражданства Украины М. Бен-Наим подписал обязательство о том, что в случае предоставления заведомо ложных сведений о себе или фальшивых документов, он утратит предоставляемое ему гражданство Украины. Однако милиция установила, что «со стороны гражданина Бен-Наима имели место факты предоставления неправдивых данных о себе, фальсифицированных документов и обмана государственных учреждений». В августе крымский правозащитник Марк Бен-Наим потребовал от Генеральной прокуратуры Украины привлечь к уголовной ответственности начальника крымской милиции Геннадия Москаля, поскольку тот якобы «дал указание привлечь правозащитника к ответственности» за проведение несанкционированного митинга. В сентябре правозащитник начал акцию протеста у здания крымского милицейского главка. Крымская милиция назвала правозащитника «шестеркой» Председателя Верховной Рады Крыма Анатолия Гриценко и крымского депутата Александра Мельника. «е-Крым»