В первые же дни работы специальной группы возникло множество вопросов, с которыми Викторов обратился к Руденко. В частности, есть ли политическое решение о массовом пересмотре дел прошлых лет и т. п. Вот что, по словам Викторова, Роман Андреевич ответил: «Поведение ваших товарищей объяснимо, им нелегко сразу воспринять все то, что вы им сообщили. Просят сослаться на решение о пересмотре дел прошлых лет? Что же, так привыкли. Не верят на слово? В академии так учили. Всем нам придется столкнуться с тем, что оценки некоторых событий и их участников, казавшиеся неизменными, нужно будет пересмотреть. Сделать это надо во имя истины, справедливости и правды истории. А решение будет. Оно готовится».
Руденко лично занимался вопросами реабилитации. Он подписал сотни постановлений следственных органов, признававших обвинения тех или иных лиц необоснованными и недоказанными, и вносил их на рассмотрение Верховного суда СССР. Он принял многих бывших узников, членов их семей, лично знакомил людей со следственными делами, разъяснял им права. Словом, помогал чем только мог.
Среди первых реабилитированных были и расстрелянные бывшие руководители Прокуратуры СССР и Прокуратуры РСФСР и их близкие: первый прокурор Союза И. А. Акулов и его жена Н. И. Шапиро, бывшие прокуроры республики Н. В. Крыленко, В. А. Антонов-Овсеенко и его жена Софья Ивановна, Ф. Е. Нюрина, Н. М. Янсон и его жена Л. Ф. Петрулевич и другие.
Конечно, без политического решения реабилитация жертв репрессий не смогла бы принять столь массовый характер. В январе 1956 года Президиумом ЦК КПСС была образована комиссия по изучению материалов о политических репрессиях в стране в период 1935—1940 годов. Ее возглавил секретарь ЦК КПСС, академик П. Н. Поспелов. В нее вошли также секретарь ЦК КПСС А. В. Аристов, Председатель ВЦСПС Н. М. Шверник, заместитель председателя Комитета партийного контроля при ЦК КПСС П. Т. Комаров. Активное участие в работе комиссии принимал и Генеральный прокурор Союза. Выводы комиссии легли в основу секретного доклада «О культе личности и его последствиях», произнесенного первым секретарем ЦК КПСС Н. С. Хрущевым 25 февраля 1956 года, в последний день работы ХХ съезда КПСС. В докладе впервые было сказано о беззакониях и произволе, творимых органами внутренних дел и государственной безопасности не только с попустительства, но и по прямому указанию И. В. Сталина.
Вот как описывает свои впечатления от этого доклада Викторов: «По инициативе Романа Андреевича Руденко я оказался с числе приглашенных на съезд. Это было глубоко впечатляющее, незабываемое событие в моей жизни... В конце работы съезда выступил Никита Сергеевич Хрущев. Его доклад о злоупотреблениях Сталина произвел большое впечатление. Еще свежа была в памяти всенародна скорбь. Прощаясь со Сталиным, многие искренне плакали. Все хорошо знали, помнили лозунг: «За Родину, за Сталина». С этими словами шли в бой и погибали. С его именем связывали все предшествующие достижения... Что произошло в 1936—1937 годы и почему, многие не могли объяснить. Слышали: были в НКВД изверги Ежов и Берия, но им ничего не простили, покарали. О какой-либо конкретной виновности во всем этом самого Сталина никто открыто не говорил.
Впервые от Никиты Сергеевича Хрущева мы услышали о фактах личных злоупотреблений Сталина — один страшнее другого. В своем блокноте я сделал тогда пометки, которые сохранились».
Многие факты, приведенные в докладе Хрущева, оказались откровением и для Генерального прокурора, участвовавшего в работе съезда в качестве делегата. Вот что говорил тогда Хрущев: «Массовые репрессии резко усилились с конца 1936 года после телеграммы Сталина и Жданова из Сочи от 25 сентября 1936 года, адресованной Кагановичу, Молотову и другим членам Политбюро, в которой говорилось следующее: «Считаем абсолютно необходимым и срочным делом назначение т. Ежова на пост наркомвнудел. Ягода явным образом оказался не на высоте своей задачи в деле разоблачения троцкистско-зиновьевского блока.
Эта сталинская установка о том, что «НКВД опоздал на 4 года» с применением массовых репрессий, что надо быстро «наверстать» упущенное, прямо толкала работников НКВД на массовые аресты и расстрелы...»
Конечно, Хрущев говорил далеко не все, что ему было известно. Ни разу он не упомянул и своего имени, не покаялся за свои «прегрешения», которых было не меньше, чем у любого другого члена Политбюро. Ведь он тоже был причастен к массовым «чисткам» на Украине, когда стал в январе 1938 года первым секретарем ЦК КПУ и кандидатом, а чуть позднее, в марте 1939 года, членом Политбюро ЦК КПСС.