# File timestamp (UTC): 2021-02-22T07:03:11.004 # NIST Circuit Complexity Project # https://csrc.nist.gov/projects/circuit-complexity begin circuit BKL16-8x8-GF256--rs=13 # Boolean Circuit for a linear system y = A.x defined by a 64x64 bit-matrix A # Matrix A weights (W): totalW=848, adjW=784, minWInRow=8, maxWInRow=18, minWInCol=11, maxWICol=15 # Matrix represented as 64 rows: vecRows=UInt64[0x01b202b208109e01, 0x0201040110205902, 0x040208022040b204, 0x0804100440800108, 0x1008200880650210, 0x2010401065ca0420, 0x40208020caf10840, 0x80406540f1871080, 0xb202b208109e0101, 0x0104011020590202, 0x0208022040b20404, 0x0410044080010808, 0x0820088065021010, 0x10401065ca042020, 0x208020caf1084040, 0x406540f187108080, 0x02b208109e0101b2, 0x0401102059020201, 0x08022040b2040402, 0x1004408001080804, 0x2008806502101008, 0x401065ca04202010, 0x8020caf108404020, 0x6540f18710808040, 0xb208109e0101b202, 0x0110205902020104, 0x022040b204040208, 0x0440800108080410, 0x0880650210100820, 0x1065ca0420201040, 0x20caf10840402080, 0x40f1871080804065, 0x08109e0101b202b2, 0x1020590202010401, 0x2040b20404020802, 0x4080010808041004, 0x8065021010082008, 0x65ca042020104010, 0xcaf1084040208020, 0xf187108080406540, 0x109e0101b202b208, 0x2059020201040110, 0x40b2040402080220, 0x8001080804100440, 0x6502101008200880, 0xca04202010401065, 0xf1084040208020ca, 0x87108080406540f1, 0x9e0101b202b20810, 0x5902020104011020, 0xb204040208022040, 0x0108080410044080, 0x0210100820088065, 0x04202010401065ca, 0x084040208020caf1, 0x108080406540f187, 0x0101b202b208109e, 0x0202010401102059, 0x04040208022040b2, 0x0808041004408001, 0x1010082008806502, 0x202010401065ca04, 0x4040208020caf108, 0x8080406540f18710] # Matrix represented as 64 columns: vecCols=UInt64[0x0ad0a00280020101, 0x15a0400501050202, 0x2190200882080404, 0x4320411004100808, 0x8741822108211010, 0x0452a44190412020, 0x0274e880a0804040, 0x05e8d00140018080, 0xd0a002800201010a, 0xa040050105020215, 0x9020088208040421, 0x2041100410080843, 0x4182210821101087, 0x52a4419041202004, 0x74e880a080404002, 0xe8d0014001808005, 0xa002800201010ad0, 0x40050105020215a0, 0x2008820804042190, 0x4110041008084320, 0x8221082110108741, 0xa441904120200452, 0xe880a08040400274, 0xd0014001808005e8, 0x02800201010ad0a0, 0x050105020215a040, 0x0882080404219020, 0x1004100808432041, 0x2108211010874182, 0x41904120200452a4, 0x80a08040400274e8, 0x014001808005e8d0, 0x800201010ad0a002, 0x0105020215a04005, 0x8208040421902008, 0x0410080843204110, 0x0821101087418221, 0x904120200452a441, 0xa08040400274e880, 0x4001808005e8d001, 0x0201010ad0a00280, 0x05020215a0400501, 0x0804042190200882, 0x1008084320411004, 0x2110108741822108, 0x4120200452a44190, 0x8040400274e880a0, 0x01808005e8d00140, 0x01010ad0a0028002, 0x020215a040050105, 0x0404219020088208, 0x0808432041100410, 0x1010874182210821, 0x20200452a4419041, 0x40400274e880a080, 0x808005e8d0014001, 0x010ad0a002800201, 0x0215a04005010502, 0x0421902008820804, 0x0843204110041008, 0x1087418221082110, 0x200452a441904120, 0x400274e880a08040, 0x8005e8d001400180] # The element in the i-th row and j-th col of A is A[i,j] = 1 & (vecRows[i]>>(j-1)) = 1 & (vecCols[j]>>(i-1)) # Matrix obtained from: https://github.com/rub-hgi/shorter_linear_slps_for_mds_matrices # Tally: 64 inputs, 64 outputs, 465 gates (465 XOR) # Depth: 10 Inputs: x1:x64 Outputs: y1:y64 Internal: t1:t401 GateSyntax: GateName Output Inputs # Regex find gate in new format: XOR\s([ty]\d+)\s([tyx]\d+)\s([tyx]\d+).*$ # Regex replacing to old format: \1 = XOR\(\2,\3\) begin SLP XOR t1 x48 x55 XOR t2 x40 x47 XOR t3 x56 x63 XOR t4 x32 x39 XOR t5 x7 x64 XOR t6 x8 x15 XOR t7 x16 x23 XOR t8 x24 x31 XOR t9 x9 x57 XOR t10 x1 x17 XOR t11 x33 x49 XOR t12 x3 x41 XOR t13 x25 x51 XOR t14 x38 x45 XOR t15 x22 x29 XOR t16 x54 x61 XOR t17 x30 x37 XOR t18 x5 x62 XOR t19 x6 x13 XOR t20 x35 t8 XOR t21 x46 x53 XOR t22 x19 t6 XOR t23 x14 x21 XOR t24 x43 t4 XOR t25 x11 t5 XOR t26 x27 t7 XOR t27 x59 t1 XOR t28 x17 x57 XOR t29 x2 t28 XOR t30 x33 x56 XOR t31 x10 x25 XOR t32 x1 x55 XOR t33 t3 t12 XOR t34 x26 x41 XOR t35 x8 x9 XOR t36 t2 t13 XOR t37 x48 x49 XOR t38 x24 x25 XOR t39 x34 x49 XOR t40 x15 t38 XOR t41 x40 x41 XOR t42 x31 t41 XOR t43 x48 t18 XOR t44 x18 t32 XOR t45 x32 x58 XOR t46 t21 t45 XOR t47 x17 x50 XOR t48 x4 t41 XOR t49 x20 x63 XOR t50 t10 t24 XOR t51 x39 x64 XOR t52 x23 x44 XOR t53 x8 t15 XOR t54 x16 t17 XOR t55 x39 t11 XOR t56 x2 x49 XOR t57 t11 t34 XOR t58 x18 t19 XOR t59 t25 t55 XOR t60 x13 t55 XOR t61 x3 t39 XOR t62 x24 x50 XOR t63 x7 x16 XOR t64 x28 t7 XOR t65 t63 t64 XOR t66 t9 t20 XOR t67 x42 x57 XOR t68 x63 t35 XOR t69 t54 t67 XOR t70 x9 x50 XOR t71 x30 t33 XOR t72 x46 t62 XOR t73 t4 t69 XOR t74 x11 x35 XOR t75 t37 t46 XOR t76 x56 x60 XOR t77 x1 t40 XOR t78 x22 t26 XOR t79 x59 t31 XOR t80 x61 t61 XOR t81 x37 t36 XOR t82 x64 t23 XOR t83 x39 t7 XOR t84 x30 x52 XOR t85 x17 t60 XOR t86 x13 t77 XOR t87 x21 t66 XOR t88 x43 x58 XOR t89 x38 t23 XOR t90 x5 x14 XOR t91 t36 t90 XOR t92 t9 t29 XOR t93 x58 t33 XOR t94 x14 x31 XOR t95 x3 t14 XOR t96 x36 x57 XOR t97 x26 t66 XOR t98 x27 t67 XOR t99 x4 t59 XOR t100 t6 t30 XOR t101 x47 t22 XOR t102 t58 t100 XOR t103 x54 t37 XOR t104 x22 t16 XOR t105 x12 t103 XOR t106 x22 t27 XOR t107 x54 t17 XOR t108 x7 t107 XOR t109 x44 t1 XOR t110 t40 t109 XOR t111 x5 t97 XOR t112 x54 x63 XOR t113 x42 x58 XOR t114 t13 t48 XOR t115 x38 x57 XOR t116 x10 t115 XOR t117 x51 t57 XOR t118 x45 t18 XOR t119 x53 t111 XOR t120 t15 t21 XOR t121 x52 t43 XOR t122 x14 x18 XOR t123 x6 x15 XOR t124 x56 t82 XOR t125 t42 t89 XOR t126 x51 x60 XOR t127 t28 t63 XOR t128 x12 t56 XOR t129 x62 t32 XOR t130 t5 t43 XOR t131 x60 t33 XOR t132 x6 x23 XOR t133 x40 x44 XOR t134 x2 t106 XOR t135 x62 t123 XOR t136 x34 t26 XOR t137 t39 t44 XOR t138 x6 x47 XOR t139 t8 t53 XOR t140 x29 t129 XOR t141 x7 x45 XOR t142 t108 t136 XOR t143 x30 x32 XOR t144 x1 t116 XOR t145 t75 t137 XOR t146 x9 t76 XOR y1 t145 t146 XOR t147 t119 t120 XOR t148 t22 t112 XOR y46 t147 t148 XOR t149 x62 t142 XOR t150 x13 t149 XOR y54 t50 t150 XOR t151 t94 t103 XOR t152 t99 t151 XOR y31 t102 t152 XOR t153 x30 t134 XOR t154 t59 t118 XOR y22 t153 t154 XOR t155 t56 t73 XOR t156 x18 t133 XOR y49 t155 t156 XOR t157 t68 t74 XOR t158 t58 t157 XOR y18 t117 t158 XOR t159 t108 t110 XOR t160 t46 t159 XOR y7 t81 t160 XOR t161 t52 t84 XOR t162 x6 t104 XOR t163 t80 t85 XOR y44 t161 t163 XOR t164 t93 t94 XOR t165 t104 t164 XOR y14 t81 t165 XOR t166 x35 t119 XOR t167 t110 t166 XOR t168 t106 t167 XOR y36 t96 t168 XOR t169 t37 t49 XOR t170 x11 t75 XOR t171 x40 t169 XOR t172 t78 t86 XOR y40 t171 t172 XOR t173 t14 t135 XOR t174 t87 t173 XOR t175 t36 t174 XOR y62 t67 t175 XOR t176 x20 x25 XOR t177 x16 t176 XOR t178 t102 t177 XOR y25 t113 t178 XOR t179 t140 t141 XOR t180 x20 t128 XOR t181 t179 t180 XOR y12 x35 t181 XOR t182 t15 t98 XOR t183 x51 t182 XOR t184 t77 t183 XOR y34 t61 t184 XOR t185 t54 t79 XOR t186 x46 t185 XOR t187 x20 t114 XOR y51 t186 t187 XOR t188 t70 t91 XOR t189 t80 t188 XOR t190 t71 t189 XOR y61 t49 t190 XOR t191 t64 t82 XOR t192 t62 t191 XOR t193 t56 t57 XOR y33 t192 t193 XOR t194 t92 t170 XOR t195 x27 t194 XOR t196 t4 t195 XOR y58 t13 t196 XOR t197 t65 t143 XOR t198 t30 t197 XOR t199 x48 t87 XOR y48 t198 t199 XOR t200 x53 t116 XOR t201 x28 t115 XOR t202 t19 t101 XOR t203 t200 t202 XOR y30 t71 t203 XOR t204 x61 t137 XOR t205 x46 t204 XOR t206 t89 t205 XOR t207 t25 t206 XOR y38 t136 t207 XOR t208 x53 t129 XOR t209 x16 t208 XOR t210 t38 t209 XOR t211 t51 t131 XOR y16 t210 t211 XOR t212 x15 x29 XOR t213 t125 t212 XOR t214 t50 t213 XOR t215 x36 t124 XOR y56 t214 t215 XOR t216 x34 t31 XOR t217 t47 t216 XOR t218 x8 x12 XOR t219 t217 t218 XOR y17 t130 t219 XOR t220 x59 t95 XOR t221 x24 t105 XOR t222 t220 t221 XOR t223 x18 x28 XOR y59 t222 t223 XOR t224 x24 t99 XOR t225 x19 t25 XOR t226 t68 t224 XOR t227 t4 t226 XOR t228 x61 t227 XOR y24 t138 t228 XOR t229 x62 t170 XOR t230 t34 t229 XOR t231 t169 t230 XOR t232 t96 t231 XOR y3 t93 t232 XOR t233 t45 t139 XOR t234 x10 x36 XOR t235 x41 t234 XOR t236 t39 t233 XOR y41 t235 t236 XOR t237 t35 t121 XOR t238 x14 x19 XOR t239 t98 t237 XOR t240 t238 t239 XOR y19 t96 t240 XOR t241 x19 t95 XOR t242 t70 t88 XOR t243 t241 t242 XOR t244 t10 t243 XOR y50 t42 t244 XOR t245 x38 t128 XOR t246 t126 t245 XOR t247 t24 t246 XOR t248 t53 t247 XOR y43 t55 t248 XOR t249 t47 t78 XOR t250 t76 t249 XOR t251 x35 t52 XOR t252 t19 t250 XOR y27 t251 t252 XOR t253 t57 t162 XOR t254 x42 t253 XOR t255 x53 t105 XOR t256 t50 t254 XOR y53 t255 t256 XOR t257 t118 t122 XOR t258 t39 t119 XOR t259 t114 t117 XOR t260 t258 t259 XOR y45 t257 t260 XOR t261 t2 t118 XOR t262 x26 t62 XOR t263 t144 t261 XOR t264 t121 t262 XOR y57 t263 t264 XOR t265 x55 t68 XOR t266 x28 t89 XOR t267 t73 t265 XOR t268 t87 t266 XOR y55 t267 t268 XOR t269 x46 t37 XOR t270 t52 t269 XOR t271 t51 t81 XOR t272 t270 t271 XOR y64 t35 t272 XOR t273 t91 t126 XOR t274 x11 t125 XOR t275 x42 t274 XOR t276 x52 t273 XOR y52 t275 t276 XOR t277 t16 t101 XOR t278 t79 t277 XOR t279 t100 t278 XOR t280 x35 t279 XOR y2 t29 t280 XOR t281 t51 t106 XOR t282 t201 t281 XOR t283 t85 t282 XOR t284 x5 t113 XOR y5 t283 t284 XOR t285 x10 t131 XOR t286 t130 t285 XOR t287 t132 t286 XOR t288 x46 t42 XOR y23 t287 t288 XOR t289 x4 t251 XOR t290 x29 t224 XOR t291 x31 x54 XOR t292 t82 t88 XOR t293 t289 t292 XOR t294 t38 t161 XOR y35 t293 t294 XOR t295 x55 t225 XOR t296 t290 t295 XOR t297 x13 t72 XOR t298 x60 t297 XOR y60 t296 t298 XOR t299 x21 t77 XOR t300 t96 t297 XOR t301 t71 t300 XOR t302 t6 t301 XOR t303 t299 t302 XOR y13 x2 t303 XOR t304 t34 t220 XOR t305 x43 t39 XOR t306 t304 t305 XOR t307 t23 t127 XOR t308 t306 t307 XOR y26 t241 t308 XOR t309 x62 t104 XOR t310 x12 t309 XOR t311 t83 t124 XOR t312 x26 t310 XOR t313 t311 t312 XOR y39 t277 t313 XOR t314 t70 t157 XOR t315 t32 t83 XOR t316 x59 t267 XOR t317 t314 t315 XOR t318 x33 t317 XOR y42 t316 t318 XOR t319 t83 t290 XOR t320 t87 t144 XOR t321 t289 t291 XOR t322 t319 t321 XOR t323 x58 t320 XOR y21 t322 t323 XOR t324 x45 t65 XOR t325 x51 t10 XOR t326 x61 t324 XOR t327 x36 t326 XOR t328 t122 t327 XOR y28 t325 t328 XOR t329 t49 t200 XOR t330 x37 t201 XOR t331 t329 t330 XOR t332 x43 t331 XOR t333 t9 t332 XOR y20 t123 t333 XOR t334 t98 t112 XOR t335 x21 t81 XOR t336 t334 t335 XOR t337 x12 t113 XOR t338 t336 t337 XOR y4 t114 t338 XOR t339 t65 t132 XOR t340 x34 t133 XOR t341 t32 t340 XOR t342 t295 t341 XOR t343 t339 t342 XOR y11 t16 t343 XOR t344 x32 x55 XOR t345 x12 t22 XOR t346 t127 t345 XOR t347 t41 t346 XOR t348 t344 t347 XOR y32 t90 t348 XOR t349 t16 t92 XOR t350 x42 t349 XOR t351 t34 t350 XOR t352 t3 t48 XOR t353 x64 t352 XOR y9 t351 t353 XOR t354 x64 t143 XOR t355 t138 t344 XOR t356 x20 t354 XOR t357 t139 t356 XOR t358 t136 t355 XOR y47 t357 t358 XOR t359 t120 t132 XOR t360 x14 t359 XOR t361 t47 t360 XOR t362 x33 t106 XOR t363 t24 t361 XOR y6 t362 t363 XOR t364 t143 t161 XOR t365 t3 t135 XOR t366 t133 t365 XOR t367 x38 t364 XOR t368 t134 t366 XOR t369 t367 t368 XOR y15 t162 t369 XOR t370 x64 t11 XOR t371 x27 t137 XOR t372 t18 t371 XOR t373 t370 t372 XOR t374 x43 t373 XOR t375 t12 t374 XOR y10 t216 t375 XOR t376 t218 t291 XOR t377 t30 t346 XOR t378 x52 t27 XOR t379 t141 t376 XOR t380 t101 t379 XOR t381 t377 t380 XOR y8 t378 t381 XOR t382 x22 t14 XOR t383 t63 t72 XOR t384 t2 t383 XOR t385 t24 t382 XOR t386 x36 t385 XOR t387 x63 t384 XOR y63 t386 t387 XOR t388 x26 t142 XOR t389 x49 t143 XOR t390 x60 t389 XOR t391 t10 t388 XOR t392 t216 t390 XOR t393 x6 t391 XOR t394 t141 t392 XOR y37 t393 t394 XOR t395 t29 t140 XOR t396 t72 t84 XOR t397 t44 t395 XOR t398 t70 t396 XOR t399 t397 t398 XOR t400 t17 t22 XOR t401 x41 t399 XOR y29 t400 t401 end SLP end circuit