Privacy-Preserving Inconsistency Measurement

Carl Corea; Nico Potyka; Timotheus Kampik

REVIEW 4 major objections 6 minor 14 references

Privacy-Preserving Inconsistency Measurement

T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Two parties can compute how inconsistent their knowledge bases are without revealing any formula, by comparing encrypted models.

desk verdict New idea, useful Id protocol, but Algorithm 4 needs a stated plaintext-space assumption and a proof. read the letter →

arxiv 2505.23825 v1 pith:VVU6DVSW submitted 2025-05-28 cs.CR

Carl Corea , Timotheus Kampik , Nico Potyka This is my paper

classification cs.CR

keywords privacy-preservinginconsistencymeasurementsecuremulti-partycomputationhomomorphicencryptionprivatesetintersectionmeasurescontensionmeasuredrasticpropositionalknowledgebases

verification ladder T0 review T1 audit T2 compute T3 formal

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 asks whether two agents who refuse to share their internal knowledge bases can still learn how much those bases conflict. It answers yes: using fully homomorphic encryption and private set intersection, the agents exchange encryptions of the sets of models (truth assignments satisfying each base) and jointly compute standard inconsistency measures on the union. Specifically, it gives protocols that return the drastic inconsistency degree exactly and an upper bound on the contension inconsistency degree, while revealing neither the formulas nor the individual models. This matters because in multi-agent settings, knowing whether or how much beliefs clash is operationally important even when disclosure is forbidden.

What carries the argument

The central object is an encrypted model-comparison protocol (Algorithm 1) that takes two interpretations encoded as bit strings and returns the Hamming distance between them while the strings stay encrypted. From this core, Algorithm 2 turns the comparison into an intersection test on the satisfaction columns of the two parties' exhaustive truth tables, and Algorithms 3 and 4 extend the comparison to all pairs of models to obtain the smallest number of mismatching assignments. Algorithm 4 pads the model multiset to hide its size and uses an encrypted scanning loop over candidate distances so that the parties learn only the minimal distance, not the intermediate products or which model pairs produced them.

What would settle it

Take a homomorphic encryption scheme whose plaintext space is the ring Z/4 (so 2 times 2 equals 0 mod 4) and run Algorithm 4 on two knowledge bases whose model pairs have Hamming distances that include two copies of 2 but no copy of 0 or 1; the product (0-2)(0-2) evaluates to 0 mod 4, so the first-zero index becomes 0 and the protocol incorrectly reports the bases as having a shared model, whereas over an integral domain the correct answer would be 2.

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is that inconsistency measurement between two propositional knowledge bases can be reduced to private set intersection over model sets: the union of the bases is inconsistent exactly when their model sets are disjoint, and the contension measure can be approximated from the minimal Hamming distance between a model of one base and a model of the other. The paper develops Algorithm 2, which computes the drastic inconsistency measure by privately testing whether the model sets intersect, and Algorithm 4, which computes an upper bound for the contension measure by finding the smallest number of differing truth assignments over any pair of models, while hiding how many models each party has and which model pairs realize the minimum. Both protocols are shown to satisfy input privacy and correctness in the honest-but-curious adversarial model, with the contension bound being an over-approximation that is exact (zero) whenever the union is consistent.

Load-bearing premise

The protocols assume that the fully homomorphic encryption scheme's plaintext arithmetic behaves like integer arithmetic in an integral domain large enough that no intermediate value wraps around; if it does wrap around, the zero-test in Algorithm 4 can report a false zero and the computed inconsistency value is wrong.

Editorial extensions

If this is right

