Relicでペアリングを動かす

2023/04/26に公開

環境

Windows 11
Ubuntu 20.04 on WSL2
RELIC version 0.6.0
Ryzen 9 5900X TB ON

参考
https://github.com/relic-toolkit/relic/wiki/Building

コンパイル

https://github.com/relic-toolkit/relic/releases/tag/0.6.0
からソースコードをダウンロード

sudo apt install libgmp-dev cmake
tar xzvf relic-0.6.0.tar.gz
cd relic-0.6.0/
mkdir -p relic-target
cd relic-target/
../preset/gmp-pbc-bn254.sh ../
make

好きなプリセットでコンパイルする

テスト

ctest

で全テスト実行

./libにライブラリが生成されている。

make install

でインストール可能

./binにベンチ関数ができている。

bench_bn  bench_ec   bench_fb   bench_md   bench_rand  test_dv  test_ep   test_fp   test_pc
bench_cp  bench_ed   bench_fbx  bench_mpc  test_bn     test_eb  test_epx  test_fpx  test_pp
bench_dv  bench_ep   bench_fp   bench_pc   test_core   test_ec  test_fb   test_md   test_rand
bench_eb  bench_epx  bench_fpx  bench_pp   test_cp     test_ed  test_fbx  test_mpc

BN254 on GMP

bench_bnを実行してみる。

-- RELIC 0.6.0 configuration:

** Allocation mode: AUTO

** Arithmetic backend: gmp

** Benchmarking options:
   Number of times: 10000

** Multiple precision module options:
   Precision: 1024 bits, 16 words
   Arithmetic method: COMBA;COMBA;MONTY;SLIDE;BASIC;BASIC

** Prime field module options:
   Prime size: 254 bits, 4 words
   Arithmetic method: INTEG;INTEG;INTEG;MONTY;LOWER;LOWER;SLIDE

** Prime field extension module options:
   Arithmetic method: INTEG;INTEG;LAZYR

** Prime elliptic curve module options:
   Arithmetic method: PROJC;LWNAF;COMBS;INTER

** Bilinear pairing module options:
   Arithmetic method: LAZYR;OATEP

** Binary field module options:
   Polynomial size: 283 bits, 5 words
   Arithmetic method: LODAH;QUICK;QUICK;QUICK;QUICK;QUICK;EXGCD;SLIDE;QUICK

** Binary elliptic curve module options:
   Arithmetic method: PROJC;LWNAF;COMBS;INTER

** Elliptic Curve Cryptography module options:
   Arithmetic method: PRIME

** Edwards Curve Cryptography module options:
   Arithmetic method: PROJC;LWNAF;COMBS;INTER

** Hash function module options:
   Chosen method: SH256


-- Benchmarks for the BN module:

** Utilities:

BENCH: bn_null                          = 0 nanosec
BENCH: bn_new                           = 1 nanosec
BENCH: bn_new_size                      = 1 nanosec
BENCH: bn_make                          = 2 nanosec
BENCH: bn_clean                         = 1 nanosec
BENCH: bn_grow                          = 2 nanosec
BENCH: bn_trim                          = 17 nanosec
BENCH: bn_free                          = 0 nanosec
BENCH: bn_free (size)                   = 0 nanosec
BENCH: bn_copy                          = 5 nanosec
BENCH: bn_abs                           = 5 nanosec
BENCH: bn_neg                           = 6 nanosec
BENCH: bn_sign                          = 0 nanosec
BENCH: bn_zero                          = 3 nanosec
BENCH: bn_is_zero                       = 0 nanosec
BENCH: bn_is_even                       = 0 nanosec
BENCH: bn_bits                          = 3 nanosec
BENCH: bn_get_bit                       = 4 nanosec
BENCH: bn_set_bit                       = 2 nanosec
BENCH: bn_ham                           = 6567 nanosec
BENCH: bn_get_dig                       = 0 nanosec
BENCH: bn_set_dig                       = 4 nanosec
BENCH: bn_set_2b                        = 4 nanosec
BENCH: bn_rand                          = 1789 nanosec
BENCH: bn_rand_mod                      = 2203 nanosec
BENCH: bn_size_str                      = 10112 nanosec
BENCH: bn_write_str                     = 20430 nanosec
BENCH: bn_read_str                      = 6129 nanosec
BENCH: bn_size_bin                      = 2 nanosec
BENCH: bn_write_bin                     = 27 nanosec
BENCH: bn_read_bin                      = 29 nanosec
BENCH: bn_size_raw                      = 0 nanosec
BENCH: bn_write_raw                     = 3 nanosec
BENCH: bn_read_raw                      = 6 nanosec
BENCH: bn_cmp_abs                       = 8 nanosec
BENCH: bn_cmp_dig                       = 1 nanosec
BENCH: bn_cmp                           = 9 nanosec

