Однако вскоре стало ясно, что нужна более масштабная реабилитация невинно осужденных.
19 марта 1954 года Руденко, министр внутренних дел Круглов, председатель КГБ при Совете Министров СССР Серов и министр юстиции СССР Горшенин направили в Президиум ЦК КПСС записку с предложением образовать Центральную комиссию по пересмотру дел осужденных за «контрреволюционные преступления», содержащихся в лагерях, колониях, тюрьмах и находящихся в ссылке на поселении. В ней отмечалось, что «с целью истребления честных, преданных делу коммунистической партии и Советской власти кадров, преступники, пробравшиеся в органы МВД, сознательно насаждали произвол и беззаконие, совершали незаконные аресты ни в чем не повинных советских граждан, применяли строжайше запрещенные законом преступные методы ведения следствия и фальсифицировали дела».
Авторы записки предлагали пересмотреть все уголовные дела на лиц, осужденных за контрреволюционные преступления судебными и внесудебными органами, содержащихся в лагерях, колониях и тюрьмах (467 946 человек), а также на лиц, находящихся в ссылке на поселении (62 462 человека).
Для пересмотра дел предлагалось создать Центральную комиссию под председательством Генерального прокурора Руденко, а в республиках (не имеющих областного деления), краях и областях – комиссии, возглавляемые прокурорами республик, краев и областей.
4 мая 1954 года постановлением Президиума ЦК КПСС такие комиссии были образованы. В Центральную комиссию, помимо Руденко, от Прокуратуры СССР вошли также начальник управления по надзору за местами заключения Вавилов, заместитель начальника отдела по спецделам Сучков, начальник отдела Главной военной прокуратуры Максимов и прокурор отдела этой же прокуратуры Турцев. 14 июля того же года Секретариат ЦК КПСС, по предложению Руденко, включил в состав Центральной комиссии по пересмотру дел его заместителя и одновременно начальника отдела по спецделам Салина.
19 апреля 1954 года Прокуратура СССР и Министерство внутренних дел внесли предложение в Президиум ЦК КПСС об освобождении из ссылки ранее осужденных за «антисоветскую деятельность» на срок до 5 лет и после отбытия наказания направленных по нарядам МГБ – МВД и постановлениям Особого совещания в ссылку на поселение. Оно было принято, и уже 24 апреля министр внутренних дел Круглов и Генеральный прокурор Руденко подписали совместный приказ на этот счет. Они предложили своим подчиненным всю работу по освобождению указанных лиц закончить к 1 июня 1954 года.
Следует отметить одну очень важную особенность, связанную с реабилитацией. Органы прокуратуры не были вполне свободны, когда речь шла о необходимости реабилитации видных советских, партийных и хозяйственных работников, осужденных по наиболее «громким» делам. В таких случаях Руденко один или же с министром внутренних дел и председателем Комитета государственной безопасности испрашивал согласие Президиума ЦК КПСС. Отсюда проистекали и такие довольно странные формулировки в партийных решениях. Так, в постановлении Президиума ЦК КПСС, предварительно рассматривавшего 15 апреля 1954 года вопрос о реабилитации лиц, проходивших по «ленинградскому делу», было записано: «Разрешить Генеральному прокурору СССР после принятия решения опротестовать приговор Военной коллегии Верховного суда СССР по данному делу на предмет его прекращения и реабилитации осужденных». 3 мая 1954 года Президиум ЦК КПСС принял в окончательной редакции постановление о «ленинградском деле», в котором уже поручал Генеральному прокурору СССР Руденко опротестовать приговор Военной коллегии по делу Кузнецова и других, хотя к этому времени протест уже был внесен и 30 апреля 1954 года Военная коллегия реабилитировала всех лиц, осужденных по этому делу, а также членов их семей и родственников, приговоренных Особым совещанием как соучастников.
Президиум ЦК КПСС поручил Н. С. Хрущеву в мае 1954 года выехать в Ленинград и доложить активу ленинградской партийной организации о решении ЦК КПСС по делу Кузнецова, Вознесенского и др. Такая поездка состоялась 6 и 7 мая. Хрущев взял с собой Генерального прокурора СССР Руденко. Открывая собрание ленинградского партийного актива, Хрущев зачитал постановление Президиума ЦК КПСС по «ленинградскому делу», а затем предложил заслушать Руденко. Роман Андреевич подробно рассказал о том, как фабриковалось это дело, о выбивании у арестованных признательных показаний и т. п. В заключение он признал, что Прокуратура СССР, по существу, не осуществляла никакого надзора за следствием в органах государственной безопасности. Он сказал: «За все время существования Прокуратуры СССР до последнего времени ни разу не проверялись прокурорским надзором Внутренняя и Лефортовская тюрьмы МГБ – МВД, хотя именно в этих тюрьмах совершались преступления. Внутренняя и Лефортовская тюрьмы не проверялись по единственной причине: Берия, Меркулов, Абакумов запретили пускать туда прокуроров».
Генеральный прокурор Руденко постоянно докладывал ЦК КПСС о результатах работы Центральной комиссии по пересмотру дел. В частности, в июне 1954 года он сообщал, что комиссия на своем заседании 31 мая рассмотрела 81 уголовное дело на 113 человек, ранее осужденных Особым совещанием. Принято решение полностью реабилитировать 46 человек, снизить меру наказания 12 лицам, переквалифицировать состав преступления и освободить из ссылки 3 человека. Отказано в просьбе об отмене решения 18 лицам.
15 ноября 1954 года Руденко и председатель КГБ при Совете Министров СССР Серов внесли предложение в ЦК КПСС об упрощении порядка рассмотрения жалоб и заявлений по делам на лиц, осужденных бывшей коллегией ОГПУ тройками НКВД– УНКВД и Особым совещанием. Указом Президиума Верховного Совета СССР от 1 сентября 1953 года эта работа была возложена на Прокуратуру Союза ССР с предварительным заключением Комитета государственной безопасности. В записке предлагалось разрешить Прокуратуре СССР и Комитету государственной безопасности самим устанавливать порядок рассмотрения жалоб. ЦК КПСС с этими доводами согласился, и вскоре появился соответствующий указ Президиума Верховного Совета СССР.
29 апреля 1955 года Руденко направил в ЦК КПСС записку о результатах работы Центральной комиссии и комиссий союзных республик, краев и областей по пересмотру дел на лиц, осужденных за контрреволюционные преступления. В ней сообщалось, что по состоянию на 1 апреля 1955 года было рассмотрено уголовных дел на 237 412 осужденных лиц. Отменено решений и дела прекращены в отношении 8973 лиц, сокращен срок наказания 76 344 лицам, в том числе с освобождением из-под стражи 21 797 человек. Отменена ссылка и высылка на поселение 1371 человеку. Отказано в реабилитации 125 202 лицам.
Как видно из записки, комиссии подходили к вопросу пересмотра дел еще довольно осторожно – более 50 процентов осужденным в реабилитации отказывалось. Характерен такой пример. Известная поэтесса А. А. Ахматова обратилась к К. Е. Ворошилову с просьбой о пересмотре дела ее сына Льва Николаевича Гумилева, молодого ученого-востоковеда, вторично арестованного органами МГБ в 1949 году и приговоренного Особым совещанием к 10 годам лишения свободы. На письме имеется резолюция Ворошилова: «Руденко Р. А. Прошу рассмотреть и помочь». Тем не менее тогда Руденко Председателю Верховного Совета отказал. В своей записке на имя Ворошилова Руденко пишет, что Гумилев занимался антисоветской деятельностью и осужден правильно и что Центральная комиссия по пересмотру дел 14 июня 1954 года приняла решение отказать Ахматовой в ее ходатайстве о пересмотре решения Особого совещания по делу ее сына – Л. Н. Гумилева.