Two parties can determine whether their knowledge bases are jointly consistent without revealing their formulas or their models.
The drastic inconsistency measure can be computed exactly and privately, while the contension measure can be approximated from above privately, and the approximation returns zero exactly when the union is consistent.
The protocols' worst-case runtime is exponential in the number of atoms (up to double-exponential for the padded contension protocol), so they are practical only for small propositional signatures.
Input privacy holds even against malicious adversaries, but correctness does not: a malicious party can submit fake models, a risk the paper notes could be mitigated by zero-knowledge proofs of consistency.
Repeated queries can leak information, as an agent can guess a model in the other's knowledge base with probability at least one over the number of that other's models in the consistent case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The reduction of inconsistency measurement to private set intersection over model sets suggests a general recipe: any inconsistency measure that depends only on the model sets, or on distances between models, could be made privacy-preserving with the same encrypted-comparison machinery.
The exponential padding in Algorithm 4 is the main computational bottleneck; alternative private-intersection-size protocols or circuit-based secure multiparty computation might compute the minimal Hamming distance with better asymptotic cost, at the price of more communication rounds.
The fixed shared atom set means the method measures disagreement only on a common vocabulary; extending to partially overlapping signatures would require a privacy-preserving way to reconcile the two vocabularies first.
The contension upper bound can be loose (the paper's own Example 10 gives a bound of 2 when the true value is 1); a natural extension would be a protocol that searches over three-valued models directly instead of over pairs of two-valued models.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Core thing to know: this is the first work I know of that computes inconsistency measures on the union of two KBs without revealing the KBs, and the high-level approach is plausible. But the protocol for the contension measure upper bound (Algorithm 4) has a correctness gap: it silently assumes the FHE plaintext space is an integral domain with enough room to avoid wraparound, and without that assumption the 'first zero index' test can return the wrong answer. The authors should be asked to state the assumption and prove correctness.

What is genuinely new and useful: the encoding of satisfaction tables as bit vectors and the use of private set intersection over model sets to compute Id is clean. The running example is helpful, and the structural induction in Lemma 1 and Corollary 1 is correct. The paper is also honest: it flags the honest-but-curious model, the exponential enumeration, and the extra leakage in Algorithm 3.

The main technical gap is Algorithm 4, lines 10–18. For each candidate i, the product of (i − d) over all d in S is computed encrypted. If the plaintext modulus is composite (e.g., BFV with t = 2^16), a product of nonzero values can decrypt to zero, so the first zero index need not be the minimal distance. Concretely, with |At| = 20 and S = {1,...,20}, 20! is divisible by 2^16, so L0 decrypts to zero even though the true minimum distance is 1. The paper never states that the plaintext ring must be integral or large enough, and no correctness proof for Algorithm 4 appears in the appendix. The 'prime encryption' step is also under-specified: the exponent p−1 only has the claimed masking effect if p is prime and each nonzero base is coprime to p. There is a fix (use a large prime plaintext modulus and bound the intermediate values), but as written the protocol is not proven. Theorems 1 and 2 are informal and also ignore finite plaintext spaces; for Algorithm 2 the product only involves 0/1, so the issue is milder there. Algorithm 3 leaks the number of models and all pairwise distances; the authors acknowledge this, so it is a fair limitation, not a hidden one.

Who this is for: people in inconsistency measurement or multi-agent systems who care about privacy, and crypto folks looking for new applications. It is a protocol sketch with a real gap in one corner, not a tightly analyzed result.

I would not desk-reject it. The idea is new and the core Id protocol is plausible. But I would send it to referees with the expectation that Algorithm 4 either gets a correctness proof under stated assumptions or is repositioned as a heuristic. If the authors can fix that, it becomes a decent contribution.

Referee Report

4 major / 6 minor

Summary. The paper proposes secure multi-party computation protocols that let two agents jointly measure inconsistency of the union of their propositional knowledge bases without revealing the bases themselves. Algorithm 1 privately computes the Hamming distance between two interpretations; Algorithm 2 uses truth-table encodings to compute the drastic inconsistency measure Id of the union; Algorithm 3 computes the minimum Hamming distance over all pairs of models, yielding an upper bound on the contension inconsistency measure Ic; Algorithm 4 is a padded variant intended to hide intermediate distances and reveal only the first zero index. The paper claims input privacy and correctness for Algorithms 1 and 2, input privacy for Algorithm 3, and gives runtime complexity bounds for all algorithms.

Significance. The problem is relevant and the proposed bridge between inconsistency measurement and private set intersection / homomorphic encryption is original. If the protocols were correct, the paper would provide a concrete, falsifiable way to assess the degree of inconsistency without revealing knowledge bases, with explicit complexity trade-offs. The authors are honest about the limitations of Algorithm 3 and about adversarial-model caveats. However, the central correctness claims, especially for Algorithm 4, rest on unstated assumptions about the FHE plaintext space, and the appendix contains no proof that the first-zero-index test is sound. The contribution is plausible and the gaps appear fixable, so the paper warrants a major revision rather than rejection.

major comments (4)

[Section 3.3, Algorithm 4, lines 10-18] No correctness proof is given for Algorithm 4, and the 'first zero index' test is not sound for the plaintext spaces of standard FHE schemes. The test computes L_i = ∏_{d∈S}(i−d) in the FHE plaintext ring and returns the first i with decrypted value 0. If the plaintext modulus is composite (e.g., t=2^16 in a BFV-type scheme), a product of nonzero factors can vanish: with |At|=20 and true distances S={1,...,20}, L_0=20! ≡ 0 mod 2^16, so the algorithm outputs 0 although the true minimum is 1. Even with a prime modulus t, wrap-around occurs whenever |i−d| ≥ t. Definition 4 imposes no condition on M, and the appendix establishes only IP for Algorithm 3, not correctness of Algorithm 4. The authors should state and prove the required hypotheses (e.g., plaintext modulus prime with t>|At|, and controlled noise growth) under which the first zero index equals min S.
[Section 3.1-3.2, Theorems 1-2] The correctness arguments for Algorithms 1 and 2 treat encrypted arithmetic as integer arithmetic and ignore the finite plaintext space. In the proof of Theorem 1, the claim that vA⊕B[i]∈{0,1} is incorrect: the homomorphic subtraction in line 6 produces −1 when the bits differ (represented as t−1 modulo t), and squaring gives 1 only if no modular reduction has occurred. The accumulated sum n can also exceed the plaintext modulus; Cor then fails unless t>|At| and the FHE scheme's noise bound is respected. The same issue propagates into Algorithms 2 and 3, which call this subroutine. The paper should fix the plaintext space, state a no-overflow condition, and prove the invariant for encrypted values rather than for plaintext values.
[Section 3.3, Algorithm 4, line 15] The step L_i ← (∏_{0...i} L_i)^{p−1} with a random prime p is not backed by a correctness or security argument. Fermat's little theorem gives a^{p−1}≡1 (mod p), but the computation is performed modulo the FHE plaintext modulus q; a^{p−1} mod q is not generally 1 for nonzero a, and if q is composite or q divides the prefix product, the result can be 0, creating additional false zeros. If p is intended to be the plaintext modulus, this must be stated explicitly and the choice of p must be removed from B's arbitrary choices; if the goal is merely to blind nonzero values, a formal leakage argument is required.
[Section 2.4, Definition 4] Definition 4 defines a homomorphic scheme with a single operation ◦, but all protocols require both addition and multiplication and implicitly assume the message space M is a ring with a modulus (e.g., Z_t). The paper never fixes M, the modulus, or the noise-growth model, although the correctness theorems depend on these choices. Please specify the concrete algebraic structure and the exact conditions under which decryption after a circuit of depth proportional to |S| and |At| remains correct.

minor comments (6)

[Section 3] The text refers to 'Axioms (1)-(4)', but no axioms are numbered in the paper; the reference should be to the homomorphic equations displayed in Section 2.4.
[Algorithm 1, line 3] There is a typo in the vector-encryption line: 'E(keωAlen(ωA))' should read 'E(ke, ωA_len(ωA))'.
[Proposition 1] The word 'inconcistency' should be 'inconsistency'.
[Algorithm 4 and Example 11] The notation '2At' and '|2At|' should be 2^{|At|}; the current notation is ambiguous and inconsistent with Table 1.
[Theorem 2 proof] The proof refers to 'line 6' of Algorithm 1 binary, but that variant is described only in prose; naming the modified algorithm and its line numbers would improve clarity.
[Section 3.3, Theorem 3] The relationship between input privacy (IP) and confidentiality (Con) should be clarified before Theorem 3, since Algorithm 3 is said to satisfy IP yet is later described as violating Con; this distinction is central to the motivation for Algorithm 4.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the protocols compute independently defined inconsistency measures from standard cryptographic primitives; the plaintext-ring correctness gap is not a circular step.

full rationale

The paper's derivation chain is self-contained against external semantics. Id and Ic are defined in Definition 2 independently of the protocols; Algorithm 2 computes Id by checking whether Mod(KA) and Mod(KB) intersect via homomorphic products, and Algorithm 3/4 approximate Ic using Lemma 1 and Corollary 1, which are proven by structural induction rather than assumed. No parameter is fitted to data, and no prediction is a renamed input; Proposition 1 follows from Corollary 1 and the definition of Ic as a minimum over a larger set of three-valued models. The only self-citation (Potyka 2018) is related-work context for disagreement, not a load-bearing premise. The skeptical concern about Algorithm 4's zero test is a genuine correctness caveat about the plaintext space needing to behave like an integral domain with no arithmetic wrap-around, but it is a missing cryptographic hypothesis, not a circular step: the algorithm's output is not defined in terms of its own output. Accordingly, no circularity is established.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The protocols introduce no new free parameters or fitted constants. The axioms they rest on are the existence of an IND-CPA secure FHE scheme, an implicit integral-domain/overflow-free plaintext space, the honest-but-curious model, and the ability to enumerate all interpretations over a shared signature. These are pulled from the cryptographic and logical literature, not from the paper itself.

assumptions (4)

domain assumption Existence of an IND-CPA secure fully homomorphic encryption scheme supporting arbitrary addition and multiplication.
Invoked in Section 2.4 and throughout the protocols; no concrete scheme is instantiated.
ad hoc to paper The plaintext message space is an integral domain (or at least zero-divisor-free) and large enough that intermediate products never wrap around modulo the plaintext modulus.
Assumed implicitly for the correctness of Algorithms 1, 2, and 4, particularly the product in line 11 of Algorithm 4, which must be zero iff one factor is zero.
domain assumption Both parties follow the honest-but-curious adversarial model.
Stated in Section 2.2; the protocols are analyzed only under this model.
domain assumption Both parties share a common, finite propositional signature At and can enumerate all interpretations/model sets of their knowledge bases.
Required for constructing the satisfaction tables in Algorithm 2 and the model sets in Algorithms 3 and 4.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Privacy-Preserving Inconsistency Measurement." pith.science (2026). https://pith.science/paper/VVU6DVSW

@misc{pith2026250523825,
  author       = {Pith},
  title        = {Pith review of: Privacy-Preserving Inconsistency Measurement},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VVU6DVSW}},
  note         = {Machine review of arXiv:2505.23825}
}