** Arithmetic:

BENCH: bn_add                           = 16 nanosec
BENCH: bn_add_dig                       = 6 nanosec
BENCH: bn_sub                           = 16 nanosec
BENCH: bn_sub_dig                       = 7 nanosec
BENCH: bn_mul                           = 129 nanosec
BENCH: bn_mul_dig                       = 11 nanosec
BENCH: bn_mul_basic                     = 152 nanosec
BENCH: bn_mul_comba                     = 130 nanosec
BENCH: bn_mul_karat                     = 252 nanosec
BENCH: bn_sqr                           = 131 nanosec
BENCH: bn_sqr_basic                     = 213 nanosec
BENCH: bn_sqr_comba                     = 132 nanosec
BENCH: bn_sqr_karat                     = 228 nanosec
BENCH: bn_dbl                           = 9 nanosec
BENCH: bn_hlv                           = 15 nanosec
BENCH: bn_lsh                           = 19 nanosec
BENCH: bn_rsh                           = 16 nanosec
BENCH: bn_div                           = 272 nanosec
BENCH: bn_div_rem                       = 281 nanosec
BENCH: bn_div_dig                       = 86 nanosec
BENCH: bn_div_rem_dig                   = 85 nanosec
BENCH: bn_mod_2b                        = 12 nanosec
BENCH: bn_mod_dig                       = 41 nanosec
BENCH: bn_mod                           = 190 nanosec
BENCH: bn_mod_basic                     = 269 nanosec
BENCH: bn_mod_pre_barrt                 = 291 nanosec
BENCH: bn_mod_barrt                     = 362 nanosec
BENCH: bn_mod_pre_monty                 = 6 nanosec
BENCH: bn_mod_monty_conv                = 300 nanosec
BENCH: bn_mod_monty                     = 175 nanosec
BENCH: bn_mod_monty_basic               = 162 nanosec
BENCH: bn_mod_monty_comba               = 184 nanosec
BENCH: bn_mod_monty_back                = 184 nanosec
BENCH: bn_mod_pre_pmers                 = 22 nanosec
BENCH: bn_mod_pmers                     = 131 nanosec
BENCH: bn_mxp                           = 394804 nanosec
BENCH: bn_mxp_basic                     = 496355 nanosec
BENCH: bn_mxp_slide                     = 401262 nanosec
BENCH: bn_mxp_monty                     = 682946 nanosec
BENCH: bn_mxp_dig                       = 30952 nanosec
BENCH: bn_mxp_crt                       = 141309 nanosec
BENCH: bn_srt                           = 47620 nanosec
BENCH: bn_gcd                           = 51976 nanosec
BENCH: bn_gcd_basic                     = 51729 nanosec
BENCH: bn_gcd_lehme                     = 6983 nanosec
BENCH: bn_gcd_binar                     = 35866 nanosec
BENCH: bn_gcd_dig                       = 128 nanosec
BENCH: bn_gcd_ext                       = 106819 nanosec
BENCH: bn_gcd_ext_basic                 = 106669 nanosec
BENCH: bn_gcd_ext_binar                 = 152490 nanosec
BENCH: bn_gcd_ext_lehme                 = 9092 nanosec
BENCH: bn_gcd_ext_binar                 = 152171 nanosec
BENCH: bn_gcd_ext_mid                   = 142780 nanosec
BENCH: bn_gcd_ext_dig                   = 2660 nanosec
BENCH: bn_lcm                           = 51910 nanosec
BENCH: bn_smb_leg                       = 401480 nanosec
BENCH: bn_smb_jac                       = 55270 nanosec
BENCH: bn_gen_prime                     = 2197216 nanosec
BENCH: bn_gen_prime_basic               = 31270498 nanosec
BENCH: bn_gen_prime_safep               = 2338315250 nanosec
BENCH: bn_gen_prime_stron               = 460274552 nanosec
BENCH: bn_is_prime                      = 1227536 nanosec
BENCH: bn_is_prime_basic                = 23364 nanosec
BENCH: bn_is_prime_rabin                = 1204783 nanosec
BENCH: bn_is_prime_solov                = 44674047 nanosec
BENCH: bn_mod_inv                       = 83497 nanosec
BENCH: bn_mod_inv_sim (2)               = 84542 nanosec
BENCH: bn_lag (2)                       = 210 nanosec
BENCH: bn_evl (2)                       = 561 nanosec
BENCH: bn_factor                        = 536691814 nanosec
BENCH: bn_is_factor                     = 53 nanosec
BENCH: bn_rec_win                       = 286 nanosec
BENCH: bn_rec_slw                       = 4543 nanosec
BENCH: bn_rec_naf                       = 11100 nanosec
BENCH: bn_rec_tnaf                      = 28290 nanosec
BENCH: bn_rec_rtnaf                     = 28778 nanosec
BENCH: bn_rec_reg                       = 3387 nanosec
BENCH: bn_rec_jsf                       = 20638 nanosec
BENCH: bn_rec_glv                       = 172 nanosec

