My understanding is that they are not considered private from non-privileged users.
However, history shows them as "" (which also looks broken). (You can probably find an example at https://www.mediawiki.org/w/index.php?title=Manual_talk:FAQ&action=history ):
(cur prev topic) 22:09, 19 November 2015 . . SPage (WMF) (talk | contribs) deleted the topic "" (kgh put a "candidates for speedy deletion" template on this) . . (-80)
And it turns out this only shows on logs because the permissions are not enforced there. I don't think this is actually a security problem if we agree that topic title is not sensitive for deleted topics. Suppress logs are restricted by a separate mechanism (https://www.mediawiki.org/wiki/Special:Log/suppress).
So if we confirm this is not sensitive, the permission system should reflect this. Probably, they should also be visible on history. If not, though, I suggest we make a history message that does not look broken.
