Cost-Efficient Set Verification as Infrastructure for the Post-Quantum Era: What Parity Bitmap Sketch Shows and What It Doesn’t Promise

04.11.2026

The quantum threat to cryptography isn’t just a question of “will a quantum computer break RSA?” It’s also an engineering question: how to more cheaply synchronize large distributed datasets as metadata volumes, trust requirements, and update frequency grow. This article examines the classic  Parity Bitmap Sketch (PBS) scheme  for set reconciliation and shows where it truly delivers: low  O(d)  communication complexity, approximately  2.13–2.87  times the theoretical minimum. However, PBS  isn’t  post-quantum cryptography and doesn’t protect signatures or keys.

1. Statement of the problem and intrigue

⚙️ Detailed research option

Imagine two participants in a distributed system: Alice and Bob. Each has a large set of objects: transactions, files, records, or hash signatures. The sets are nearly identical but differ in  d elements. Alice needs to recognize the difference  A △ B and restore the merger by transmitting as little data and performing as few computations as possible.

This is the set reconciliation problem  . It arises in cloud synchronization, distributed databases, and blockchain networks. The PBS paper [PBS] shows that existing solutions fall into an awkward tradeoff: IBF approaches have  O(d) complexity but transmit approximately 6 times the theoretical minimum; ECC approaches transmit almost the minimum but are decoded in  O(d²) .

A point of intrigue for the reader:  is it possible to achieve both low communication and low computational complexity—not in the quantum, but in the classical engineering sense?  PBS answers: largely yes, but with caveats. And the quantum context adds a second question:  what changes in the transition to post-quantum cryptography?  The answer: the motivation and workload profile change, but not the nature of PBS.

2. What exactly is being studied

⚙️ Detailed research option

The object of this study is  PBS , a set verification scheme based on parity bitmaps and BCH codes. The paper [PBS] describes it in two modes: PBS-for-small d and PBS-for-large d. In the first mode  d , little is known; in the second, the hash sets are partitioned into  g = d/δ groups, and then the small scheme is applied to each group. This reduces the complexity of BCH decoding from  O(d²)  to  O(d) .

Key elements:

  • consistent hash partitioning  A and  B subset  n partitioning;
  • parity bitmap: the bit is 1 if the subset has an odd number of elements;
  • BCH code that allows Bob to find the positions of the bitmap differences;
  • XOR sums to recover individual elements when  d ≤ 1;
  • checksum to verify the result;
  • multi-round process with independent hash functions;
  • ToW power of difference estimator  d;
  • Markov model for parameter tuning.

3. Tested hypothesis and refutation criteria

⚙️ Detailed research option

The central hypothesis is  that PBS provides a practical compromise for large-set verification: communication remains within a few theoretical minima, and computation scales approximately linearly in  d; however, PBS is  a complement  to post-quantum migration, not a replacement for it.

SubhypothesisWhat should be observedWhat would refute
H1. Communication compromisePBS transmits approximately 2-3 theoretical minimums and is better than IBF schemes in communicationCommunication growth is stronger than linear or worse than D.Digest/Graphene under comparable conditions
H2. Computational scalabilityPBS has O(d) behavior and is noticeably faster than PinSketch at large dDecoding PBS grows as O(d²) on large d
H3. Step-by-step reconciliationMore than 95% of differences are recovered in the first round; the number of rounds is smallMost differences require many rounds
H4. Analytical customizabilityThe Markov model predicts success and allows for choice  n, tThe model does not agree with experiments or does not provide a working setting
H5. Role in the quantum contextPBS reduces synchronization costs but does not solve cryptanalytic threatsPBS itself provides post-quantum security for signatures/keys

4. Which questions from the constructor were selected?

⚙️ Detailed research option

From the general framework, questions were selected that directly link the mechanism, proofs, comparison and limitations:  1, 4, 5, 6, 18, 25, 28, 29, 30, 37, 38, 39, 43, 44, 45, 46. From the specialized sections of cryptography and communications:  49, 50, 51, 53, 54, 56, 57, 58. For future synthesis  , 69, 70, 75 were added .

These questions don’t promise “quantum supremacy” for PBS. They test: what problem does the scheme solve, what is the mechanism, what is the evidence, where are the boundaries, how to compare fairly, and what remains open.