いろいろオプションがあることがわかる。
ペアリングはここにはなさそうだが、何のベンチなんだろうか・・・

続いてbench_pc

-- RELIC 0.6.0 configuration:

** Allocation mode: AUTO

** Arithmetic backend: gmp

** Benchmarking options:
   Number of times: 10000

** Multiple precision module options:
   Precision: 1024 bits, 16 words
   Arithmetic method: COMBA;COMBA;MONTY;SLIDE;BASIC;BASIC

** Prime field module options:
   Prime size: 254 bits, 4 words
   Arithmetic method: INTEG;INTEG;INTEG;MONTY;LOWER;LOWER;SLIDE

** Prime field extension module options:
   Arithmetic method: INTEG;INTEG;LAZYR

** Prime elliptic curve module options:
   Arithmetic method: PROJC;LWNAF;COMBS;INTER

** Bilinear pairing module options:
   Arithmetic method: LAZYR;OATEP

** Binary field module options:
   Polynomial size: 283 bits, 5 words
   Arithmetic method: LODAH;QUICK;QUICK;QUICK;QUICK;QUICK;EXGCD;SLIDE;QUICK

** Binary elliptic curve module options:
   Arithmetic method: PROJC;LWNAF;COMBS;INTER

** Elliptic Curve Cryptography module options:
   Arithmetic method: PRIME

** Edwards Curve Cryptography module options:
   Arithmetic method: PROJC;LWNAF;COMBS;INTER

** Hash function module options:
   Chosen method: SH256


-- Benchmarks for the PC module:

-- Curve BN-P254:

-- Group G_1:

** Utilities:

