Pith. sign in

REVIEW 2 major objections 5 minor 22 references

NCorr-FP: A Neighbourhood-based Correlation-preserving Fingerprinting Scheme for Intellectual Property Protection of Structured Data

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Pith's one-line read NCorr-FP embeds recipient-specific fingerprints by sampling replacements from the local density of similar records, yielding 100% detection confidence even after 80% record or 70% attribute deletion.

desk verdict Solid incremental extension of the authors' own categorical fingerprinting to mixed-type data, but the headline vertical-subsetting robustness claim doesn't follow from the algorithm as written. read the letter →

arxiv 2505.06379 v1 pith:P7BHFPL5 submitted 2025-05-09 cs.CR

classification cs.CR
keywords datafingerprintingdatabasewatermarkingcorrelationpreservationblinddetectioncollusion-resistantcodesneighbourhoodsamplingfidelity
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 introduces NCorr-FP, a data fingerprinting method that embeds a recipient-specific bit string into structured tabular data by making small, locally plausible value changes. The central claim is that by picking replacement values from the low- or high-density parts of the distribution among similar records, the fingerprint is both statistically invisible and recoverable without the original data. On the Adult dataset, the method reports 100% detection confidence after deleting up to 80% of records or 70% of attributes, near-zero distribution distortion, and at most a 1.6% drop in downstream classification accuracy. If true, this gives data owners a way to trace leaks without sacrificing the usability or statistical fidelity of the shared data.

What carries the argument

The load-bearing object is the neighbourhood-constrained density split. Given a record $r$ and a target attribute $A_i$, the algorithm computes a neighbourhood $N$ of records most similar to $r$ using a distance metric over a precomputed correlated-attribute group $C$; it then estimates the distribution of $A_i$ values inside $N$ (Gaussian KDE for continuous attributes, frequency counts for categorical attributes), separates it by percentile $\phi$ into high-density $HD_\phi$ and low-density $LD_\phi$ regions, and samples the replacement from one of these regions according to the mark bit. The same split is rebuilt during detection, which is why no original data is needed; the redundancy of each fingerprint bit, $\omega \approx n/(L\gamma)$, converts per-position classification errors into a reliable majority vote.

What would settle it

Run the detection algorithm on a fingerprinted copy from which one column has been removed, without any special column-remapping logic; because the algorithm computes the attribute as $s_1 \bmod v$ on the reduced column count, the marks that used the deleted column would be read from the wrong attribute and detection confidence should fall toward chance unless an explicit remapping exists. This is directly testable with the paper's released implementation.

Watch

Extended reading notes

Core claim

The discovery is the embedding–detection loop itself. For each record selected by a pseudorandom generator seeded with the owner's key and the record's primary key, an attribute, a fingerprint bit, and a mask bit are chosen; the mark bit $m = x \oplus f$ decides whether the new value is sampled from the high-density or low-density region of the target attribute's distribution among $k$ nearest neighbours. Detection repeats the same positions without access to the original data, classifies the observed value into the high- or low-density region, recovers $m$, and retrieves $f = m \oplus x$; all votes for each fingerprint bit are then majority-decided. The paper argues that this makes every modification look like a natural value for that record, preserving marginal distributions and correlations, while the redundancy of embedding each bit many times makes the fingerprint robust to deletion and flipping attacks.

Load-bearing premise

The whole scheme rests on the detector being able to reconstruct the same pseudo-random positions that the embedder used; if deleting columns shifts the attribute index to a different column, the reported robustness to 70% attribute deletion does not follow from the detection algorithm as described.

Editorial extensions