read the original abstract

We investigate a new form of (privacy-preserving) inconsistency measurement for multi-party communication. Intuitively, for two knowledge bases K_A, K_B (of two agents A, B), our results allow to quantitatively assess the degree of inconsistency for K_A U K_B without having to reveal the actual contents of the knowledge bases. Using secure multi-party computation (SMPC) and cryptographic protocols, we develop two concrete methods for this use-case and show that they satisfy important properties of SMPC protocols -- notably, input privacy, i.e., jointly computing the inconsistency degree without revealing the inputs.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Cryptology ePr int Archive (2015)

Armknecht, F., Boyd, C., Carr, C., Gjøsteen, K., Jäschke, A., Reuter, C.A., Strand, M.: A guide to fully homomorphic encryption. Cryptology ePr int Archive (2015)

work page 2015
[2]

In: Pro- ceedings of the 2012 ACM conference on Computer and communic ations security

Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of gar bled circuits. In: Pro- ceedings of the 2012 ACM conference on Computer and communic ations security. pp. 784–796 (2012)

work page 2012
[3]

Cambridge University Press (2015)

Cramer, R., Damgård, I.B., et al.: Secure multiparty comp utation. Cambridge University Press (2015)

work page 2015
[4]

In: Proceedings of the forty-ﬁrst annual ACM symposium on Theory of computin g

