# File timestamp (UTC): 2021-02-22T06:48:43.767 # NIST Circuit Complexity Project # https://csrc.nist.gov/projects/circuit-complexity begin circuit Fox_Mu8--rs=1 # Boolean Circuit for a linear system y = A.x defined by a 64x64 bit-matrix A # Matrix A weights (W): totalW=1321, adjW=1257, minWInRow=9, maxWInRow=31, minWInCol=9, maxWICol=26 # Matrix represented as 64 rows: vecRows=UInt64[0x7efc040282030101, 0xfce308041f060202, 0xe3dd10083e0c0404, 0xdda120107c180808, 0xa1594020f8301010, 0x59b28040eb602020, 0xb27f1b80cdc04040, 0x7ffe361b819b8080, 0x017efc0402820301, 0x02fce308041f0602, 0x04e3dd10083e0c04, 0x08dda120107c1808, 0x10a1594020f83010, 0x2059b28040eb6020, 0x40b27f1b80cdc040, 0x807ffe361b819b80, 0x03017efc04028201, 0x0602fce308041f02, 0x0c04e3dd10083e04, 0x1808dda120107c08, 0x3010a1594020f810, 0x602059b28040eb20, 0xc040b27f1b80cd40, 0x9b807ffe361b8180, 0x8203017efc040201, 0x1f0602fce3080402, 0x3e0c04e3dd100804, 0x7c1808dda1201008, 0xf83010a159402010, 0xeb602059b2804020, 0xcdc040b27f1b8040, 0x819b807ffe361b80, 0x028203017efc0401, 0x041f0602fce30802, 0x083e0c04e3dd1004, 0x107c1808dda12008, 0x20f83010a1594010, 0x40eb602059b28020, 0x80cdc040b27f1b40, 0x1b819b807ffe3680, 0x04028203017efc01, 0x08041f0602fce302, 0x10083e0c04e3dd04, 0x20107c1808dda108, 0x4020f83010a15910, 0x8040eb602059b220, 0x1b80cdc040b27f40, 0x361b819b807ffe80, 0xfc04028203017e01, 0xe308041f0602fc02, 0xdd10083e0c04e304, 0xa120107c1808dd08, 0x594020f83010a110, 0xb28040eb60205920, 0x7f1b80cdc040b240, 0xfe361b819b807f80, 0x0101010101010103, 0x0202020202020206, 0x040404040404040c, 0x0808080808080818, 0x1010101010101030, 0x2020202020202060, 0x40404040404040c0, 0x808080808080809b] # Matrix represented as 64 columns: vecCols=UInt64[0x8101010101010101, 0x8302020202020202, 0x0604040404040404, 0x8c08080808080808, 0x9810101010101010, 0x3020202020202020, 0x6040404040404040, 0xc080808080808080, 0x01bc5e4080e28101, 0x02c5e2c081278302, 0x048bc581024e0604, 0x08abd542847e8c08, 0x10ebf5c4881e9810, 0x20d7eb88103c3020, 0x40afd71020786040, 0x805eaf2040f1c080, 0x0101bc5e4080e281, 0x0202c5e2c0812783, 0x04048bc581024e06, 0x0808abd542847e8c, 0x1010ebf5c4881e98, 0x2020d7eb88103c30, 0x4040afd710207860, 0x80805eaf2040f1c0, 0x018101bc5e4080e2, 0x028302c5e2c08127, 0x0406048bc581024e, 0x088c08abd542847e, 0x109810ebf5c4881e, 0x203020d7eb88103c, 0x406040afd7102078, 0x80c0805eaf2040f1, 0x01e28101bc5e4080, 0x02278302c5e2c081, 0x044e06048bc58102, 0x087e8c08abd54284, 0x101e9810ebf5c488, 0x203c3020d7eb8810, 0x40786040afd71020, 0x80f1c0805eaf2040, 0x0180e28101bc5e40, 0x0281278302c5e2c0, 0x04024e06048bc581, 0x08847e8c08abd542, 0x10881e9810ebf5c4, 0x20103c3020d7eb88, 0x4020786040afd710, 0x8040f1c0805eaf20, 0x014080e28101bc5e, 0x02c081278302c5e2, 0x0481024e06048bc5, 0x0842847e8c08abd5, 0x10c4881e9810ebf5, 0x2088103c3020d7eb, 0x401020786040afd7, 0x802040f1c0805eaf, 0x015e4080e28101bc, 0x02e2c081278302c5, 0x04c581024e06048b, 0x08d542847e8c08ab, 0x10f5c4881e9810eb, 0x20eb88103c3020d7, 0x40d71020786040af, 0x80af2040f1c0805e] # 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, 540 gates (540 XOR) # Depth: 14 Inputs: x1:x64 Outputs: y1:y64 Internal: t1:t476 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 x16 x56 XOR t2 x24 x40 XOR t3 x8 x48 XOR t4 x32 x39 XOR t5 x4 x31 XOR t6 x7 x36 XOR t7 x28 x55 XOR t8 x23 x52 XOR t9 x20 x47 XOR t10 x15 x44 XOR t11 x2 x51 XOR t12 x35 x42 XOR t13 x19 x26 XOR t14 x11 x18 XOR t15 x27 x34 XOR t16 x43 x50 XOR t17 x3 x10 XOR t18 x25 x33 XOR t19 x1 x9 XOR t20 x41 x49 XOR t21 x12 t4 XOR t22 x13 x46 XOR t23 x21 x54 XOR t24 x5 x38 XOR t25 x22 x45 XOR t26 x6 x29 XOR t27 x30 x53 XOR t28 x14 x37 XOR t29 x40 x48 XOR t30 x17 x24 XOR t31 x32 t3 XOR t32 t10 t30 XOR t33 t1 t6 XOR t34 x56 t7 XOR t35 x14 t29 XOR t36 x1 t34 XOR t37 t2 t5 XOR t38 t21 t24 XOR t39 t9 t14 XOR t40 t8 t16 XOR t41 t3 t36 XOR t42 x16 t32 XOR t43 x11 t38 XOR t44 x34 t35 XOR t45 x3 t37 XOR t46 t11 t41 XOR t47 x50 x51 XOR t48 x2 t33 XOR t49 t13 t31 XOR t50 x9 x19 XOR t51 x26 x27 XOR t52 x18 t51 XOR t53 x35 t51 XOR t54 x15 x23 XOR t55 x33 x41 XOR t56 t12 t55 XOR t57 x42 x58 XOR t58 x10 x46 XOR t59 x13 t43 XOR t60 x5 x37 XOR t61 x59 t15 XOR t62 x17 x57 XOR t63 x25 t49 XOR t64 t13 t20 XOR t65 x47 x55 XOR t66 t18 t45 XOR t67 t10 t56 XOR t68 x31 x39 XOR t69 x48 t27 XOR t70 x53 t9 XOR t71 x43 t3 XOR t72 x47 t30 XOR t73 x63 t31 XOR t74 t28 t58 XOR t75 t22 t39 XOR t76 t17 t29 XOR t77 t1 t40 XOR t78 t64 t77 XOR t79 t7 t23 XOR t80 x6 t50 XOR t81 x9 t33 XOR t82 x23 x45 XOR t83 x49 t46 XOR t84 x25 t4 XOR t85 x29 t8 XOR t86 x6 x62 XOR t87 t26 t83 XOR t88 t48 t85 XOR t89 x7 x22 XOR t90 x19 t89 XOR t91 t12 t19 XOR t92 t52 t72 XOR t93 x54 t92 XOR t94 x21 x42 XOR t95 x63 t54 XOR t96 x52 t45 XOR t97 t15 t66 XOR t98 t25 t75 XOR t99 x53 t93 XOR t100 x36 t44 XOR t101 t37 t87 XOR t102 x64 t35 XOR t103 x3 x56 XOR t104 x12 t76 XOR t105 x5 t47 XOR t106 x10 t11 XOR t107 x49 t84 XOR t108 x43 x58 XOR t109 t57 t100 XOR t110 x30 t86 XOR t111 x22 x46 XOR t112 t22 t26 XOR t113 t53 t60 XOR t114 t110 t113 XOR t115 x26 t78 XOR t116 x38 t82 XOR t117 t71 t74 XOR t118 t90 t94 XOR t119 x16 t70 XOR t120 x61 t60 XOR t121 t16 t61 XOR t122 t63 t91 XOR t123 t18 t62 XOR t124 x54 t24 XOR t125 t28 t110 XOR t126 t49 t96 XOR t127 x62 t68 XOR t128 x7 t65 XOR t129 t103 t123 XOR t130 t14 t67 XOR t131 x16 t39 XOR t132 x55 t48 XOR t133 x20 t99 XOR t134 t69 t101 XOR t135 x60 t12 XOR t136 t59 t74 XOR t137 t67 t136 XOR t138 x60 t24 XOR t139 t25 t38 XOR t140 x8 t24 XOR t141 t88 t97 XOR t142 x17 t106 XOR t143 x4 t59 XOR t144 t69 t80 XOR t145 x40 t107 XOR t146 t47 t62 XOR t147 t57 t142 XOR t148 t27 t139 XOR t149 t33 t104 XOR t150 t27 t79 XOR t151 x51 t119 XOR t152 t69 t115 XOR t153 t23 t101 XOR t154 t2 t73 XOR t155 x61 t70 XOR t156 x13 x31 XOR t157 t32 t81 XOR t158 t98 t157 XOR t159 x28 x40 XOR t160 x23 t48 XOR t161 t118 t151 XOR t162 x44 t35 XOR t163 t132 t162 XOR t164 x47 t117 XOR t165 t43 t116 XOR t166 x30 x64 XOR t167 t15 t138 XOR t168 x8 t42 XOR t169 t42 t68 XOR t170 x60 x64 XOR t171 x21 t120 XOR t172 x29 x53 XOR t173 x55 t21 XOR t174 x11 t108 XOR t175 x41 t44 XOR t176 x31 t140 XOR t177 t16 t17 XOR t178 t41 t177 XOR t179 t8 t63 XOR t180 x33 t143 XOR t181 x4 x12 XOR t182 x51 t94 XOR t183 t54 t64 XOR t184 x1 x2 XOR t185 t95 t128 XOR y7 t127 t185 XOR t186 t1 t154 XOR y8 x64 t186 XOR t187 t126 t138 XOR y20 t137 t187 XOR t188 t124 t125 XOR t189 t120 t188 XOR y6 t111 t189 XOR t190 t39 t121 XOR t191 t91 t190 XOR y43 t168 t191 XOR t192 t129 t180 XOR t193 t100 t192 XOR y49 t132 t193 XOR t194 t141 t148 XOR t195 x61 t90 XOR y29 t194 t195 XOR t196 t61 t122 XOR t197 t145 t149 XOR y51 t196 t197 XOR t198 x64 t20 XOR t199 t19 t123 XOR y1 t198 t199 XOR t200 x43 t135 XOR t201 t11 t158 XOR t202 t159 t200 XOR y44 t201 t202 XOR t203 t5 t14 XOR t204 t61 t64 XOR t205 t46 t203 XOR y59 t204 t205 XOR t206 t52 t147 XOR t207 t15 t206 XOR t208 x64 t207 XOR y2 t146 t208 XOR t209 x33 t76 XOR t210 t78 t131 XOR t211 x59 t209 XOR y11 t210 t211 XOR t212 x45 t170 XOR t213 t172 t212 XOR t214 x13 t171 XOR y5 t213 t214 XOR t215 t121 t142 XOR t216 t66 t215 XOR t217 x32 t216 XOR y27 t6 t217 XOR t218 t15 t196 XOR t219 t77 t218 XOR t220 t30 t219 XOR y35 t46 t220 XOR t221 t11 t104 XOR t222 x59 t84 XOR t223 t221 t222 XOR y19 t130 t223 XOR t224 x5 t146 XOR t225 t144 t224 XOR t226 t126 t225 XOR y57 t65 t226 XOR t227 t80 t163 XOR t228 t130 t227 XOR t229 t109 t228 XOR t230 x38 t229 XOR y50 t63 t230 XOR t231 x27 t13 XOR t232 t134 t231 XOR t233 x12 t9 XOR t234 t135 t232 XOR y60 t233 t234 XOR t235 t23 t152 XOR t236 x21 t82 XOR t237 t161 t235 XOR t238 t95 t237 XOR t239 t28 t236 XOR y15 t238 t239 XOR t240 t39 t167 XOR t241 x4 t148 XOR t242 t235 t241 XOR y12 t240 t242 XOR t243 x43 t51 XOR t244 t153 t243 XOR t245 t6 t155 XOR t246 t244 t245 XOR y61 t156 t246 XOR t247 t98 t169 XOR t248 x63 t247 XOR t249 t50 t124 XOR t250 t80 t184 XOR t251 x10 t248 XOR y47 t249 t251 XOR t252 x3 t174 XOR t253 x51 t13 XOR t254 t53 t253 XOR t255 t252 t254 XOR y3 x59 t255 XOR t256 t165 t175 XOR t257 t81 t166 XOR t258 t256 t257 XOR t259 t137 t258 XOR y24 t164 t259 XOR t260 x61 t85 XOR t261 x42 t164 XOR t262 t76 t261 XOR t263 t158 t262 XOR y45 t260 t263 XOR t264 t21 t81 XOR t265 t167 t178 XOR t266 t28 t264 XOR t267 x20 t265 XOR t268 x35 t266 XOR y52 t267 t268 XOR t269 t19 t73 XOR t270 t136 t156 XOR t271 t103 t270 XOR t272 t160 t269 XOR t273 t69 t272 XOR y55 t271 t273 XOR t274 t71 t109 XOR t275 x33 t274 XOR t276 t183 t275 XOR t277 t30 t33 XOR t278 t58 t276 XOR y42 t277 t278 XOR t279 t113 t159 XOR t280 t20 t26 XOR t281 t176 t279 XOR t282 t160 t281 XOR t283 x57 t282 XOR y25 t280 t283 XOR t284 t161 t280 XOR t285 x50 t284 XOR t286 t163 t285 XOR t287 x62 t22 XOR t288 x2 t286 XOR y14 t287 t288 XOR t289 x40 t75 XOR t290 x61 t152 XOR t291 t289 t290 XOR t292 t150 t291 XOR t293 x35 t292 XOR y13 t165 t293 XOR t294 t74 t239 XOR t295 t173 t294 XOR t296 t131 t295 XOR t297 x41 t80 XOR t298 x38 t144 XOR t299 t296 t297 XOR y48 t102 t299 XOR t300 x27 x44 XOR t301 t96 t153 XOR t302 t105 t300 XOR t303 t125 t302 XOR t304 t89 t303 XOR y62 t301 t304 XOR t305 x51 x60 XOR t306 t150 t305 XOR t307 t177 t306 XOR t308 x36 t307 XOR t309 t32 t308 XOR y36 t179 t309 XOR t310 x14 t137 XOR t311 t3 t310 XOR t312 t10 t155 XOR t313 t37 t311 XOR t314 t300 t313 XOR y21 t312 t314 XOR t315 x15 x18 XOR t316 t30 t118 XOR t317 t75 t129 XOR t318 t315 t317 XOR t319 t316 t318 XOR y41 t104 t319 XOR t320 x28 t133 XOR t321 x44 t99 XOR t322 t22 t92 XOR t323 t97 t322 XOR t324 t4 t320 XOR t325 t114 t324 XOR y30 t323 t325 XOR t326 x31 t90 XOR t327 x29 t133 XOR t328 x49 t326 XOR t329 t102 t327 XOR t330 t34 t328 XOR y40 t329 t330 XOR t331 x38 t2 XOR t332 x3 t25 XOR t333 x50 t332 XOR t334 t134 t333 XOR t335 t95 t331 XOR y63 t334 t335 XOR t336 t42 t117 XOR t337 x18 t181 XOR t338 t236 t298 XOR t339 t336 t337 XOR t340 t86 t339 XOR y46 t338 t340 XOR t341 x63 t8 XOR t342 t150 t322 XOR t343 x6 t341 XOR t344 x19 t343 XOR t345 t84 t342 XOR y39 t344 t345 XOR t346 x25 t127 XOR t347 t93 t151 XOR t348 x46 t347 XOR t349 t85 t139 XOR t350 x15 t114 XOR t351 t348 t349 XOR y38 t346 t351 XOR t352 x62 t100 XOR t353 t41 t89 XOR t354 t102 t350 XOR t355 t352 t353 XOR t356 t84 t354 XOR y32 t355 t356 XOR t357 x52 x59 XOR t358 t181 t321 XOR t359 t170 t320 XOR t360 x36 t359 XOR t361 t357 t358 XOR y4 t360 t361 XOR t362 t27 t159 XOR t363 t18 t99 XOR t364 x7 t108 XOR t365 t363 t364 XOR t366 t178 t365 XOR y58 t362 t366 XOR t367 t91 t146 XOR t368 t4 t53 XOR t369 t321 t367 XOR t370 t25 t77 XOR t371 t368 t369 XOR y9 t370 t371 XOR t372 t55 t109 XOR t373 t128 t364 XOR t374 t59 t373 XOR t375 t79 t374 XOR t376 x45 t375 XOR t377 t372 t376 XOR y22 t86 t377 XOR t378 x36 t166 XOR t379 t145 t378 XOR t380 x46 t105 XOR t381 x54 t380 XOR t382 x31 t111 XOR t383 t88 t379 XOR t384 t45 t381 XOR y64 t383 t384 XOR t385 x48 t206 XOR t386 t231 t385 XOR t387 t257 t379 XOR t388 t111 t128 XOR t389 t387 t388 XOR y10 t386 t389 XOR t390 x28 t43 XOR t391 t169 t171 XOR t392 t179 t391 XOR t393 t241 t392 XOR t394 t105 t393 XOR t395 x39 t390 XOR y37 t394 t395 XOR t396 t18 t153 XOR t397 t100 t154 XOR t398 t83 t396 XOR t399 t53 t140 XOR t400 t398 t399 XOR t401 t397 t400 XOR y31 t128 t401 XOR t402 t349 t399 XOR t403 x35 t402 XOR t404 x10 t143 XOR t405 t19 t404 XOR t406 t160 t405 XOR t407 t350 t403 XOR y54 t406 t407 XOR t408 t182 t297 XOR t409 t40 t298 XOR t410 t168 t408 XOR t411 x55 t409 XOR t412 t166 t410 XOR t413 t382 t412 XOR y16 t411 t413 XOR t414 t67 t71 XOR t415 x37 t44 XOR t416 t73 t89 XOR t417 t414 t415 XOR t418 t173 t417 XOR t419 t112 t416 XOR y23 t418 t419 XOR t420 t106 t175 XOR t421 t4 t72 XOR t422 t105 t174 XOR t423 t176 t420 XOR t424 t19 t421 XOR t425 t422 t423 XOR y18 t424 t425 XOR t426 x32 t347 XOR t427 t138 t426 XOR t428 x24 t427 XOR t429 x6 t321 XOR t430 t131 t141 XOR t431 t428 t430 XOR y28 t429 t431 XOR t432 t4 t250 XOR t433 t96 t432 XOR t434 t56 t78 XOR t435 x4 t108 XOR t436 t434 t435 XOR t437 t433 t436 XOR y26 x30 t437 XOR t438 t10 t44 XOR t439 t7 t120 XOR t440 t26 t182 XOR t441 t31 t91 XOR t442 t438 t439 XOR t443 t441 t442 XOR t444 t440 t443 XOR y53 t149 t444 XOR t445 x49 t68 XOR t446 x1 x45 XOR t447 x34 x35 XOR t448 t62 t336 XOR t449 t446 t448 XOR t450 t445 t447 XOR t451 x36 t449 XOR y17 t450 t451 XOR t452 t49 t72 XOR t453 x56 t150 XOR t454 x50 x54 XOR t455 t54 t454 XOR t456 x57 t453 XOR t457 t327 t455 XOR t458 t55 t457 XOR t459 t452 t458 XOR y33 t456 t459 XOR t460 t17 t249 XOR t461 t2 t176 XOR t462 x15 t461 XOR t463 x47 x64 XOR t464 t180 t463 XOR t465 t460 t462 XOR t466 t60 t250 XOR t467 t464 t465 XOR y56 t466 t467 XOR t468 t51 t382 XOR t469 t183 t207 XOR t470 x16 t468 XOR t471 x5 t381 XOR t472 t142 t470 XOR t473 t471 t472 XOR t474 t63 t469 XOR t475 x1 t474 XOR t476 x24 t473 XOR y34 t475 t476 end SLP end circuit