If this is right

  • With redundancy at least $\omega \geq 16$, fingerprints are extracted with 100% confidence from just 20% of records and 30% of columns, i.e. after 80% horizontal and 70% vertical subsetting.
  • Robustness against value flipping is controlled by embedding ratio: with $1/\gamma = 0.13$ the fingerprint stays above 95% confidence for up to 25% flipped values, and with $1/\gamma = 0.5$ for up to 40% flipped values.
  • Fidelity and utility degrade slowly with embedding strength: the worst observed Hellinger distance is 0.0225, KL divergence is below $6 \times 10^{-3}$, and classification accuracy loss is at most 1.6% across four classifiers.
  • Colluding recipients can be traced with perfect precision for small coalitions and precision at least 0.88 for up to 10 colluders when using longer Tardos fingerprints; recall is lower for larger collusions.
  • The recommended parameter rule is to choose the largest fingerprint length $L$ that still satisfies $\omega \geq 16$, use a high embedding ratio near 1, and keep the neighbourhood size $k$ at or below 1% of the dataset.

Reading between the lines

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

  • The density-split trick should be tested beyond Adult: on high-dimensional, sparse, or highly skewed data, kNN neighbourhoods and KDE estimates behave differently, so the same redundancy rule may not transfer unchanged.
  • The reported vertical-subsetting robustness implies the detector must cope with a shrunken attribute count; since detection computes the attribute as $s_1 \bmod v$ on the modified database, a direct replication of the 70% column-deletion result with the released implementation would show whether there is an undocumented remapping or whether the result depends on the Adult column order.
  • Because detection only recovers the mark bit and not the original value, the scheme is a natural fit for incremental data updates: new records can be marked and later checked as long as the owner keeps the same key and parameter set.
  • The $\omega \geq 16$ rule gives a ready-made design target: for a fixed dataset size it upper-bounds fingerprint length relative to embedding ratio, which directly translates into the trade-off between collusion tracing power and single-copy robustness.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The manuscript proposes NCorr-FP, a fingerprinting scheme for structured tabular data that embeds recipient-specific bits by replacing selected attribute values with values sampled from high- or low-density regions of the neighbourhood of similar records, where neighbourhoods are built using correlated attribute groups. Detection reverses the embedding by regenerating pseudo-random positions from the owner's secret key and record primary keys, classifying observed values by density, and applying majority voting; Tardos codes are used for collusion accusation. The authors evaluate the method on the Adult Census dataset across effectiveness (vote error rate, detection confidence, false accusation confidence), fidelity (Hellinger distance, KL divergence, correlation maps), utility (four classifiers), and robustness (horizontal/vertical subsetting, flipping, cluster-flipping, collusion). They report 100% detection confidence under removal of up to 80% of records or 70% of attributes, negligible fidelity loss, and precise collusion detection for small collusions.

Significance. If the results hold, NCorr-FP would be a useful addition to the database fingerprinting literature: it targets mixed-type tabular data, aims to preserve joint distributions and correlations, and is evaluated under a broad attack model. The open-source code release, the explicit parameter guidance in Table VIII, and the attacker-cost analysis are concrete strengths, and the horizontal-deletion and flipping robustness claims are plausible because they follow from high bit redundancy and low per-vote error. However, the vertical-subsetting robustness claim, which is part of the paper's headline contribution, is not derivable from the algorithms as written because detection and embedding use different attribute counts after columns are removed. That load-bearing gap must be resolved before the published vertical-robustness numbers can be accepted.

major comments (2)
  1. [Section V-B, Algorithm 3 (line 6) vs. Algorithm 1 (line 4); Fig. 10b] The reported vertical-subsetting robustness does not follow from the stated algorithms. In Algorithm 1, line 4, the marked attribute is i = s1 mod v, where v is the original attribute count. In Algorithm 3, line 6, the same formula is applied to the fingerprinted database after vertical subsetting, whose attribute count is no longer v. Unless the detector is explicitly given the original v and a mapping from surviving column positions to original column positions—neither of which is stated, and both of which would sit uneasily with the claimed blind setting—the detector will generally examine a different attribute than the embedder marked. The same schema-alignment problem affects the correlated groups C: they are defined on the original attribute set, and if member columns are deleted they cannot be reconstructed on the attacked schema. The paper must either specify the schema-alignment and group-reconstruction mechanism used to produce Figure 10b or re-run the vertical-subsetting experiments under the stated blind, schema-mismatched protocol and report the resulting detection confidence.
  2. [Section V-B, Algorithm 3 (lines 9-10); Section VII-D] Even if the attribute-index mismatch were fixed, the detection procedure still presupposes that the neighbourhood construction used in embedding can be reproduced after vertical subsetting. Algorithm 2 builds neighbourhoods from the values of the correlated group C, but after column deletion some members of a group are missing, so select_neighbours cannot be executed as written on the reduced schema. The paper does not describe how the detector handles partially deleted correlated groups or whether it falls back to a different similarity definition. This is not a cosmetic issue: the reported 100% detection confidence under 70% attribute removal depends on the detector being able to reconstruct, for each surviving marked attribute, a neighbourhood comparable to the one used at embedding time.