Gentry, C.: Fully homomorphic encryption using ideal lat tices. In: Proceedings of the forty-ﬁrst annual ACM symposium on Theory of computin g. pp. 169–178 (2009)

work page 2009
[5]

In: European Conference on Symb olic and Quantitative Approaches to Reasoning and Uncertainty

Grant, J., Hunter, A.: Measuring consistency gain and inf ormation loss in stepwise inconsistency resolution. In: European Conference on Symb olic and Quantitative Approaches to Reasoning and Uncertainty. pp. 362–373. Spri nger (2011)

work page 2011
[6]

KR 8(358-366), 42 (2008)

Hunter, A., Konieczny, S., et al.: Measuring inconsisten cy through minimal incon- sistent sets. KR 8(358-366), 42 (2008)

work page 2008
[7]

Computer Science Review 49, 100567 (2023)

Morales, D., Agudo, I., Lopez, J.: Private set intersecti on: A systematic literature review. Computer Science Review 49, 100567 (2023)

work page 2023
[8]

In: International Conference on Scalable Uncertainty Management

Potyka, N.: Measuring disagreement among knowledge base s. In: International Conference on Scalable Uncertainty Management. pp. 212–22 7. Springer (2018)

work page 2018

Show all 14 references

[9]

Journal of Philosophica l logic pp

