Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs
The arithmetic of computing multiple scalar multiplications in an elliptic curve group then adding them together is called multi-scalar multiplication (MSM). MSM over fixed points dominates the time consumption in the pairing-based trusted setup zero-knowledge succinct non-interactive argument of k...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-03-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/10287 |
| _version_ | 1827996773687230464 |
|---|---|
| author | Guiwen Luo Shihui Fu Guang Gong |
| author_facet | Guiwen Luo Shihui Fu Guang Gong |
| author_sort | Guiwen Luo |
| collection | DOAJ |
| description |
The arithmetic of computing multiple scalar multiplications in an elliptic curve group then adding them together is called multi-scalar multiplication (MSM). MSM over fixed points dominates the time consumption in the pairing-based trusted setup zero-knowledge succinct non-interactive argument of knowledge (zkSNARK), thus for practical applications we would appreciate fast algorithms to compute it. This paper proposes a bucket set construction that can be utilized in the context of Pippenger’s bucket method to speed up MSM over fixed points with the help of precomputation. If instantiating the proposed construction over BLS12-381 curve, when computing n-scalar multiplications for n = 2e (10 ≤ e ≤ 21), theoretical analysis ndicates that the proposed construction saves more than 21% computational cost compared to Pippenger’s bucket method, and that it saves 2.6% to 9.6% computational cost compared to the most popular variant of Pippenger’s bucket method. Finally, our experimental result demonstrates the feasibility of accelerating the computation of MSM over fixed points using large precomputation tables as well as the effectiveness of our new construction.
|
| first_indexed | 2024-04-10T05:18:25Z |
| format | Article |
| id | doaj.art-ad55e5e323324ac19b696241cbf2ccb0 |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-10T05:18:25Z |
| publishDate | 2023-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-ad55e5e323324ac19b696241cbf2ccb02023-03-08T15:37:32ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252023-03-012023210.46586/tches.v2023.i2.358-380Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKsGuiwen Luo0Shihui Fu1Guang Gong2Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, CanadaDepartment of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, CanadaDepartment of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada The arithmetic of computing multiple scalar multiplications in an elliptic curve group then adding them together is called multi-scalar multiplication (MSM). MSM over fixed points dominates the time consumption in the pairing-based trusted setup zero-knowledge succinct non-interactive argument of knowledge (zkSNARK), thus for practical applications we would appreciate fast algorithms to compute it. This paper proposes a bucket set construction that can be utilized in the context of Pippenger’s bucket method to speed up MSM over fixed points with the help of precomputation. If instantiating the proposed construction over BLS12-381 curve, when computing n-scalar multiplications for n = 2e (10 ≤ e ≤ 21), theoretical analysis ndicates that the proposed construction saves more than 21% computational cost compared to Pippenger’s bucket method, and that it saves 2.6% to 9.6% computational cost compared to the most popular variant of Pippenger’s bucket method. Finally, our experimental result demonstrates the feasibility of accelerating the computation of MSM over fixed points using large precomputation tables as well as the effectiveness of our new construction. https://tches.iacr.org/index.php/TCHES/article/view/10287Multi-scalar multiplicationPippenger’s bucket methodzkSNARKblockchain |
| spellingShingle | Guiwen Luo Shihui Fu Guang Gong Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs Transactions on Cryptographic Hardware and Embedded Systems Multi-scalar multiplication Pippenger’s bucket method zkSNARK blockchain |
| title | Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs |
| title_full | Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs |
| title_fullStr | Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs |
| title_full_unstemmed | Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs |
| title_short | Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs |
| title_sort | speeding up multi scalar multiplication over fixed points towards efficient zksnarks |
| topic | Multi-scalar multiplication Pippenger’s bucket method zkSNARK blockchain |
| url | https://tches.iacr.org/index.php/TCHES/article/view/10287 |
| work_keys_str_mv | AT guiwenluo speedingupmultiscalarmultiplicationoverfixedpointstowardsefficientzksnarks AT shihuifu speedingupmultiscalarmultiplicationoverfixedpointstowardsefficientzksnarks AT guanggong speedingupmultiscalarmultiplicationoverfixedpointstowardsefficientzksnarks |