minor comments (5)
  1. [Abstract and Section I] There are several typos, including 'embeddeding' in the abstract, 'requriements' in Section II, 'hihg-density' in Table I, 'accross' in Section IV, 'distibution' in Table I, and 'approx' in Section VII-D; a proofreading pass is needed.
  2. [Figure 4 caption] The caption reads 'N=20', but Table I defines N as a neighbourhood, whereas Figure 4 appears to use N as the number of recipients; please rename one of these to avoid ambiguity.
  3. [Algorithm 3] Line 11 contains the typo 'LDphi′' instead of 'LD′ϕ', and the indentation of lines 16-17 relative to the if/else on lines 12-15 is ambiguous; the pseudocode should make explicit that the fingerprint bit is computed for both branches.
  4. [Section VI-B and Table II] The baseline 'random fingerprinting' used in Table II and Figure 8 is not described or cited; please specify the baseline algorithm and parameters so the fidelity comparison is reproducible.
  5. [Equation (9)] The symbol ν in the lower bound 1 − 1/(νγ) is not defined in Table I or in the text; please define it or replace it with an explicitly named quantity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: NCorr-FP's embedding and detection are inverse procedures specified in the paper, and the claimed robustness is an empirical result, not a fitted input or a self-citation chain.

full rationale

NCorr-FP does not derive a prediction from a fitted parameter or from a load-bearing self-citation. The embedding procedure (Algorithm 1) and the detection procedure (Algorithm 3) are inverse uses of the same PRSG, attribute-index, neighbourhood, and density-region logic; that is the standard construction of a watermarking scheme rather than a circular reduction. The central ingredients are specified in the paper itself: the correlated groups C are computed from the data by a correlation graph, the density regions are defined by Equations (3)-(7), and the Tardos code is adopted from an external reference with its length formula stated. Detection confidence is assessed empirically against a random baseline (FAC around 0.5) and against external attacks, so the reported 100% DC is an experimental outcome, not an input to the algorithm. The paper's citations to the authors' earlier categorical fingerprinting work [14] are related-work context; the present method is described completely in Algorithms 1-3 and does not rely on [14] for its claimed validity. The caveats the paper itself notes, such as uniform target values and undecided bits, are acknowledged limitations rather than hidden assumptions. The vertical-subsetting index-mapping concern raised by the reader is a potential correctness and robustness issue in Algorithm 3, but it is not circularity: the detector is still defined as the inverse of the embedder, and no experimental claim is reduced to a fitted input by construction.

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

The central claim rests on a small set of experimental hyperparameters and standard assumptions about KDE, secret-key secrecy, and Tardos accusation. No new physical or modeled entity is introduced.

free parameters (5)
  • density percentile phi = not reported in experiments
    Separates low- and high-density regions in embedding and detection; Figures 2-3 use 75% but the evaluation tables do not state the value used.
  • neighbourhood size k = 30, 300, 450 in experiments; recommended k <= 1% of dataset
    Controls the local context for density estimation; the paper recommends small k for fidelity and effectiveness, larger k for robustness.
  • embedding ratio 1/gamma = tested 0.03 to 0.5; recommended close to 1.0
    Fraction of records selected for marking; higher values increase redundancy and robustness but reduce fidelity.
  • fingerprint length L = tested 128 to 1024; recommended largest L satisfying omega >= 16
    Trade-off between redundancy per bit and collusion resolution; the paper recommends omega = n/(L*gamma) >= 16.
  • accusation threshold multiplier x = x = 1 in collusion evaluation
    Sets Z_x = mean + x * std of Tardos accusation scores; the paper evaluates only Z1.
