Aggregatable Subvector Commitment with Efficient Updates
An aggregatable subvector commitment scheme extends a vector commitment scheme by enabling the aggregation of multiple proofs into a single compact subvector proof. However, the existing schemes have to recompute proofs for each position when inserting an element into the vector, incurring significa...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/2/554 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832589242612580352 |
|---|---|
| author | Qing Xu Chenyang Gao Yunling Wang |
| author_facet | Qing Xu Chenyang Gao Yunling Wang |
| author_sort | Qing Xu |
| collection | DOAJ |
| description | An aggregatable subvector commitment scheme extends a vector commitment scheme by enabling the aggregation of multiple proofs into a single compact subvector proof. However, the existing schemes have to recompute proofs for each position when inserting an element into the vector, incurring significant computational overhead. In this paper, we propose a novel aggregatable subvector commitment scheme based on Newton interpolation, which efficiently supports the addition of new elements. Specifically, the proposed scheme allows incremental updates to the commitment and proofs for each position, avoiding the requirement for full recomputation and thereby significantly reducing computational overhead. Additionally, we employ the Karatsuba algorithm to efficiently perform large-integer multiplication, which improves the aggregation and verification of proofs. Finally, we implement the proposed scheme and conduct a detailed comparison with aSVC. Experimental results demonstrate that the proposed scheme achieves a 48× speedup when adding an element to a 16-length vector, as well as 2.13× and 1.73× speedups for aggregating eight proofs and performing verification, respectively. |
| format | Article |
| id | doaj-art-24683adfb85a410cba3ca6707be847a1 |
| institution | Kabale University |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-24683adfb85a410cba3ca6707be847a12025-01-24T13:19:49ZengMDPI AGApplied Sciences2076-34172025-01-0115255410.3390/app15020554Aggregatable Subvector Commitment with Efficient UpdatesQing Xu0Chenyang Gao1Yunling Wang2School of Cyperspace Security, Xi’an University of Posts & Telecommunications, Xi’an 710121, ChinaSchool of Cyperspace Security, Xi’an University of Posts & Telecommunications, Xi’an 710121, ChinaSchool of Cyperspace Security, Xi’an University of Posts & Telecommunications, Xi’an 710121, ChinaAn aggregatable subvector commitment scheme extends a vector commitment scheme by enabling the aggregation of multiple proofs into a single compact subvector proof. However, the existing schemes have to recompute proofs for each position when inserting an element into the vector, incurring significant computational overhead. In this paper, we propose a novel aggregatable subvector commitment scheme based on Newton interpolation, which efficiently supports the addition of new elements. Specifically, the proposed scheme allows incremental updates to the commitment and proofs for each position, avoiding the requirement for full recomputation and thereby significantly reducing computational overhead. Additionally, we employ the Karatsuba algorithm to efficiently perform large-integer multiplication, which improves the aggregation and verification of proofs. Finally, we implement the proposed scheme and conduct a detailed comparison with aSVC. Experimental results demonstrate that the proposed scheme achieves a 48× speedup when adding an element to a 16-length vector, as well as 2.13× and 1.73× speedups for aggregating eight proofs and performing verification, respectively.https://www.mdpi.com/2076-3417/15/2/554vector commitmentNewton interpolationaggregatable |
| spellingShingle | Qing Xu Chenyang Gao Yunling Wang Aggregatable Subvector Commitment with Efficient Updates Applied Sciences vector commitment Newton interpolation aggregatable |
| title | Aggregatable Subvector Commitment with Efficient Updates |
| title_full | Aggregatable Subvector Commitment with Efficient Updates |
| title_fullStr | Aggregatable Subvector Commitment with Efficient Updates |
| title_full_unstemmed | Aggregatable Subvector Commitment with Efficient Updates |
| title_short | Aggregatable Subvector Commitment with Efficient Updates |
| title_sort | aggregatable subvector commitment with efficient updates |
| topic | vector commitment Newton interpolation aggregatable |
| url | https://www.mdpi.com/2076-3417/15/2/554 |
| work_keys_str_mv | AT qingxu aggregatablesubvectorcommitmentwithefficientupdates AT chenyanggao aggregatablesubvectorcommitmentwithefficientupdates AT yunlingwang aggregatablesubvectorcommitmentwithefficientupdates |