5. PBS Mechanism Without Magic

⚙️ Detailed research option

5.1. Small  d: bitmap, BCH and XOR

⚙️ Detailed research option

If  d ≤ 1 there are enough XOR sums, Bob sends the XOR of all elements  B, Alice compares it with her XOR sum. If the result is 0, there are no differences; if not 0, a single different element was found. This is Procedure 1 in [PBS].

If  d the set is small, the hash is divided into  n subsets. If  the set n is large enough,  d distinct elements are highly likely to fall into different subsets. Then the parity bitmap  A[1..n] differs  B[1..n] exactly in  d bits. Bob decodes the BCH code, finds these positions, and sends Alice the XOR sums of the corresponding subsets. Alice recovers the elements and verifies the checksum.

The probability of an “ideal” case is  ∏(1 − k/n), that is, approximately  1 − O(d²/n). Therefore,  n it should be  Ω(d²). In the article example, for  d=5 ,  n=255 the probability of an ideal case is approximately  0.96 .

5.2. Exceptions and why they don’t break correctness

⚙️ Detailed research option

There are two types of exceptions.  Type I : the subset has an even number of non-zero differences; the bits match, but BCH doesn’t notice this. The  d=5, n=255 probability is about  0.04 .  Type II : the number of differences is odd, ≥3; BCH “thinks” there is only one difference and reconstructs the false element. The probability under the same parameters is about  1.52×10⁻⁴ ; verification  h(s)=i reduces the probability of accepting the false element to about  6×10⁻⁷ .

The checksum is the main “guard.” If the check fails, a new round is started with an independent hash function. False confirmation with a 32-bit checksum is estimated as  O(10⁻¹²) a non-ideal case; for critical applications, a Merkle tree or MSet-XOR-Hash can be added.

5.3. Large  d: Groups and Parameters δ

⚙️ Detailed research option

For large  d PBS, the sets are divided into  g=d/δ groups. The article fixes  δ=5. Then, on average, there are 5 differences per group, and the BCH decoding of each group can be considered  O(1); in total, it is  O(d) . The parameter  t —the BCH correction capacity—is chosen to be the same for all groups. Too small  a parameter t produces many decoding errors; too large a parameter results in unnecessary communication. The optimum, according to the article, is approximately  1.5δ–3.5δ . For , it  d=1000, δ=5, g=200 is optimal  t=13.

If BCH decoding of a group fails, the group is divided into three subgroups. The  δ=5, t=13 probability of a BCH failure for a group is about  6.7×10⁻⁴ , and the conditional probability that a subgroup will exceed ⁻¹⁰ again  tis about  9.5×10⁻¹⁰ . A two-way division would yield  0.0012 , so a three-way division is chosen.

6. Proofs: Communication, Computation, Rounds

⚙️ Detailed research option

6.1. Communication

⚙️ Detailed research option

The theoretical minimum in the article is  d log|U|. For 32-bit signatures, this is 32 bits per distinguishing element. Comparison in [PBS]:

SchemeCommunication is relatively minimalComment
D.Digest (IBF)≈ 6×About 6×32 bits per distinct element
GrapheneBetter than IBF in a special case B⊂AAt  dclose to 100,000, it can overtake PBS; breakeven between 10,000 and 16,000, practically after ≈50,000
PinSketch≈ 1.38×Better communication, but  O(d²) decoding
PBS≈ 2.13–2.87×Compromise: noticeably better than IBF, slightly worse than PinSketch
PinSketch/WPWorse than PBSWhen  log|U|=256 the gap in favor of PBS increases

The reason for PBS’s advantage over PinSketch/WP is that the BCH code in PBS is approximately  t log n, while in PinSketch it is  t log|U|. Since  log n it is typically 3-4 times smaller  log|U|, the “margin” for errors is less expensive. In a blockchain with 256-bit identifiers, this gap should be even more noticeable; this is demonstrated in the paper using a simulation for  log|U|=256.

6.2. Calculations

⚙️ Detailed research option