assumptions (4)
  • domain assumption Gaussian KDE with bandwidth h reliably estimates the target attribute density within each neighbourhood
    Equation (3) uses Gaussian KDE, but no bandwidth selection rule is given; detection assumes the density estimate on fingerprinted data stays close to the embedding-time estimate.
  • domain assumption Attacker does not know the owner's secret key K
    The threat model (Section III) assumes a white-box attacker who knows the algorithm but not K; if K leaks, the whole embedding is replicable.
  • domain assumption Tardos code accusation threshold via mean plus x standard deviations is reliable
    Equation (2) defines the accusation rule; the paper does not derive or validate this threshold beyond the reported experiments.
  • ad hoc to paper The empirical redundancy bound omega >= 16 guarantees 100% detection confidence
    Section VII-E states this as a practical lower bound based on Adult Census experiments; it is not derived from first principles and may depend on dataset properties.

how reviews work

0 comments
Cite this review

Pith. "Pith review of NCorr-FP: A Neighbourhood-based Correlation-preserving Fingerprinting Scheme for Intellectual Property Protection of Structured Data." pith.science (2026). https://pith.science/paper/P7BHFPL5

@misc{pith2026250506379,
  author       = {Pith},
  title        = {Pith review of: NCorr-FP: A Neighbourhood-based Correlation-preserving Fingerprinting Scheme for Intellectual Property Protection of Structured Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P7BHFPL5}},
  note         = {Machine review of arXiv:2505.06379}
}
read the original abstract

Ensuring data ownership and traceability of unauthorised redistribution are central to safeguarding intellectual property in shared data environments. Data fingerprinting addresses these challenges by embedding recipient-specific marks into the data, typically via content modifications. We propose NCorr-FP, a Neighbourhood-based Correlation-preserving Fingerprinting system for structured tabular data with the main goal of preserving statistical fidelity. The method uses local record similarity and density estimation to guide the insertion of fingerprint bits. The embedding logic is then reversed to extract the fingerprint from a potentially modified dataset. Extensive experiments confirm its effectiveness, fidelity, utility and robustness. Results show that fingerprints are virtually imperceptible, with minute Hellinger distances and KL divergences, even at high embedding ratios. The system also maintains high data utility for downstream predictive tasks. The method achieves 100\% detection confidence under substantial data deletions and remains robust against adaptive and collusion attacks. Satisfying all these requirements concurrently on mixed-type datasets highlights the strong applicability of NCorr-FP to real-world data settings.

Figures

Figures reproduced from arXiv: 2505.06379 by the authors.

