REVIEW 1 major objections 4 minor 40 references
Anonymous Public Announcements
T0 review · 1 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read Safe anonymous public announcements are shown to be exactly public announcements of a new safety modality, with a complete axiomatization and expressivity equivalence among the resulting languages.
desk verdict Worth reading and worth refereeing: the core reduction is clean, but the completeness proof has a small but genuine gap in Lemma 9 that the authors need to fix. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
The paper then considers announcements made with the intention to stay anonymous. Now the announcer must be sure enough people could have said the same thing, and those people must in turn know that enough people could have said it, and so on. The authors encode this recursive requirement as a safety operator, written like a diamond, and defined as a greatest fixed point. A safe announcement is then exactly the public announcement of safety: it removes exactly the states where the statement would not have been safe. They prove this equivalence, and also that the safe announcement language, the safety language, and their combination all have the same expressive power.
The final part gives a sound and complete axiom system for the safety modality, using a Mix axiom and an induction rule similar to common knowledge, but adapted to a weaker, non-normal modality. The paper is theoretical throughout; it does not provide tooling or case studies.
Extended reading notes
Core claim
Safe intentional anonymous announcements are exactly public announcements of safety: for any formulas phi and psi, [phi‡]psi is equivalent to [safety(phi)!]psi, and the safety logic L_safety is sound and complete. This is stated as Lemma 3 and its corollary in Section 4, with completeness as Theorem 1.
Load-bearing premise
The equivalence and completeness results rest on the model-theoretic assumption that the event 'someone announced phi' carries no information beyond 'some agent knows phi', and that anonymity is judged against individual agents rather than coalitions. This enters at Definition 8, where the updated accessibility is (s,a) ~_c (t,b) iff s ~_c t and a=c iff b=c, and in the choice of three-agent groups in the fixpoint defining safety. If announcements leak metadata, or if non-announcers pool knowledge via distributed knowledge, safety as defined may fail; the paper itself lists distributed knowledge as future work in Section 5.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper formalizes anonymous public announcements in the DEL tradition, distinguishing pseudo-anonymous announcements [ϕ†] (no assumption about the announcer's intention) from intentional safe announcements [ϕ‡] (common knowledge of the intention to stay anonymous). The pseudo-anonymous operator is shown to be reducible to epistemic logic via action models, and L† and L! are shown to be update incomparable. The central contribution is a new safety modality ▲, defined as a greatest fixpoint over triples of agents, together with the results that [ϕ‡]ψ is equivalent to the public announcement of safety [▲ϕ!]ψ (Lemma 3), that the languages L‡▲, L‡, and L▲ are equally expressive (Corollary 2), and that the proof system S▲ is sound and complete for L▲ (Proposition 3 and Theorem 1).
Significance. If the results stand, the paper provides a clean and useful DEL-based account of anonymous communication, a novel non-normal safety modality, and a complete axiomatization via a canonical-model argument adapted from common knowledge. The expressivity hierarchy and the fixpoint characterization are elegant, and the reduction of safe anonymous announcements to public announcements of safety is a particularly appealing simplification. The paper carefully separates pseudo- from intentional anonymity and connects the framework to k-anonymity and the Russian Cards problem. The proofs are mostly standard and the paper is honest about its assumptions, explicitly listing distributed knowledge and self-referential announcements as future work. One load-bearing step in the completeness proof, however, needs repair before Theorem 1 is fully established; this is the basis of my major comment.
major comments (1)
- [Section 4.2.2, Lemma 9 and the definition of group assignment function before Lemma 8] In Lemma 9, the candidate group assignment f is defined by 'f(Δ)=G if E_G▲ϕ∈Δ for some G⊆N' (and similarly in the left-to-right direction), with an arbitrary choice among such G. This conflicts with the definition of a group assignment function before Lemma 8, which requires f(Δ)∈N3 or f(Δ)=∅. The conflict is load-bearing in the proof of (2): after establishing 'for every G∈N3 there is i_G∈G such that Δ∧◇K_{i_G}¬χ is consistent', the proof instantiates with G=f(Δ); if the arbitrary choice produced a singleton or pair, that instantiation is invalid. The same problem affects the use of f-consistent paths in the left-to-right direction, where the path argument in Lemma 8 relies on f assigning triples. The gap is local and repairable: from Δ⊢▲ϕ, the Mix axiom gives E_H▲ϕ for some H∈N3, so f(Δ) can be defined to choose such a triple. As printed, however, Theorem 1 is not fully established.
minor comments (4)
- [Definition 11] The clause '(s,a)∼′_c (t,b) iff s∼_c b and a=c iff b=c' should read 's∼_c t' instead of 's∼_c b'; as written it compares a state with an agent.
- [Lemma 3, proof] In the Back direction, the names c and d are reused both as the case parameter and as members of the triple guaranteed by ▲ϕ, which makes the argument unnecessarily hard to follow; renaming the triple members would improve clarity.
- [Lemma 4] The reduction argument is compressed: the claim that the AML reduction axioms remain valid in AML▲− and that the process terminates in L▲ is stated rather than proved. This is standard, but a short explanation of why ▲ never appears in the scope of a dynamic modality during the reduction would help.
- [Section 3.2, Proposition 2] In the formula ϕ := r∧ bKa q∧ bKbKa(¬q∧r)∧Kb p, the symbol 'b' before K_a appears to be a rendering of the diamond ◇_b; this should be typeset consistently to avoid confusion.
Circularity Check
The [ϕ‡]/safety equivalence is largely built into Definition 11, but the safety guarantee and completeness proof are independent; the printed completeness proof has a non-circular gap.
-
self definitional
[Section 4, Definition 11; Section 4.1, Lemma 5; Lemma 3]
"Definition 11: S′ ={(s,a ) :s∈S, M,s|=Ka▲ϕ} ... M,s|= [ϕ‡]ψ⇔∀a∈N, M,s|=Ka▲ϕ⇒Mϕ‡, (s,a )|=ψ. Lemma 5: M,s |=▲ϕ iff M,s|=¬[ϕ‡]⊥."
The [ϕ‡] operator is introduced with a semantic precondition K_a▲ϕ for each possible announcer a, i.e. [ϕ‡] is defined in terms of ▲ϕ. Therefore ¬[ϕ‡]⊥ is, by definition, 'there is an a with K_a▲ϕ'; Lemma 5 then equates this with ▲ϕ using only the Truth axiom and the fixed-point/Mix property of ▲. The claimed expressibility of ▲ by [ϕ‡], and the related reduction [ϕ‡]ψ ↔ [▲ϕ!]ψ in Lemma 3, are thus restatements of the chosen definition rather than independent derivations. This is not a hidden fit or a statistical prediction; it is a transparent definitional reduction. The paper's independent content lies in Lemma 2, the update-expressivity comparisons, and the axiomatisation.
full rationale
The paper contains one self-definitional reduction: Definition 11 defines [ϕ‡] by the precondition K_a▲ϕ, and Lemma 5 shows ▲ϕ ↔ ¬[ϕ‡]⊥; Lemma 3 shows [ϕ‡]ψ ↔ [▲ϕ!]ψ. These are honest, visible equivalences that follow from the chosen semantics plus the S5/fixed-point properties of the safety operator. They are not fitted predictions and no external data are involved. The safety guarantee in Lemma 2, the update-expressivity results (Proposition 2, Corollary 1), the expressivity collapse (Corollary 2), and the soundness/completeness of S▲ are substantive results that do not reduce to the definition of [ϕ‡]. No load-bearing self-citation is used: the cited prior work of the authors is background or future work (e.g., group announcement logic, quantified announcements), and the standard DEL/canonical-model tools are cited to textbooks. Separately, the completeness proof as printed has a non-circular gap: in Lemma 9, f(Δ) is defined as 'G if E_G▲ϕ ∈ Δ for some G⊆ N', choosing an arbitrary G, but a group assignment function was defined to require f(s)∈N3 or ∅; the subsequent proof of (2) instantiates G = f(Δ) and needs a triple. This is a local, repairable gap (one can pick a triple H∈N3 with E_H▲ϕ via Mix), not a circularity. Overall score 3 reflects that one central equivalence is definitional, while the main technical content is independent.
Assumptions & free parameters
assumptions (5)
- standard math Multi-agent epistemic logic is S5: each agent's accessibility relation is an equivalence relation, with Truth and introspection.
- standard math Standard dynamic epistemic logic facts hold: action model logic is equally expressive as epistemic logic via reduction axioms, and bisimulation invariance applies.
- standard math Common knowledge and the new safety operator are defined as greatest fixed points of monotone operators.
- domain assumption At least three distinct agents are required for a safe announcement.
- domain assumption The anonymous announcement event conveys no information beyond 'some agent who knows phi announced it', with no metadata, timing, or coalitional inference.
Cite this review
Pith. "Pith review of Anonymous Public Announcements." pith.science (2026). https://pith.science/paper/QSI2OUZH
@misc{pith2026250412546,
author = {Pith},
title = {Pith review of: Anonymous Public Announcements},
year = {2026},
howpublished = {\url{https://pith.science/paper/QSI2OUZH}},
note = {Machine review of arXiv:2504.12546}
}
abstract
We formalise the notion of an anonymous public announcement in the tradition of public announcement logic. Such announcements can be seen as in-between a public announcement from ``the outside" (an announcement of $\phi$) and a public announcement by one of the agents (an announcement of $K_a\phi$): we get more information than just $\phi$, but not (necessarily) about exactly who made it. Even if such an announcement is prima facie anonymous, depending on the background knowledge of the agents it might reveal the identity of the announcer: if I post something on a message board, the information might reveal who I am even if I don't sign my name. Furthermore, like in the Russian Cards puzzle, if we assume that the announcer's intention was to stay anonymous, that in fact might reveal more information. In this paper we first look at the case when no assumption about intentions are made, in which case the logic with an anonymous public announcement operator is reducible to epistemic logic. We then look at the case when we assume common knowledge of the intention to stay anonymous, which is both more complex and more interesting: in several ways it boils down to the notion of a ``safe" announcement (again, similarly to Russian Cards). Main results include formal expressivity results and axiomatic completeness for key logical languages.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
Studia Logica 104(4), 597–640 (2016)
Ågotnes, T., Ditmarsch, H., French, T.: The undecidability of quantified announcements. Studia Logica 104(4), 597–640 (2016). https://doi.org/10.1007/s11225-016-9657-0, http://dx.doi.org/10. 1007/s11225-016-9657-0 6That also applies to the Russian Cards problem. 25
-
[2]
Journal of Logic, Language and Information 31(2), 141–166 (2022)
Ågotnes, T., Alechina, N., Galimullin, R.: Logics with group announce- ments and distributed knowledge: Completeness and expressive power. Journal of Logic, Language and Information 31(2), 141–166 (2022). https://doi.org/10.1007/s10849-022-09355-0
-
[3]
Journal of Applied Logic8(1), 62–81 (2010)
Ågotnes, T., Balbiani, P., van Ditmarsch, H., Seban, P.: Group announce- ment logic. Journal of Applied Logic8(1), 62–81 (2010)
work page 2010
-
[4]
Autonomous Agents and Multi-agent Systems37(19) (2023)
Ågotnes, T., Galimullin, R.: Quantifying over information change with common knowledge. Autonomous Agents and Multi-agent Systems37(19) (2023)
work page 2023
-
[5]
In: Bienvenu, M., Lake- meyer, G., Erdem, E
Ågotnes, T., Wáng, Y.N.: Somebody knows. In: Bienvenu, M., Lake- meyer, G., Erdem, E. (eds.) Proceedings of the 18th KR. pp. 2–11 (2021).https://doi.org/10.24963/kr.2021/1, https://doi.org/10.24963/ kr.2021/1
-
[6]
Review of Symbolic Logic 1(3), 305–334 (2008)
Balbiani, P., Baltag, A., van Ditmarsch, H., Herzig, A., Hoshi, T., Lima, T.D.: ‘Knowable’ as ‘known after an announcement’. Review of Symbolic Logic 1(3), 305–334 (2008)
work page 2008
-
[7]
Journal of Applied Non-Classical Logics25(1), 2–19 (2015)
Balbiani, P.: Putting right the wording and the proof of the truth lemma for apal. Journal of Applied Non-Classical Logics25(1), 2–19 (2015)
work page 2015
-
[8]
Studies in Logic8, 65–78 (2015)
Balbiani, P., van Ditmarsch, H.: A simple proof of the completeness of apal. Studies in Logic8, 65–78 (2015)
work page 2015
Show all 40 references
-
[9]
In: Kern-Isberner, G., Lakemeyer, G., Meyer, T
Baltag, A., Bezhanishvili, N., Fernández-Duque, D.: The topology of sur- prise. In: Kern-Isberner, G., Lakemeyer, G., Meyer, T. (eds.) Proceedings of the 19th KR (2022). https://doi.org/10.24963/kr.2022/4
2022 doi
-
[10]
Synthese139(2), 165–224 (2004)
Baltag, A., Moss, L.S.: Logics for epistemic programs. Synthese139(2), 165–224 (2004). https://doi.org/10.1023/B:SYNT.0000024912.56773.5E
2004
-
[11]
In: Proceed- ings of the 27th CSF
Barthe, G., Gaboardi, M., Arias, E.J.G., Hsu, J., Kunz, C., Strub, P.: Proving differential privacy in hoare logic. In: Proceed- ings of the 27th CSF. pp. 411–424. IEEE Computer Society (2014). https://doi.org/10.1109/CSF.2014.36
2014 doi
-
[12]
In: Blackburn, P., Van Ben- them, J., Wolter, F
Bradfield, J., Stirling, C.: Modal mu-calculi. In: Blackburn, P., Van Ben- them, J., Wolter, F. (eds.) Handbook of Modal Logic, Studies in Logic and Practical Reasoning, vol. 3, pp. 721–756. Elsevier (2007). https://doi.org/10.1016/S1570-2464(07)80015-2
2007 doi
-
[13]
Studia logica75, 31–62 (2003)
van Ditmarsch, H.: The russian cards problem. Studia logica75, 31–62 (2003). https://doi.org/10.1023/A:1026168632319
2003 doi
-
[14]
van Ditmarsch, H., van der Hoek, W., Kooi, B.: Dynamic Epistemic Logic, Synthese Library, vol. 337. Springer (2007) 26
2007
-
[15]
Information and Computation275, 104544 (2020)
van Ditmarsch, H., van der Hoek, W., Kooi, B., Kuijer, L.B.: Ar- row update synthesis. Information and Computation275, 104544 (2020). https://doi.org/10.1016/J.IC.2020.104544
2020
-
[16]
Synthesis Lectures on Information Secu- rity, Privacy, & Trust, Morgan & Claypool Publishers (2016)
Domingo-Ferrer, J., Sánchez, D., Soria-Comas, J.: Database Anonymiza- tion: Privacy Models, Data Utility, and Microaggregation-based Inter-model Connections. Synthesis Lectures on Information Secu- rity, Privacy, & Trust, Morgan & Claypool Publishers (2016). https://doi.org/10...
2016 doi
-
[17]
The MIT Press, Cambridge, Massachusetts (1995)
Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning About Knowl- edge. The MIT Press, Cambridge, Massachusetts (1995)
1995
-
[18]
In: Blackburn, P., van Benthem, J., Wolter, F
Goranko, V., Otto, M.: Model theory of modal logic. In: Blackburn, P., van Benthem, J., Wolter, F. (eds.) Handbook of Modal Logic, Studies in Logic and Practical Reasoning, vol. 3, pp. 249–329. Elsevier (2007)
2007
-
[19]
Journal of Computer Security 13(3), 483–512 (2005)
Halpern, J.Y., O’Neill, K.R.: Anonymity and information hiding in mul- tiagent systems. Journal of Computer Security 13(3), 483–512 (2005). https://doi.org/10.3233/JCS-2005-13305
2005 doi
-
[20]
ACM Transactions on Information and System Security12(1), 5:1–5:47 (2008)
Halpern, J.Y., O’Neill, K.R.: Secrecy in multiagent systems. ACM Transactions on Information and System Security12(1), 5:1–5:47 (2008). https://doi.org/10.1145/1410234.1410239
2008
-
[21]
Mathematical Social Sciences 38(2), 215–240 (1999)
van der Hoek, W., van Linder, B., Meyer, J.J.: Group knowledge is not always distributed (neither is it always im- plicit). Mathematical Social Sciences 38(2), 215–240 (1999). https://doi.org/https://doi.org/10.1016/S0165-4896(99)00013-X
1999 doi
-
[22]
Journal of Computer Security 12(1), 3–36 (2004)
Hughes, D.J.D., Shmatikov, V.: Information hiding, anonymity and pri- vacy: a modular approach. Journal of Computer Security 12(1), 3–36 (2004). https://doi.org/10.3233/JCS-2004-12102
2004 doi
-
[23]
Journal of Cybersecurity 11(1) (2025)
Jiang, J., Naumov, P.: De re/de dicto distinction: a logicians’ per- spective on data anonymity. Journal of Cybersecurity 11(1) (2025). https://doi.org/10.1093/CYBSEC/TYAE025
2025 doi
-
[24]
In: Proceedings of the The 6th International Conference on Logic and Argumentation (CLAR 2025)
Li, Y., Ren, J., Ågotnes, T.: The surprise exam in full modal fixed-point logic. In: Proceedings of the The 6th International Conference on Logic and Argumentation (CLAR 2025). LNCS, Springer (2025), to appear
2025
-
[25]
ACM Trans- actions on Knowledge Discovery from Data 1(1), 3 (2007)
Machanavajjhala, A., Kifer, D., Gehrke, J., Venkitasubrama- niam, M.: L-diversity: Privacy beyond k-anonymity. ACM Trans- actions on Knowledge Discovery from Data 1(1), 3 (2007). https://doi.org/10.1145/1217299.1217302
2007
-
[26]
Journal of Logic and Computation20(6), 1251–1288 (2010)
Mano, K., Kawabe, Y., Sakurada, H., Tsukada, Y.: Role interchange for anonymity and privacy of voting. Journal of Logic and Computation20(6), 1251–1288 (2010). https://doi.org/10.1093/LOGCOM/EXQ013 27
2010 doi
-
[27]
41.CUP(1995)
Meyer, J.C., van der Hoek, W.: Epistemic logic for AI and computer sci- ence, Cambridge tracts in theoretical computer science, vol. 41.CUP(1995)
1995
-
[28]
An- nals of Mathematics and Artificial Intelligence 62(1-2), 79–101 (2011)
More, S.M., Naumov, P.: Hypergraphs of multiparty secrets. An- nals of Mathematics and Artificial Intelligence 62(1-2), 79–101 (2011). https://doi.org/10.1007/S10472-011-9252-Z
2011 doi
-
[29]
Annals of Pure and Applied Logic 162(12), 959–969 (2011)
More, S.M., Naumov, P.: Logic of secrets in collaboration net- works. Annals of Pure and Applied Logic 162(12), 959–969 (2011). https://doi.org/10.1016/J.APAL.2011.06.001
2011 doi
-
[30]
In: Proceedings of the 32nd IJCAI
Naumov, P., Orejola, O.: Shhh! the logic of clandestine operations. In: Proceedings of the 32nd IJCAI. pp. 3304–3311. ijcai.org (2023). https://doi.org/10.24963/IJCAI.2023/368
2023 doi
-
[31]
inf.tu-dresden.de/literatur/Anon_Terminology_v0.34.pdf, v0.34
Pfitzmann, A., Hansen, M.: A terminology for talking about privacy by data minimization: Anonymity, unlinkability, undetectability, unobserv- ability, pseudonymity, and identity management (Aug 2010),http://dud. inf.tu-dresden.de/literatur/Anon_Terminology_v0.34.pdf, v0.34
2010
-
[32]
In: Proceedings of the 4th ISMIS
Plaza, J.: Logics of public communications. In: Proceedings of the 4th ISMIS. pp. 201–216. Oak Ridge National Laboratory (1989)
1989
-
[33]
In: Bertino, E., Kurth, H., Martella, G., Montolivo, E
Schneider, S.A., Sidiropoulos, A.: CSP and anonymity. In: Bertino, E., Kurth, H., Martella, G., Montolivo, E. (eds.) Proceedings of the 4th ESORICS. LNCS, vol. 1146, pp. 198–218. Springer (1996). https://doi.org/10.1007/3-540-61770-1_38
1996 doi
-
[34]
International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems10(5), 557–570 (2002)
Sweeney, L.: k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems10(5), 557–570 (2002). https://doi.org/10.1142/S0218488502001648
2002 doi
-
[35]
In: Wing, J.M., Woodcock, J., Davies, J
Syverson, P.F., Stubblebine, S.G.: Group principals and the formaliza- tion of anonymity. In: Wing, J.M., Woodcock, J., Davies, J. (eds.) Pro- ceedings of the FM 1999. LNCS, vol. 1708, pp. 814–833. Springer (1999). https://doi.org/10.1007/3-540-48119-2_45
1999 doi
-
[36]
In: Proceed- ings of the 12th CSE
Tsukada, Y., Mano, K., Sakurada, H., Kawabe, Y.: Anonymity, pri- vacy, onymity, and identity: A modal logic approach. In: Proceed- ings of the 12th CSE. pp. 42–51. IEEE Computer Society (2009). https://doi.org/10.1109/CSE.2009.251
2009 doi
-
[37]
An- nals of Mathematics and Artificial Intelligence 78(2), 101–129 (2016)
Tsukada, Y., Sakurada, H., Mano, K., Manabe, Y.: On composi- tional reasoning about anonymity and privacy in epistemic logic. An- nals of Mathematics and Artificial Intelligence 78(2), 101–129 (2016). https://doi.org/10.1007/S10472-016-9516-8, https://doi.org/10.1007/ s10472-0...
2016 doi
-
[38]
Elec- tronic Notes in Theoretical Computer Science 168, 159–174 (2007)
van Eijck, J., Orzan, S.: Epistemic verification of anonymity. Elec- tronic Notes in Theoretical Computer Science 168, 159–174 (2007). https://doi.org/https://doi.org/10.1016/j.entcs.2006.08.026, proceedings of the 2nd VODCA
2007 doi
-
[39]
Annals of Mathematics and Artificial Intelligence91(4), 375–407 (2023)
Xiong, Z., Ågotnes, T.: The logic of secrets and the interpolation rule. Annals of Mathematics and Artificial Intelligence91(4), 375–407 (2023). https://doi.org/10.1007/S10472-022-09815-0
2023 doi
-
[40]
In: Ramamohanarao, K., Krishna, P.R., Mohania, M.K., Nantajeewarawat, E
Ye, X., Li, Z., Li, Y.: Capture inference attacks for k-anonymity with privacy inference logic. In: Ramamohanarao, K., Krishna, P.R., Mohania, M.K., Nantajeewarawat, E. (eds.) Proceedings of the 12th DASFAA. LNCS, vol. 4443, pp. 676–687. Springer (2007). https://doi.org/10.100...
2007 doi
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.