PBS uses BCH decoding via Toeplitz matrix inversion in  O(d²)  for small  d; for large ,  d the groups yield a total of  O(d) . In experiments:

  • PBS encoding time is significantly lower than PinSketch and D.Digest;
  • when  d=10 000 decoding, PinSketch is approximately three orders of magnitude slower than PBS and D.Digest;
  • D.Digest decodes 1.53–2.35 times faster than PBS, but D.Digest’s encoding is an order of magnitude slower; overall, PBS wins;
  • PBS encodes 1.34–11.38 times faster than Graphene; decodes 1.20–2.28 times slower than Graphene, and near  d≈100 000 decodes up to 4.87 times slower.

Conclusion:  PBS is not an absolute winner in every metric , but it is the best overall “communication + encoding + decoding” tradeoff among the schemes considered.

6.3. Rounds and “staged verification”

⚙️ Detailed research option

In the optimal setting  , d=1000, δ=5, r=3, p₀=0,99 we obtained  n=127, t=13. Expected proportions of differences recovered across rounds:

RoundProportion of recovered differences
10.962
20.0380
33.61×10⁻⁴
42.86×10⁻⁶

Empirically, the average number of rounds was: 1.20 at  d=10; 1.81 at 100; 2.04 at 1,000; 2.09 at 10,000; 2.18 at 100,000. No experiment required more than 3 rounds. This confirms “piecewise reconciliability”: the main work is done immediately, and rare exceptions do not reset all progress.

6.4. Evaluation  d and customization

⚙️ Detailed research option

In practice,  d it’s unknown. PBS uses a ToW estimator:  d̂ = (Σ(Y_i(A)−Y_i(B))²)/ℓ, unbiased, with variance  (2d²−2d)/ℓ.  ℓ=128 This is 336 bytes. To be on the safe side,  Pr[d ≤ 1,38 d̂] ≥ 0,99 they use  γ=1,38. This estimate is conservative: it may increase communication, but reduces the risk of failure.

The Markov model describes the number of “bad” elements after each round. The probability of success over  r rounds is  (M^r)(x,0). In the optimization example, , , and ,  d=1000, δ=5, g=200, r=3, p₀=0,99 are chosen  n=127, t=13. Communication per group: 591 bits for  r=1, 402 for  r=2, 318 for  r=3, and 288 for  r=4. This results  r=3 in a “sweet spot” for high  p₀.

7. Connecting with Quantum Issues: Where PBS Is Really Useful

⚙️ Detailed research option

An important distinction.  PBS is a classic scheme based on BCH codes and a parity bitmap. It  does not  perform factorization, does not implement a quantum algorithm, does not provide secrecy, and does not replace post-quantum signatures or KEM. The quantum context here is  infrastructural : migration to PQC and the growth of distributed systems make synchronization costs more important.

Questions 49–51.  Quantum cryptanalysis threatens specific problems—factorization, discrete logarithm, and so on. PBS is not one of them. Its correctness is based on BCH and hash partitioning, not on the difficulty of these problems.

Questions 53–54.  Quantum-Keyed Disclosure and post-quantum cryptography solve different problems. PBS is neither: it is a data verification protocol. It can be used over a secure channel, but it does not secure the channel itself.

Question 56.  In blockchain, PBS aims to reduce the volume of hash signature transmissions for relay transactions. However, signature verification, the choice of post-quantum schemes, and the timing of public key disclosure are separate issues. The [PBS] paper cites an Erlay benchmark: verification communications account for approximately 5% of total relay traffic; using IBF without identifier compression, this could increase to ~55%. This is the motivation, not a measurement of PBS in a real network.

Questions 57–58.  For communications, PBS reduces the amount of overhead but does not eliminate authentication, the classic channel, intermediate node memory, or trust. Its advantage is particularly noticeable when objects are small or synchronized less frequently than their hash signatures.

Questions 63–66.  The practical value of PBS lies in reducing bandwidth and computation. However, the total cost of ownership includes evaluation  d, BCH setup, exception handling, additional rounds, and verification. This is sufficient for a lab prototype; for production, integration with existing protocols is required.

8. Honest comparison and limitations

⚙️ Detailed research option

  • Not “exactly two minima.”  In the PBS experiments, it’s 2.13–2.87 times the theoretical minimum, not exactly 2.
  • Dependency on  d.  The estimate  d costs 336 bytes and may be conservative due to  γ=1,38.
  • Graphene can win in a special case.  For  B⊂A and very large  d , Graphene uses a Bloom filter and can outperform PBS in communication after ≈50,000; this is the best-case scenario for Graphene.
  • PinSketch transmits less.  But its decoding  O(d²) scales poorly;  d=10 000 the gap is about three orders of magnitude.
  • Experiments with 32-bit signatures.  For 256-bit signatures, the advantage of PBS over PinSketch/WP should increase, but this is demonstrated by simulation, not a full implementation.
  • The quantum component was not measured.  The paper does not contain experiments with PQC signatures, quantum channels, or quantum attacks. This provides external context and is a direction for future work.
  • False positive.  With a 32-bit checksum, the probability is low, but not zero; for critical systems, additional cryptographic verification is required.

9. What would be an interesting next study?

⚙️ Detailed research option

  1. Repeat the comparison of PBS and PinSketch/WP on real 256-bit blockchain identifiers, not just a simulation.
  2. Add post-quantum signatures to the experiment and measure full relay traffic, not just hash matching.
  3. To test how PBS behaves under uneven distribution of differences and in the presence of an adversary influencing the hash partition.
  4. Compare the Markov model with a wider range of  δ,  t and  d, including very large  d.
  5. Evaluate the integration of PBS with Merkle Tree or MSet-XOR-Hash for mission-critical applications.

10. Conclusion

⚙️ Detailed research option

PBS is a powerful engineering result: it significantly improves the tradeoff between communication and computation for set verification. Its main contribution is not a “quantum miracle,” but rather a reduction in the cost of synchronization in distributed systems where the differences are small relative to the union. In a post-quantum context, this is complementary: PQC protects signatures and keys, while PBS reduces the cost of metadata transmission and verification. If this paper is intended to arouse curiosity, it is not by promising “quantum supremacy,” but by asking a precise question:  where exactly do savings on verification become critical in the transition to new cryptography, and how can this gain be measured fairly?

11. Pre-publication check

⚙️ Detailed research option

  • Classical PBS results are separated from the quantum context.
  • The exact communication ranges are given, not just “about two”.
  • Comparisons of PBS with PinSketch, D.Digest, and Graphene come with caveats.
  • PBS is not claimed to provide post-quantum security.
  • Limitations and disadvantages are clearly stated.
  • It is clear to the reader what new the article provides and what experiment is needed next.

12. Sources and notes

⚙️ Detailed research option

  1. [PBS]  Long Gong, Ziheng Liu, Liang Liu, Jun Xu, Mitsunori Ogihara, Tong Yang.  Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS) . PVLDB, 14(xxx), 2021. Preprint 2007.14569v3. All technical details about PBS, experiments, Markov model, ToW estimator, and comparisons are taken from this file.
  2. National Quantum Initiative. Quantum science areas: computing, networks, sensors. External context, not a PBS result.
  3. NIST. FIPS 203, 204, 205 Approval (August 13, 2024). External context for post-quantum migration; PBS is not part of these standards.
  4. NIST NCCoE. Migration to Post-Quantum Cryptography. Context for a Practical Transition.

Citation note: [PBS] references are to the preprint; external sources on quantum technologies and PQC are used for context only and do not endorse the technical results of PBS.

Appendix A. Selected Design Questions

⚙️ Detailed research option

General:  1, 4, 5, 6, 18, 25, 28, 29, 30, 37, 38, 39, 43, 44, 45, 46.
Profile:  49, 50, 51, 53, 54, 56, 57, 58.
For future synthesis:  69, 70, 75.

Appendix B. Article Card

⚙️ Detailed research option

TopicPBS as an infrastructure for cost-effective set verification in the context of post-quantum migration
The central questionIs it possible to simultaneously reduce communication and computation when reconciling sets, and what difference does this make in a quantum context?
HypothesisPBS gives O(d) and ≈2–3× minimum; it complements PQC but does not replace it
MethodPreprint analysis, comparison of algorithms, analysis of experiments and limitations
MetricsCommunication, encoding/decoding time, number of rounds, probability of success
Restrictions32-bit signatures in experiments;  d estimated; quantum effects not measured
New contributionThe PQC context → synchronization cost → PBS as a classic infrastructure layer
Next experimentFull relay traffic with 256-bit identifiers and PQC signatures