Figure 1
Figure 1. Fingerprinting system: (i) fingerprint embedding pro [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. NCorr-FP demonstration for continuous attributes: [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. NCorr-FP demonstration for categorical attributes: in a) [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Effectiveness NCorr-FP: Vote Error Rate (VER) on [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Effectiveness of NCorr-FP : Detection confidence [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: NCorr-FP fidelity: Histogram difference for 2 repre [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]
Figure 7
Figure 7. Figure 7: Fidelity: Pairwise histogram for attributes [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: Attribute correlation change3 between the original and fingerprinted Adult Census data. The subset of attributes is used for brevity. The top row represents the baseline fingerprinting and the other NCorr scheme with k=300 and k=450, respectively. Darker shades represe…
Figure 9
Figure 9. Figure 9: Utility of the fingerprinted data: ML classification [PITH_FULL_IMAGE:figures/full_fig_p011_9.png]
Figure 10
Figure 10. Figure 10: Robustness of NCorr-FP: DC under subsetting attacks consistent across the two tested neighborhood sizes (k = 300 and k = 450), suggesting that the embedding strength, rather than the neighborhood size, has a more pronounced effect on utility. Overall, the fingerprinti…
Figure 11
Figure 11. Figure 11: Robustness of NCorr-FP: Detection Confidence (DC) under flipping attacks. [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Comparative Analysis of Relational Database Watermarking Techniques: An Empirical Study,

    S. Rani and R. Halder, “Comparative Analysis of Relational Database Watermarking Techniques: An Empirical Study,” IEEE Access, vol. 10, pp. 27970–27989, 2022

  2. [2]

    Optimal probabilistic fingerprint codes,

    G. Tardos, “Optimal probabilistic fingerprint codes,” Journal of the ACM, vol. 55, pp. 10:1–10:24, May 2008

  3. [3]

    Watermarking Techniques for Relational Databases: Survey, Classification and Comparison,

    R. Halder, U. C. F. Venezia, and A. Cortesi, “Watermarking Techniques for Relational Databases: Survey, Classification and Comparison,” Jour- nal of Universal Computer Science , vol. 16, no. 21, pp. 3164–3190, 2010

  4. [4]

    Information Forensics and Security: A quarter-century-long journey,

    M. Barni, P. Campisi, E. J. Delp, G. Do ¨err, J. Fridrich, N. Memon, F. P ´erez-Gonz´alez, A. Rocha, L. Verdoliva, and M. Wu, “Information Forensics and Security: A quarter-century-long journey,” IEEE Signal Processing Magazine, vol. 40, pp. 67–79, July 2023. Conference Name: IEEE Signal Processing Magazine

  5. [5]

    Survey of robust and im- perceptible watermarking,

    N. Agarwal, A. K. Singh, and P. K. Singh, “Survey of robust and im- perceptible watermarking,” Multimedia Tools and Applications , vol. 78, pp. 8603–8633, Apr. 2019

  6. [6]

    Watermarking relational data: framework, algorithms and analysis,

    R. Agrawal, P. J. Haas, and J. Kiernan, “Watermarking relational data: framework, algorithms and analysis,” The VLDB Journal , vol. 12, pp. 157–169, Aug. 2003

  7. [7]

    Fingerprinting relational databases: schemes and specialties,

    Y . Li, V . Swarup, and S. Jajodia, “Fingerprinting relational databases: schemes and specialties,” IEEE Transactions on Dependable and Secure Computing, vol. 2, pp. 34–45, Jan. 2005

  8. [8]

    A Block Oriented Fingerprinting Scheme in Relational Database,

    S. Liu, S. Wang, R. H. Deng, and W. Shao, “A Block Oriented Fingerprinting Scheme in Relational Database,” in Information Security and Cryptology – ICISC 2004 (C.-s. Park and S. Chee, eds.), Lecture Notes in Computer Science, (Berlin, Heidelberg), pp. 455–466, Springer, 2005. 13

Show all 22 references
  1. [9]

    Fingerprinting Relational Databases,

    F. Guo, J. Wang, and D. Li, “Fingerprinting Relational Databases,” in Proceedings of the 2006 ACM Symposium on Applied Computing , SAC ’06, (New York, NY , USA), pp. 487–492, ACM, 2006

  2. [10]

    Watermill: An Optimized Fingerprinting System for Databases under Constraints,

    J. Lafaye, D. Gross-Amblard, C. Constantin, and M. Guerrouani, “Watermill: An Optimized Fingerprinting System for Databases under Constraints,” IEEE Transactions on Knowledge and Data Engineering , vol. 20, pp. 532–546, Apr. 2008. Conference Name: IEEE Transactions on Knowledg...

  3. [11]

    An Evaluation on Robustness and Utility of Fingerprinting Schemes,

    T. ˇSarˇcevi´c and R. Mayer, “An Evaluation on Robustness and Utility of Fingerprinting Schemes,” in Machine Learning and Knowledge Ex- traction (A. Holzinger, P. Kieseberg, A. M. Tjoa, and E. Weippl, eds.), Lecture Notes in Computer Science, (Cham), pp. 209–228, Springer Inte...

  4. [12]

    The Curse of Correlations for Robust Fingerprinting of Relational Databases,

    T. Ji, E. Yilmaz, E. Ayday, and P. Li, “The Curse of Correlations for Robust Fingerprinting of Relational Databases,” in 24th International Symposium on Research in Attacks, Intrusions and Defenses , pp. 412– 427, New York, NY , USA: Association for Computing Machinery, Oct. 2021

  5. [13]

    Towards Robust Fingerprinting of Relational Databases by Mitigating Correlation Attacks,

    T. Ji, E. Ayday, E. Yilmaz, and P. Li, “Towards Robust Fingerprinting of Relational Databases by Mitigating Correlation Attacks,” IEEE Trans- actions on Dependable and Secure Computing , vol. 20, pp. 2939–2953, July 2023

  6. [14]

    A Correlation-Preserving Fingerprinting Technique for Categorical Data in Relational Databases,

    T. Sarcevic and R. Mayer, “A Correlation-Preserving Fingerprinting Technique for Categorical Data in Relational Databases,” in ICT Sys- tems Security and Privacy Protection (M. H ¨olbl, K. Rannenberg, and T. Welzer, eds.), (Cham), pp. 401–415, Springer International Publishing, 2020

  7. [15]

    Robust {Optimization-Based} Watermarking Scheme for Sequential Data,

    E. Ayday, E. Yilmaz, and A. Yilmaz, “Robust {Optimization-Based} Watermarking Scheme for Sequential Data,” pp. 323–336, 2019

  8. [16]

    Collusion-Resilient Probabilistic Fingerprint- ing Scheme for Correlated Data,

    E. Yilmaz and E. Ayday, “Collusion-Resilient Probabilistic Fingerprint- ing Scheme for Correlated Data,” Jan. 2020

  9. [17]

    Semantic-driven watermarking of relational textual databases,

    M. L. P ´erez Gort, M. Olliaro, A. Cortesi, and C. Feregrino Uribe, “Semantic-driven watermarking of relational textual databases,” Expert Systems with Applications , vol. 167, p. 114013, Apr. 2021

  10. [18]

    Collusion-secure fingerprinting for digital data,

    D. Boneh and J. Shaw, “Collusion-secure fingerprinting for digital data,” IEEE Transactions on Information Theory, vol. 44, pp. 1897–1905, Sept. 1998

  11. [19]

    An improvement of discrete Tardos finger- printing codes,

    K. Nuida, S. Fujitsu, M. Hagiwara, T. Kitagawa, H. Watanabe, K. Ogawa, and H. Imai, “An improvement of discrete Tardos finger- printing codes,” Designs, Codes and Cryptography , vol. 52, pp. 339– 362, Sept. 2009

  12. [20]

    Anti-collusion fingerprint- ing for multimedia,

    W. Trappe, M. Wu, Z. Wang, and K. R. Liu, “Anti-collusion fingerprint- ing for multimedia,” IEEE Transactions on Signal Processing , vol. 51, pp. 1069–1087, Apr. 2003

  13. [21]

    Group-Oriented Anti-Collusion Fingerprint Based on BIBD Code,

    Y . Yu, H. Lu, X. Chen, and Z. Zhang, “Group-Oriented Anti-Collusion Fingerprint Based on BIBD Code,” in 2010 2nd International Confer- ence on E-business and Information System Security, pp. 1–5, May 2010

  14. [22]

    Collusion-Resilient Privacy-Preserving Database Fingerprinting,

    S. Zhang, Y . Zhu, and A. Zeng, “Collusion-Resilient Privacy-Preserving Database Fingerprinting,” IEEE Transactions on Information Forensics and Security, vol. 19, pp. 8306–8321, 2024. 14

Pith tools

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