Priest, G.: The logic of paradox. Journal of Philosophica l logic pp. 219–241 (1979)

1979
[10]

In: Scalable Uncertainty Management: 14th I nternational Conference, SUM 2020, Bozen-Bolzano, Italy, September 23–25, 2020, Pro ceedings 14

Ribeiro, J.S., Sofronie-Stokkermans, V., Thimm, M.: Me asuring disagreement with interpolants. In: Scalable Uncertainty Management: 14th I nternational Conference, SUM 2020, Bozen-Bolzano, Italy, September 23–25, 2020, Pro ceedings 14. pp. 84–

2020
[11]

Theory and practice of cryptography and network security protocols and technolog ies 31 (2013)

Sen, J.: Homomorphic encryption-theory and applicatio n. Theory and practice of cryptography and network security protocols and technolog ies 31 (2013)

2013
[12]

In: Scalable Unc ertainty Management: 13th International Conference, SUM 2019, Compiègne, Franc e, December 16–18, 2019, Proceedings 13

Thimm, M.: Inconsistency measurement. In: Scalable Unc ertainty Management: 13th International Conference, SUM 2019, Compiègne, Franc e, December 16–18, 2019, Proceedings 13. pp. 9–23. Springer (2019)

2019
[13]

Springer (2014) Appendix: Proofs for Technical Results Theorem 1

Yi, X., Paulet, R., Bertino, E., Yi, X., Paulet, R., Berti no, E.: Homomorphic en- cryption. Springer (2014) Appendix: Proofs for Technical Results Theorem 1. Algorithm 1 satisﬁes IP, Cor. Proof. The protocol adheres to IP as no party learns anything beyond the Ham- ming dista...

2014
[14]

Thus we have O(k + 5 ∗ |At| + 1) = O(k + |At|)

Line 9 is constant. Thus we have O(k + 5 ∗ |At| + 1) = O(k + |At|). Proposition 4. The lower-bound runtime complexity of Alg1 is Ω (k + |At|), where k is the asymptotic cost of generating the key pair. Proof. Analogous to O. Proposition 5. The runtime complexity of Alg2 is O(k...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Cryptology ePr int Archive (2015)

Armknecht, F., Boyd, C., Carr, C., Gjøsteen, K., Jäschke, A., Reuter, C.A., Strand, M.: A guide to fully homomorphic encryption. Cryptology ePr int Archive (2015)

work page 2015

[2] [2]

In: Pro- ceedings of the 2012 ACM conference on Computer and communic ations security

Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of gar bled circuits. In: Pro- ceedings of the 2012 ACM conference on Computer and communic ations security. pp. 784–796 (2012)

work page 2012

[3] [3]

Cambridge University Press (2015)

Cramer, R., Damgård, I.B., et al.: Secure multiparty comp utation. Cambridge University Press (2015)

work page 2015

[4] [4]

In: Proceedings of the forty-ﬁrst annual ACM symposium on Theory of computin g

Gentry, C.: Fully homomorphic encryption using ideal lat tices. In: Proceedings of the forty-ﬁrst annual ACM symposium on Theory of computin g. pp. 169–178 (2009)

work page 2009

[5] [5]

In: European Conference on Symb olic and Quantitative Approaches to Reasoning and Uncertainty

Grant, J., Hunter, A.: Measuring consistency gain and inf ormation loss in stepwise inconsistency resolution. In: European Conference on Symb olic and Quantitative Approaches to Reasoning and Uncertainty. pp. 362–373. Spri nger (2011)

work page 2011

[6] [6]

KR 8(358-366), 42 (2008)

Hunter, A., Konieczny, S., et al.: Measuring inconsisten cy through minimal incon- sistent sets. KR 8(358-366), 42 (2008)

work page 2008

[7] [7]

Computer Science Review 49, 100567 (2023)

Morales, D., Agudo, I., Lopez, J.: Private set intersecti on: A systematic literature review. Computer Science Review 49, 100567 (2023)

work page 2023

[8] [8]

In: International Conference on Scalable Uncertainty Management

Potyka, N.: Measuring disagreement among knowledge base s. In: International Conference on Scalable Uncertainty Management. pp. 212–22 7. Springer (2018)

work page 2018