Homomorphic Authenticators for Blockless Data Verification

63 concepts49 papers1 proposal

When data is outsourced to an untrusted remote server—whether for cloud storage, distributed multi-party computation, or edge processing—verifying its integrity poses a fundamental dilemma. Traditional integrity verification relies on cryptographic hash functions like SHA-256. To verify a file using a standard hash, a client must download the entire file and recompute its digest.

If a client has to download a terabyte of data just to verify that a cloud provider is still storing it correctly, the bandwidth savings of outsourcing the data are entirely defeated.

To bypass this bottleneck, researchers developed homomorphic authenticators (often called homomorphic linear authenticators, or HLAs). These cryptographic primitives allow a verifier to check the integrity of an entire dataset by downloading a single, constant-sized proof. This paradigm is known as blockless verification: the server proves it possesses the intact data without ever transmitting the actual data blocks to the auditor.


The Core Intuition: Linear Combinations

To understand why homomorphic authenticators work, consider how a file is structured. A large file is split into $n$ independent data blocks: $m_1, m_2, \dots, m_n$.

During data pre-processing, the data owner generates a metadata tag (or authenticator) $\sigma_i$ for each individual block $m_i$ using a secret key. Crucially, these tags possess a homomorphic property: an algebraic operation performed on the tags yields a valid tag for the corresponding algebraic operation performed on the underlying data blocks.

In a typical challenge-response auditing protocol, verification unfolds in three steps:

  1. The Challenge: Instead of asking for the whole file, the verifier sends a random challenge consisting of a subset of block indices and a set of randomly chosen coefficients $\nu_i$.
  2. The Aggregation: The remote server uses these coefficients to compute a single, composite data block $\mu$ by taking a linear combination of the requested blocks: $$\mu = \sum \nu_i m_i$$ Simultaneously, the server aggregates the corresponding tags $\sigma_i$ using the same coefficients into a single composite tag $\sigma$.

  3. The Verification: The server transmits only the composite block $\mu$ and the composite tag $\sigma$ to the auditor. The auditor then checks if $\sigma$ is a valid authenticator for $\mu$.

Verifier                                    Prover (Storage Server)
   |                                                   |
   | --- Challenge: Indices & Random Coeffs (\nu) ---> |
   |                                                   | Compute Linear Combinations:
   |                                                   |   \mu = \sum \nu_i * m_i
   |                                                   |   \sigma = Aggregated Tags
   |                                                   |
   | <--- Response: Composite (\mu, \sigma) ---------- |
   |                                                   |
   v                                                   v
Verify \sigma matches \mu
(Blockless Verification)

Why the Prover Cannot Cheat

Why can't a malicious server simply delete a corrupted block and guess a valid composite tag? The security relies on the randomness of the coefficients $\nu_i$, which are chosen by the verifier after the server has committed to storing the data.

If the server modifies a block $m_i$ to $m_i + \delta$, the resulting composite block will be offset by $\nu_i \delta$. Because the server does not know the random coefficients in advance, it cannot predict how the error will propagate through the linear combination. By the properties of polynomial identity testing (such as the Schwartz-Zippel lemma), the probability that the server can forge a matching composite tag $\sigma$ for a corrupted data vector without possessing the exact original blocks is negligibly small.

As demonstrated by Cong Wang et al. in Privacy-Preserving Public Auditing for Secure Cloud Storage, this mechanism allows a Third-Party Auditor (TPA) to verify data integrity on behalf of a client without learning anything about the underlying file content, preserving user privacy while minimizing communication overhead.


Optimizing the Computational Cost

Early iterations of homomorphic verification relied heavily on modular exponentiations within bilinear groups to generate and aggregate tags. While this achieved small proof sizes, it placed a heavy computational burden on the client during the initial data upload phase.

To make blockless verification practical for resource-constrained devices, researchers shifted toward linear operations. In Towards Efficient Provable Data Possession, Ee-Chien Chang et al. showed that replacing expensive modular exponentiations with linear combinations during the data tagging phase drastically reduces client-side computation. This adjustment allows data upload speeds to scale linearly with hardware capabilities while preserving the server's ability to compress thousands of block proofs into a single, fixed-size response.