BENCH: g1_null                          = 0 nanosec
BENCH: g1_new                           = 0 nanosec
BENCH: g1_free                          = 0 nanosec
BENCH: g1_is_infty                      = 1 nanosec
BENCH: g1_set_infty                     = 7 nanosec
BENCH: g1_copy                          = 8 nanosec
BENCH: g1_cmp                           = 137 nanosec
BENCH: g1_cmp (1 norm)                  = 74 nanosec
BENCH: g1_cmp (2 norm)                  = 22 nanosec
BENCH: g1_rand                          = 52560 nanosec
BENCH: g1_is_valid                      = 136 nanosec
BENCH: g1_size_bin (0)                  = 2 nanosec
BENCH: g1_size_bin (1)                  = 2 nanosec
BENCH: g1_write_bin (0)                 = 114 nanosec
BENCH: g1_write_bin (1)                 = 130 nanosec
BENCH: g1_read_bin (0)                  = 292 nanosec
BENCH: g1_read_bin (1)                  = 11286 nanosec

** Arithmetic:

BENCH: g1_add                           = 624 nanosec
BENCH: g1_sub                           = 633 nanosec
BENCH: g1_dbl                           = 374 nanosec
BENCH: g1_neg                           = 14 nanosec
BENCH: g1_mul                           = 86308 nanosec
BENCH: g1_mul_gen                       = 49258 nanosec
BENCH: g1_mul_pre                       = 48448 nanosec
BENCH: g1_mul_fix                       = 48898 nanosec
BENCH: g1_mul_sim                       = 124308 nanosec
BENCH: g1_mul_sim_gen                   = 123192 nanosec
BENCH: g1_mul_dig                       = 37733 nanosec
BENCH: g1_map                           = 44718 nanosec

-- Group G_2:

** Utilities:

BENCH: g2_null                          = 0 nanosec
BENCH: g2_new                           = 0 nanosec
BENCH: g2_free                          = 0 nanosec
BENCH: g2_is_infty                      = 3 nanosec
BENCH: g2_set_infty                     = 15 nanosec
BENCH: g2_copy                          = 17 nanosec
BENCH: g2_cmp                           = 722 nanosec
BENCH: g2_cmp (1 norm)                  = 1299 nanosec
BENCH: g2_cmp (2 norm)                  = 50 nanosec
BENCH: g2_rand                          = 127214 nanosec
BENCH: g2_is_valid                      = 74386 nanosec
BENCH: g2_size_bin (0)                  = 24 nanosec
BENCH: g2_size_bin (1)                  = 24 nanosec
BENCH: g2_write_bin (0)                 = 227 nanosec
BENCH: g2_write_bin (1)                 = 199 nanosec
BENCH: g2_read_bin (0)                  = 649 nanosec
BENCH: g2_read_bin (1)                  = 29199 nanosec

** Arithmetic:

BENCH: g2_add                           = 1577 nanosec
BENCH: g2_sub                           = 1603 nanosec
BENCH: g2_dbl                           = 764 nanosec
BENCH: g2_neg                           = 26 nanosec
BENCH: g2_mul                           = 159807 nanosec
BENCH: g2_mul_gen                       = 119598 nanosec
BENCH: g2_mul_pre                       = 186738 nanosec
BENCH: g2_mul_fix                       = 117704 nanosec
BENCH: g2_mul_sim                       = 266773 nanosec
BENCH: g2_mul_sim_gen                   = 267339 nanosec
BENCH: g2_mul_dig                       = 75209 nanosec
BENCH: g2_map                           = 142065 nanosec

-- Group G_T:

** Utilities:

BENCH: gt_null                          = 0 nanosec
BENCH: gt_new                           = 0 nanosec
BENCH: gt_free                          = 0 nanosec
BENCH: gt_copy                          = 29 nanosec
BENCH: gt_zero                          = 28 nanosec
BENCH: gt_set_unity                     = 31 nanosec
BENCH: gt_is_unity                      = 8 nanosec
BENCH: gt_rand                          = 242590 nanosec
BENCH: gt_cmp                           = 3 nanosec
BENCH: gt_size_bin (0)                  = 0 nanosec
BENCH: gt_write_bin (0)                 = 572 nanosec
BENCH: gt_read_bin (0)                  = 983 nanosec
BENCH: gt_size_bin (1)                  = 5312 nanosec
BENCH: gt_write_bin (1)                 = 5720 nanosec
BENCH: gt_read_bin (1)                  = 2285 nanosec
BENCH: gt_is_valid                      = 129936 nanosec

** Arithmetic:

BENCH: gt_mul                           = 1987 nanosec
BENCH: gt_sqr                           = 1625 nanosec
BENCH: gt_inv                           = 49 nanosec
BENCH: gt_exp                           = 280737 nanosec
BENCH: gt_exp_gen                       = 278066 nanosec
BENCH: gt_exp_sim                       = 634525 nanosec
BENCH: gt_exp_dig                       = 171936 nanosec

-- Pairing:

** Arithmetic:

BENCH: pc_map                           = 528920 nanosec
BENCH: pc_exp                           = 231527 nanosec
BENCH: pc_map_sim (2)                   = 714320 nanosec

これがペアリングのベンチっぽい。
上に書いてあるオプションや曲線はpreset段階で決まるのだろう。
BN254ペアリングがGMPで528μsなので、結構速いのではないだろうか。

BN254 on asm?

x64-pbc-bn254.shプリセットを使う。

-- RELIC 0.6.0 configuration:

** Allocation mode: AUTO

** Arithmetic backend: X64_ASM_4L

** Benchmarking options:
   Number of times: 10000

** Multiple precision module options:
   Precision: 1024 bits, 16 words
   Arithmetic method: COMBA;COMBA;MONTY;SLIDE;BASIC;BASIC

** Prime field module options:
   Prime size: 254 bits, 4 words
   Arithmetic method: INTEG;INTEG;INTEG;MONTY;LOWER;LOWER;SLIDE

** Prime field extension module options:
   Arithmetic method: INTEG;INTEG;LAZYR

** Prime elliptic curve module options:
   Arithmetic method: PROJC;LWNAF;COMBS;INTER

** Bilinear pairing module options:
   Arithmetic method: LAZYR;OATEP

** Binary field module options:
   Polynomial size: 283 bits, 5 words
   Arithmetic method: LODAH;QUICK;QUICK;QUICK;QUICK;QUICK;EXGCD;SLIDE;QUICK

** Binary elliptic curve module options:
   Arithmetic method: PROJC;LWNAF;COMBS;INTER

** Elliptic Curve Cryptography module options:
   Arithmetic method: PRIME

** Edwards Curve Cryptography module options:
   Arithmetic method: PROJC;LWNAF;COMBS;INTER

** Hash function module options:
   Chosen method: SH256


-- Benchmarks for the PC module:

-- Curve BN-P254:

-- Group G_1:

** Utilities:

BENCH: g1_null                          = 28 cycles
BENCH: g1_new                           = 18 cycles
BENCH: g1_free                          = 18 cycles
BENCH: g1_is_infty                      = 26 cycles
BENCH: g1_set_infty                     = 43 cycles
BENCH: g1_copy                          = 39 cycles
BENCH: g1_cmp                           = 288 cycles
BENCH: g1_cmp (1 norm)                  = 170 cycles
BENCH: g1_cmp (2 norm)                  = 84 cycles
BENCH: g1_rand                          = 93006 cycles
BENCH: g1_is_valid                      = 311 cycles
BENCH: g1_size_bin (0)                  = 26 cycles
BENCH: g1_size_bin (1)                  = 26 cycles
BENCH: g1_write_bin (0)                 = 243 cycles
BENCH: g1_write_bin (1)                 = 297 cycles
BENCH: g1_read_bin (0)                  = 702 cycles
BENCH: g1_read_bin (1)                  = 26549 cycles

** Arithmetic:

BENCH: g1_add                           = 1086 cycles
BENCH: g1_sub                           = 1152 cycles
BENCH: g1_dbl                           = 704 cycles
BENCH: g1_neg                           = 48 cycles
BENCH: g1_mul                           = 157430 cycles
BENCH: g1_mul_gen                       = 90600 cycles
BENCH: g1_mul_pre                       = 88983 cycles
BENCH: g1_mul_fix                       = 89438 cycles
BENCH: g1_mul_sim                       = 231884 cycles
BENCH: g1_mul_sim_gen                   = 230883 cycles
BENCH: g1_mul_dig                       = 67444 cycles
BENCH: g1_map                           = 101715 cycles

-- Group G_2:

** Utilities:

BENCH: g2_null                          = 19 cycles
BENCH: g2_new                           = 18 cycles
BENCH: g2_free                          = 18 cycles
BENCH: g2_is_infty                      = 28 cycles
BENCH: g2_set_infty                     = 66 cycles
BENCH: g2_copy                          = 58 cycles
BENCH: g2_cmp                           = 1236 cycles
BENCH: g2_cmp (1 norm)                  = 3702 cycles
BENCH: g2_cmp (2 norm)                  = 155 cycles
BENCH: g2_rand                          = 188247 cycles
BENCH: g2_is_valid                      = 123332 cycles
BENCH: g2_size_bin (0)                  = 85 cycles
BENCH: g2_size_bin (1)                  = 84 cycles
BENCH: g2_write_bin (0)                 = 461 cycles
BENCH: g2_write_bin (1)                 = 464 cycles
BENCH: g2_read_bin (0)                  = 1533 cycles
BENCH: g2_read_bin (1)                  = 69810 cycles

** Arithmetic:

BENCH: g2_add                           = 2561 cycles
BENCH: g2_sub                           = 2645 cycles
BENCH: g2_dbl                           = 1189 cycles
BENCH: g2_neg                           = 70 cycles
BENCH: g2_mul                           = 250438 cycles
BENCH: g2_mul_gen                       = 181351 cycles
BENCH: g2_mul_pre                       = 290248 cycles
BENCH: g2_mul_fix                       = 181542 cycles
BENCH: g2_mul_sim                       = 425573 cycles
BENCH: g2_mul_sim_gen                   = 422098 cycles
BENCH: g2_mul_dig                       = 115120 cycles
BENCH: g2_map                           = 294985 cycles

-- Group G_T:

** Utilities:

BENCH: gt_null                          = 19 cycles
BENCH: gt_new                           = 18 cycles
BENCH: gt_free                          = 18 cycles
BENCH: gt_copy                          = 91 cycles
BENCH: gt_zero                          = 104 cycles
BENCH: gt_set_unity                     = 109 cycles
BENCH: gt_is_unity                      = 46 cycles
BENCH: gt_rand                          = 310769 cycles
BENCH: gt_cmp                           = 31 cycles
BENCH: gt_size_bin (0)                  = 22 cycles
BENCH: gt_write_bin (0)                 = 1148 cycles
BENCH: gt_read_bin (0)                  = 2368 cycles
BENCH: gt_size_bin (1)                  = 8626 cycles
BENCH: gt_write_bin (1)                 = 9497 cycles
BENCH: gt_read_bin (1)                  = 5886 cycles
BENCH: gt_is_valid                      = 176523 cycles

** Arithmetic:

BENCH: gt_mul                           = 2968 cycles
BENCH: gt_sqr                           = 2304 cycles
BENCH: gt_inv                           = 90 cycles
BENCH: gt_exp                           = 390653 cycles
BENCH: gt_exp_gen                       = 394873 cycles
BENCH: gt_exp_sim                       = 886306 cycles
BENCH: gt_exp_dig                       = 233123 cycles

-- Pairing:

** Arithmetic:

BENCH: pc_map                           = 712353 cycles
BENCH: pc_exp                           = 297977 cycles
BENCH: pc_map_sim (2)                   = 993358 cycles

単位がサイクル表記になった。
3 GHzだとするとペアリングが237 μsくらい。
TB ONの実測で190 μsとか。
ちなみにこのパソコンでmclは677.797Kclk だったので、ほとんど同じ性能が出ている。
pc_map_sim (2)はたぶん2ペアリングを同時実行してるんだと思うが、1ペアリングとそんなに変わらない。

Discussion