h2c_iso_map.hpp
Go to the documentation of this file.
1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2020-2021 Mikhail Komarov <nemo@nil.foundation>
3 // Copyright (c) 2020-2021 Ilias Khairullin <ilias@nil.foundation>
4 //
5 // MIT License
6 //
7 // Permission is hereby granted, free of charge, to any person obtaining a copy
8 // of this software and associated documentation files (the "Software"), to deal
9 // in the Software without restriction, including without limitation the rights
10 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 // copies of the Software, and to permit persons to whom the Software is
12 // furnished to do so, subject to the following conditions:
13 //
14 // The above copyright notice and this permission notice shall be included in all
15 // copies or substantial portions of the Software.
16 //
17 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 // SOFTWARE.
24 //---------------------------------------------------------------------------//
25 
26 #ifndef CRYPTO3_ALGEBRA_CURVES_HASH_TO_CURVE_ISO_MAP_HPP
27 #define CRYPTO3_ALGEBRA_CURVES_HASH_TO_CURVE_ISO_MAP_HPP
28 
29 #include <nil/crypto3/algebra/curves/detail/h2c/h2c_suites.hpp>
30 
31 #include <nil/crypto3/algebra/curves/bls12.hpp>
32 
33 #include <array>
34 
35 namespace nil {
36  namespace crypto3 {
37  namespace algebra {
38  namespace curves {
39  namespace detail {
40  template<typename GroupType>
41  struct iso_map;
42 
43  // 11-isogeny map for BLS12-381 G1
44  // https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-10#appendix-E.2
45  template<>
46  class iso_map<typename bls12_381::g1_type<>> {
47  typedef typename bls12_381::g1_type<> group_type;
48  typedef h2c_suite<group_type> suite_type;
49 
50  typedef typename suite_type::group_value_type group_value_type;
51  typedef typename suite_type::field_value_type field_value_type;
52  typedef typename suite_type::integral_type integral_type;
53 
54  // TODO: change integral_type on field_value_type when constexpr will be finished
55  constexpr static std::array<integral_type, 12> k_x_num = {
56  0x11a05f2b1e833340b809101dd99815856b303e88a2d7005ff2627b56cdb4e2c85610c2d5f2e62d6eaeac1662734649b7_cppui381,
57  0x17294ed3e943ab2f0588bab22147a81c7c17e75b2f6a8417f565e33c70d1e86b4838f2a6f318c356e834eef1b3cb83bb_cppui381,
58  0xd54005db97678ec1d1048c5d10a9a1bce032473295983e56878e501ec68e25c958c3e3d2a09729fe0179f9dac9edcb0_cppui381,
59  0x1778e7166fcc6db74e0609d307e55412d7f5e4656a8dbf25f1b33289f1b330835336e25ce3107193c5b388641d9b6861_cppui381,
60  0xe99726a3199f4436642b4b3e4118e5499db995a1257fb3f086eeb65982fac18985a286f301e77c451154ce9ac8895d9_cppui381,
61  0x1630c3250d7313ff01d1201bf7a74ab5db3cb17dd952799b9ed3ab9097e68f90a0870d2dcae73d19cd13c1c66f652983_cppui381,
62  0xd6ed6553fe44d296a3726c38ae652bfb11586264f0f8ce19008e218f9c86b2a8da25128c1052ecaddd7f225a139ed84_cppui381,
63  0x17b81e7701abdbe2e8743884d1117e53356de5ab275b4db1a682c62ef0f2753339b7c8f8c8f475af9ccb5618e3f0c88e_cppui381,
64  0x80d3cf1f9a78fc47b90b33563be990dc43b756ce79f5574a2c596c928c5d1de4fa295f296b74e956d71986a8497e317_cppui381,
65  0x169b1f8e1bcfa7c42e0c37515d138f22dd2ecb803a0c5c99676314baf4bb1b7fa3190b2edc0327797f241067be390c9e_cppui381,
66  0x10321da079ce07e272d8ec09d2565b0dfa7dccdde6787f96d50af36003b14866f69b771f8c285decca67df3f1605fb7b_cppui381,
67  0x6e08c248e260e70bd1e962381edee3d31d79d7e22c837bc23c0bf1bc24c6b68c24b1b80b64d391fa9c8ba2e8ba2d229_cppui381};
68 
69  constexpr static std::array<integral_type, 10> k_x_den = {
70  0x8ca8d548cff19ae18b2e62f4bd3fa6f01d5ef4ba35b48ba9c9588617fc8ac62b558d681be343df8993cf9fa40d21b1c_cppui381,
71  0x12561a5deb559c4348b4711298e536367041e8ca0cf0800c0126c2588c48bf5713daa8846cb026e9e5c8276ec82b3bff_cppui381,
72  0xb2962fe57a3225e8137e629bff2991f6f89416f5a718cd1fca64e00b11aceacd6a3d0967c94fedcfcc239ba5cb83e19_cppui381,
73  0x3425581a58ae2fec83aafef7c40eb545b08243f16b1655154cca8abc28d6fd04976d5243eecf5c4130de8938dc62cd8_cppui381,
74  0x13a8e162022914a80a6f1d5f43e7a07dffdfc759a12062bb8d6b44e833b306da9bd29ba81f35781d539d395b3532a21e_cppui381,
75  0xe7355f8e4e667b955390f7f0506c6e9395735e9ce9cad4d0a43bcef24b8982f7400d24bc4228f11c02df9a29f6304a5_cppui381,
76  0x772caacf16936190f3e0c63e0596721570f5799af53a1894e2e073062aede9cea73b3538f0de06cec2574496ee84a3a_cppui381,
77  0x14a7ac2a9d64a8b230b3f5b074cf01996e7f63c21bca68a81996e1cdf9822c580fa5b9489d11e2d311f7d99bbdcc5a5e_cppui381,
78  0xa10ecf6ada54f825e920b3dafc7a3cce07f8d1d7161366b74100da67f39883503826692abba43704776ec3a79a1d641_cppui381,
79  0x95fc13ab9e92ad4476d6e3eb3a56680f682b4ee96f7d03776df533978f31c1593174e4b4b7865002d6384d168ecdd0a_cppui381};
80 
81  constexpr static std::array<integral_type, 16> k_y_num = {
82  0x90d97c81ba24ee0259d1f094980dcfa11ad138e48a869522b52af6c956543d3cd0c7aee9b3ba3c2be9845719707bb33_cppui381,
83  0x134996a104ee5811d51036d776fb46831223e96c254f383d0f906343eb67ad34d6c56711962fa8bfe097e75a2e41c696_cppui381,
84  0xcc786baa966e66f4a384c86a3b49942552e2d658a31ce2c344be4b91400da7d26d521628b00523b8dfe240c72de1f6_cppui381,
85  0x1f86376e8981c217898751ad8746757d42aa7b90eeb791c09e4a3ec03251cf9de405aba9ec61deca6355c77b0e5f4cb_cppui381,
86  0x8cc03fdefe0ff135caf4fe2a21529c4195536fbe3ce50b879833fd221351adc2ee7f8dc099040a841b6daecf2e8fedb_cppui381,
87  0x16603fca40634b6a2211e11db8f0a6a074a7d0d4afadb7bd76505c3d3ad5544e203f6326c95a807299b23ab13633a5f0_cppui381,
88  0x4ab0b9bcfac1bbcb2c977d027796b3ce75bb8ca2be184cb5231413c4d634f3747a87ac2460f415ec961f8855fe9d6f2_cppui381,
89  0x987c8d5333ab86fde9926bd2ca6c674170a05bfe3bdd81ffd038da6c26c842642f64550fedfe935a15e4ca31870fb29_cppui381,
90  0x9fc4018bd96684be88c9e221e4da1bb8f3abd16679dc26c1e8b6e6a1f20cabe69d65201c78607a360370e577bdba587_cppui381,
91  0xe1bba7a1186bdb5223abde7ada14a23c42a0ca7915af6fe06985e7ed1e4d43b9b3f7055dd4eba6f2bafaaebca731c30_cppui381,
92  0x19713e47937cd1be0dfd0b8f1d43fb93cd2fcbcb6caf493fd1183e416389e61031bf3a5cce3fbafce813711ad011c132_cppui381,
93  0x18b46a908f36f6deb918c143fed2edcc523559b8aaf0c2462e6bfe7f911f643249d9cdf41b44d606ce07c8a4d0074d8e_cppui381,
94  0xb182cac101b9399d155096004f53f447aa7b12a3426b08ec02710e807b4633f06c851c1919211f20d4c04f00b971ef8_cppui381,
95  0x245a394ad1eca9b72fc00ae7be315dc757b3b080d4c158013e6632d3c40659cc6cf90ad1c232a6442d9d3f5db980133_cppui381,
96  0x5c129645e44cf1102a159f748c4a3fc5e673d81d7e86568d9ab0f5d396a7ce46ba1049b6579afb7866b1e715475224b_cppui381,
97  0x15e6be4e990f03ce4ea50b3b42df2eb5cb181d8f84965a3957add4fa95af01b2b665027efec01c7704b456be69c8b604_cppui381};
98 
99  constexpr static std::array<integral_type, 15> k_y_den = {
100  0x16112c4c3a9c98b252181140fad0eae9601a6de578980be6eec3232b5be72e7a07f3688ef60c206d01479253b03663c1_cppui381,
101  0x1962d75c2381201e1a0cbd6c43c348b885c84ff731c4d59ca4a10356f453e01f78a4260763529e3532f6102c2e49a03d_cppui381,
102  0x58df3306640da276faaae7d6e8eb15778c4855551ae7f310c35a5dd279cd2eca6757cd636f96f891e2538b53dbf67f2_cppui381,
103  0x16b7d288798e5395f20d23bf89edb4d1d115c5dbddbcd30e123da489e726af41727364f2c28297ada8d26d98445f5416_cppui381,
104  0xbe0e079545f43e4b00cc912f8228ddcc6d19c9f0f69bbb0542eda0fc9dec916a20b15dc0fd2ededda39142311a5001d_cppui381,
105  0x8d9e5297186db2d9fb266eaac783182b70152c65550d881c5ecd87b6f0f5a6449f38db9dfa9cce202c6477faaf9b7ac_cppui381,
106  0x166007c08a99db2fc3ba8734ace9824b5eecfdfa8d0cf8ef5dd365bc400a0051d5fa9c01a58b1fb93d1a1399126a775c_cppui381,
107  0x16a3ef08be3ea7ea03bcddfabba6ff6ee5a4375efa1f4fd7feb34fd206357132b920f5b00801dee460ee415a15812ed9_cppui381,
108  0x1866c8ed336c61231a1be54fd1d74cc4f9fb0ce4c6af5920abc5750c4bf39b4852cfe2f7bb9248836b233d9d55535d4a_cppui381,
109  0x167a55cda70a6e1cea820597d94a84903216f763e13d87bb5308592e7ea7d4fbc7385ea3d529b35e346ef48bb8913f55_cppui381,
110  0x4d2f259eea405bd48f010a01ad2911d9c6dd039bb61a6290e591b36e636a5c871a5c29f4f83060400f8b49cba8f6aa8_cppui381,
111  0xaccbb67481d033ff5852c1e48c50c477f94ff8aefce42d28c0f9a88cea7913516f968986f7ebbea9684b529e2561092_cppui381,
112  0xad6b9514c767fe3c3613144b45f1496543346d98adf02267d5ceef9a00d9b8693000763e3b90ac11e99b138573345cc_cppui381,
113  0x2660400eb2e4f3b628bdd0d53cd76f2bf565b94e72927c1cb748df27942480e420517bd8714cc80d1fadc1326ed06f7_cppui381,
114  0xe0fa1d816ddc03e6b24255e0d7819c171c40f65e273b853324efcd6356caa205ca2f570f13497804415473a1d634b8f_cppui381};
115 
116  public:
117  static inline group_value_type process(const group_value_type &ci) {
118  field_value_type x_num = field_value_type::zero();
119  field_value_type x_den = field_value_type::zero();
120  field_value_type y_num = field_value_type::zero();
121  field_value_type y_den = field_value_type::zero();
122 
123  std::vector<field_value_type> xi_powers = [&ci]() {
124  std::vector<field_value_type> xi_powers {field_value_type::one()};
125  for (std::size_t i = 0; i < 15; i++) {
126  xi_powers.emplace_back(xi_powers.back() * ci.X);
127  }
128  return xi_powers;
129  }();
130 
131  for (std::size_t i = 0; i < k_x_den.size(); i++) {
132  x_den += field_value_type(k_x_den[i]) * xi_powers[i];
133  }
134  x_den += xi_powers[k_x_den.size()];
135 
136  for (std::size_t i = 0; i < k_y_den.size(); i++) {
137  y_den += field_value_type(k_y_den[i]) * xi_powers[i];
138  }
139  y_den += xi_powers[k_y_den.size()];
140 
141  if (x_den.is_zero() || y_den.is_zero()) {
142  return group_value_type::one();
143  }
144 
145  for (std::size_t i = 0; i < k_x_num.size(); i++) {
146  x_num += field_value_type(k_x_num[i]) * xi_powers[i];
147  }
148 
149  for (std::size_t i = 0; i < k_y_num.size(); i++) {
150  y_num += field_value_type(k_y_num[i]) * xi_powers[i];
151  }
152 
153  return group_value_type(x_num / x_den, ci.Y * y_num / y_den, field_value_type::one());
154  }
155  };
156 
157  // 3-isogeny map for BLS12-381 G2
158  // https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-10#appendix-E.3
159  template<>
160  class iso_map<typename bls12_381::g2_type<>> {
161  typedef typename bls12_381::g2_type<> group_type;
162  typedef h2c_suite<group_type> suite_type;
163 
164  typedef typename suite_type::group_value_type group_value_type;
165  typedef typename suite_type::field_value_type field_value_type;
166  typedef typename suite_type::integral_type integral_type;
167 
168  // TODO: change integral_type on field_value_type when constexpr will be finished
169  constexpr static std::array<std::array<integral_type, 2>, 4> k_x_num = {
170  {{{0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaaaaaaa97d6_cppui381,
171  0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaaaaaaa97d6_cppui381}},
172  {{0,
173  0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c6b4f20a4181472aaa9cb8d555526a9ffffffffc71a_cppui381}},
174  {{0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c6b4f20a4181472aaa9cb8d555526a9ffffffffc71e_cppui381,
175  0x8ab05f8bdd54cde190937e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ffffffffe38d_cppui381}},
176  {{0x171d6541fa38ccfaed6dea691f5fb614cb14b4e7f4e810aa22d6108f142b85757098e38d0f671c7188e2aaaaaaaa5ed1_cppui381,
177  0}}}};
178 
179  constexpr static std::array<std::array<integral_type, 2>, 2> k_x_den = {
180  {{{0,
181  0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa63_cppui381}},
182  {{0xc,
183  0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa9f_cppui381}}}};
184 
185  constexpr static std::array<std::array<integral_type, 2>, 4> k_y_num = {
186  {{{0x1530477c7ab4113b59a4c18b076d11930f7da5d4a07f649bf54439d87d27e500fc8c25ebf8c92f6812cfc71c71c6d706_cppui381,
187  0x1530477c7ab4113b59a4c18b076d11930f7da5d4a07f649bf54439d87d27e500fc8c25ebf8c92f6812cfc71c71c6d706_cppui381}},
188  {{0,
189  0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaaaaaaa97be_cppui381}},
190  {{0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c6b4f20a4181472aaa9cb8d555526a9ffffffffc71c_cppui381,
191  0x8ab05f8bdd54cde190937e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ffffffffe38f_cppui381}},
192  {{0x124c9ad43b6cf79bfbf7043de3811ad0761b0f37a1e26286b0e977c69aa274524e79097a56dc4bd9e1b371c71c718b10_cppui381,
193  0}}}};
194 
195  constexpr static std::array<std::array<integral_type, 2>, 3> k_y_den = {
196  {{{0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb_cppui381,
197  0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb_cppui381}},
198  {{0,
199  0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffa9d3_cppui381}},
200  {{0x12,
201  0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa99_cppui381}}}};
202 
203  public:
204  static inline group_value_type process(const group_value_type &ci) {
205  field_value_type x_num = field_value_type::zero();
206  field_value_type x_den = field_value_type::zero();
207  field_value_type y_num = field_value_type::zero();
208  field_value_type y_den = field_value_type::zero();
209 
210  std::vector<field_value_type> xi_powers = [&ci]() {
211  std::vector<field_value_type> xi_powers {field_value_type::one()};
212  for (std::size_t i = 0; i < 3; i++) {
213  auto v = xi_powers.back();
214  xi_powers.emplace_back(xi_powers.back() * ci.X);
215  }
216  return xi_powers;
217  }();
218 
219  for (std::size_t i = 0; i < k_x_den.size(); i++) {
220  x_den += field_value_type(k_x_den[i][0], k_x_den[i][1]) * xi_powers[i];
221  }
222  x_den += xi_powers[k_x_den.size()];
223 
224  for (std::size_t i = 0; i < k_y_den.size(); i++) {
225  y_den += field_value_type(k_y_den[i][0], k_y_den[i][1]) * xi_powers[i];
226  }
227  y_den += xi_powers[k_y_den.size()];
228 
229  if (x_den.is_zero() || y_den.is_zero()) {
230  return group_value_type::one();
231  }
232 
233  for (std::size_t i = 0; i < k_x_num.size(); i++) {
234  x_num += field_value_type(k_x_num[i][0], k_x_num[i][1]) * xi_powers[i];
235  }
236 
237  for (std::size_t i = 0; i < k_y_num.size(); i++) {
238  y_num += field_value_type(k_y_num[i][0], k_y_num[i][1]) * xi_powers[i];
239  }
240 
241  return group_value_type(x_num / x_den, ci.Y * y_num / y_den, field_value_type::one());
242  }
243  };
244  } // namespace detail
245  } // namespace curves
246  } // namespace algebra
247  } // namespace crypto3
248 } // namespace nil
249 
250 #endif // CRYPTO3_ALGEBRA_CURVES_HASH_TO_CURVE_ISO_MAP_HPP
h2c_suites.hpp
nil::crypto3::algebra::curves::bls12
A struct representing a BLS12-381 and BLS12-377 curve.
Definition: curves/bls12.hpp:49
nil::crypto3::algebra::curves::bls12::g2_type
typename detail::bls12_g2< Version, Form, Coordinates > g2_type
Definition: curves/bls12.hpp:63
nil::crypto3::algebra::curves::bls12::g1_type
typename detail::bls12_g1< Version, Form, Coordinates > g1_type
Definition: curves/bls12.hpp:59
nil::crypto3::algebra::curves::detail::iso_map< typename bls12_381::g1_type<> >::process
static group_value_type process(const group_value_type &ci)
Definition: h2c_iso_map.hpp:117
nil::crypto3::algebra::curves::detail::iso_map< typename bls12_381::g2_type<> >::process
static group_value_type process(const group_value_type &ci)
Definition: h2c_iso_map.hpp:204
nil
Definition: pair.hpp:31
nil::crypto3::algebra::curves::detail::h2c_suite
Definition: algebra/include/nil/crypto3/algebra/curves/detail/h2c/h2c_suites.hpp:48
nil::crypto3::algebra::curves::detail::iso_map
Definition: h2c_iso_map.hpp:41