Application Across Distributed Architectures

The mathematical elegance of homomorphic proof aggregation makes it highly adaptable. Beyond simple cloud storage, it solves trust and verification problems across several distributed domains.

Fault-Tolerant Distributed Storage

In multi-server cloud environments, systems must withstand active adversaries capable of corrupting nodes over time. Kevin D. Bowers et al. designed HAIL: A High-Availability and Integrity Layer for Cloud Storage, which unifies Proofs of Retrievability (PORs) with distributed erasure coding. By computing linear combinations of data blocks across a network of servers, HAIL allows a client to verify the integrity of large datasets using a few hundred bytes of transmitted data, enabling frequent, low-bandwidth auditing.

Preventing Pollution in Network Coding

In multi-source network coding, intermediate routers optimize throughput by mixing packets from different senders before forwarding them. However, this leaves the network vulnerable to "pollution attacks," where a single malicious node injects corrupted packets that propagate and spoil the entire downstream data flow.

To combat this, Shweta Agrawal et al. proposed a discrete-logarithm-based homomorphic signature scheme in Preventing Pollution Attacks in Multi-Source Network Coding. Because the signatures are homomorphic, intermediate routers can mathematically combine the incoming signatures from multiple sources. The routers can then verify that a mixed packet is a legitimate linear combination of authorized source packets without needing to decode or view the original unmixed messages.

Verifiable Edge and Federated Learning

Homomorphic aggregation is also vital when outsourcing computation. In edge computing, a master node might offload heavy linear algebraic tasks to untrusted edge workers. Yasaman Keshtkarjahromi et al. leveraged homomorphic hashing in Secure Coded Cooperative Computation at the Heterogeneous Edge against Byzantine Attacks to validate worker outputs. Because the hash function preserves the linear structure of the computation, the master node can verify the integrity of a worker's result using only the hashes of the input data, avoiding local re-execution.

Similarly, in distributed machine learning, Giulio Zizzo et al. applied this concept to federated learning in Verifiability and Privacy in Federated Learning through Context-Hiding Multi-Key Homomorphic Authenticators. Their framework allows a central server to aggregate individual digital signatures from multiple participants into a single aggregate signature. This aggregate signature validates the sum of the model updates, ensuring the integrity of the global model aggregation while preventing the server from inspecting individual raw user inputs.


Interactive and Group Auditing Extensions

As blockless verification has matured, researchers have extended the core homomorphic mechanism to support complex access patterns and group dynamics.

When multiple users share and modify data in the cloud, auditing becomes complicated because signatures must be updated when users change. Yining Qi addressed this in Blockchain-Based Privacy-Preserving Public Auditing for Group Shared Data by combining linkable homomorphic authenticators with blockchain smart contracts. This integration allows public auditors to verify group data integrity via aggregated proofs while keeping the specific identity of the uploader hidden.

Finally, homomorphic principles have been adapted to accelerate secure multi-party computation (MPC). In standard MPC, verifying that a party is using their previously committed inputs typically requires evaluating heavy static hash functions inside a secure circuit. In MPC-Friendly Commitments for Publicly Verifiable Covert Security, Nitin Agrawal 0002 et al. introduced "indexed hash functions." Rather than computing a static hash over the entire input, the verifier interactively selects a specific index to be computed during the protocol. This interactivity allows the system to verify only a subset of the commitment logic, drastically reducing the computational and communication burden on the secure circuit.

Key Foundational Work

HAIL: A High-Availability and Integrity Layer for Cloud Storage (2008) — contributed 2 concept elements to this direction.
Provable Data Possession at Untrusted Stores (2007) — contributed 2 concept elements to this direction.
Towards Secure Link Quality Measurement in Multihop Wireless Networks (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_homomorphic_proof_aggregation_2330436c,
  title = {homomorphic proof aggregation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/homomorphic-proof-aggregation/rdr_2330436c857048e4a008c79f5cf50760},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_homomorphic_proof_aggregation_2330436c_v1,
  title = {homomorphic proof aggregation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/homomorphic-proof-aggregation/rdr_2330436c857048e4a008c79f5cf50760/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake