# File timestamp (UTC): 2021-02-22T06:29:59.868 # NIST Circuit Complexity Project # https://csrc.nist.gov/projects/circuit-complexity begin circuit SKOP15-8x8-GF256--rs=1 # Boolean Circuit for a linear system y = A.x defined by a 64x64 bit-matrix A # Matrix A weights (W): totalW=832, adjW=768, minWInRow=9, maxWInRow=17, minWInCol=10, maxWICol=17 # Matrix represented as 64 rows: vecRows=UInt64[0xa9e1910408030201, 0x9101e10810060402, 0xe1020110200c0804, 0x0104022040181008, 0x0208044080302010, 0x04100880c3604020, 0x082010c345c08040, 0x104020458a43c380, 0xe1a9049103080102, 0x019108e106100204, 0x02e110010c200408, 0x0401200218400810, 0x0802400430801020, 0x1004800860c32040, 0x2008c310c0454080, 0x40104520438a80c3, 0x9104a9e102010803, 0xe108910104021006, 0x0110e1020804200c, 0x0220010410084018, 0x0440020820108030, 0x088004104020c360, 0x10c30820804045c0, 0x20451040c3808a43, 0x0491e1a901020308, 0x08e1019102040610, 0x100102e104080c20, 0x2002040108101840, 0x4004080210203080, 0x80081004204060c3, 0xc31020084080c045, 0x4520401080c3438a, 0x08030201a9e19104, 0x100604029101e108, 0x200c0804e1020110, 0x4018100801040220, 0x8030201002080440, 0xc360402004100880, 0x45c08040082010c3, 0x8a43c38010402045, 0x03080102e1a90491, 0x06100204019108e1, 0x0c20040802e11001, 0x1840081004012002, 0x3080102008024004, 0x60c3204010048008, 0xc04540802008c310, 0x438a80c340104520, 0x020108039104a9e1, 0x04021006e1089101, 0x0804200c0110e102, 0x1008401802200104, 0x2010803004400208, 0x4020c36008800410, 0x804045c010c30820, 0xc3808a4320451040, 0x010203080491e1a9, 0x0204061008e10191, 0x04080c20100102e1, 0x0810184020020401, 0x1020308040040802, 0x204060c380081004, 0x4080c045c3102008, 0x80c3438a45204010] # Matrix represented as 64 columns: vecCols=UInt64[0x0f0307c060818001, 0x10040840a0838102, 0x2008108140060204, 0x41102002810c0408, 0x8220410402180810, 0x0541820804301020, 0x048102d068e0a040, 0x07010360b040c080, 0x030fc00781600180, 0x0410400883a00281, 0x0820811006400402, 0x104102200c810804, 0x2082044118021008, 0x4105088230042010, 0x8104d002e06840a0, 0x0107600340b080c0, 0x07c00f0380016081, 0x084010048102a083, 0x1081200802044006, 0x200241100408810c, 0x4104822008100218, 0x8208054110200430, 0x02d00481a04068e0, 0x03600701c080b040, 0xc007030f01808160, 0x40080410028183a0, 0x8110082004020640, 0x0220104108040c81, 0x0441208210081802, 0x0882410520103004, 0xd002810440a0e068, 0x6003010780c040b0, 0x608180010f0307c0, 0xa083810210040840, 0x4006020420081081, 0x810c040841102002, 0x0218081082204104, 0x0430102005418208, 0x68e0a040048102d0, 0xb040c08007010360, 0x81600180030fc007, 0x83a0028104104008, 0x0640040208208110, 0x0c81080410410220, 0x1802100820820441, 0x3004201041050882, 0xe06840a08104d002, 0x40b080c001076003, 0x8001608107c00f03, 0x8102a08308401004, 0x0204400610812008, 0x0408810c20024110, 0x0810021841048220, 0x1020043082080541, 0xa04068e002d00481, 0xc080b04003600701, 0x01808160c007030f, 0x028183a040080410, 0x0402064081100820, 0x08040c8102201041, 0x1008180204412082, 0x2010300408824105, 0x40a0e068d0028104, 0x80c040b060030107] # 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, 445 gates (445 XOR) # Depth: 8 Inputs: x1:x64 Outputs: y1:y64 Internal: t1:t381 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 x40 x64 XOR t2 x16 x24 XOR t3 x8 x32 XOR t4 x48 x56 XOR t5 x2 x17 XOR t6 x1 x18 XOR t7 x10 x25 XOR t8 x9 x26 XOR t9 x34 x49 XOR t10 x33 x50 XOR t11 x41 x58 XOR t12 x42 x57 XOR t13 x33 x43 XOR t14 x19 x25 XOR t15 x17 x27 XOR t16 x51 x57 XOR t17 x3 x9 XOR t18 x49 x59 XOR t19 x35 x41 XOR t20 x15 t3 XOR t21 x8 x63 XOR t22 x7 t2 XOR t23 x16 x55 XOR t24 x39 t4 XOR t25 x23 x48 XOR t26 x1 x11 XOR t27 x47 t1 XOR t28 x31 x40 XOR t29 x15 t17 XOR t30 x39 t13 XOR t31 x47 t19 XOR t32 x7 t26 XOR t33 t9 t16 XOR t34 x14 x30 XOR t35 x38 x54 XOR t36 t7 t15 XOR t37 t11 t12 XOR t38 x6 x22 XOR t39 t5 t14 XOR t40 x46 x62 XOR t41 x21 t10 XOR t42 x4 x50 XOR t43 x53 t6 XOR t44 x18 x36 XOR t45 x61 t8 XOR t46 x26 x44 XOR t47 x27 x41 XOR t48 x23 x45 XOR t49 x38 x57 XOR t50 x5 x63 XOR t51 x31 x37 XOR t52 x55 t27 XOR t53 x8 t40 XOR t54 x16 t35 XOR t55 x54 t37 XOR t56 x63 t24 XOR t57 x31 t22 XOR t58 x13 x55 XOR t59 x29 t18 XOR t60 x6 x10 XOR t61 x34 x46 XOR t62 x48 t38 XOR t63 x2 x14 XOR t64 x23 t20 XOR t65 x40 t34 XOR t66 x34 t63 XOR t67 x28 x42 XOR t68 x12 x58 XOR t69 x29 t11 XOR t70 x56 t41 XOR t71 t42 t47 XOR t72 x3 x13 XOR t73 x47 x62 XOR t74 x20 x37 XOR t75 x22 t57 XOR t76 t17 t73 XOR t77 t25 t67 XOR t78 x32 t45 XOR t79 x30 x39 XOR t80 x1 t13 XOR t81 x51 t5 XOR t82 t2 t46 XOR t83 t52 t54 XOR t84 t14 t51 XOR t85 t6 t39 XOR t86 x12 x61 XOR t87 x30 t85 XOR t88 x24 t31 XOR t89 x4 x53 XOR t90 x54 t56 XOR t91 x53 t65 XOR t92 x42 t60 XOR t93 x10 t49 XOR t94 x5 x64 XOR t95 x35 x45 XOR t96 x21 x23 XOR t97 x25 x60 XOR t98 t23 t97 XOR t99 x14 t57 XOR t100 x26 x54 XOR t101 x4 t93 XOR t102 x6 t64 XOR t103 x2 t61 XOR t104 x60 t25 XOR t105 x17 t60 XOR t106 x37 x52 XOR t107 x36 t84 XOR t108 x43 t106 XOR t109 x24 t43 XOR t110 x59 t7 XOR t111 t15 t48 XOR t112 t8 t36 XOR t113 x22 t112 XOR t114 x61 t62 XOR t115 x7 x62 XOR t116 x33 t26 XOR t117 x12 t103 XOR t118 x39 x54 XOR t119 x28 t116 XOR t120 x19 t68 XOR t121 t4 t115 XOR t122 t3 t44 XOR t123 x44 t66 XOR t124 x55 x56 XOR t125 x22 x58 XOR t126 t37 t80 XOR t127 x60 t28 XOR t128 x13 x51 XOR t129 x59 t20 XOR t130 t18 t62 XOR t131 x35 t104 XOR t132 t14 t21 XOR t133 x13 x62 XOR t134 x52 t133 XOR t135 t10 t72 XOR t136 x11 x20 XOR t137 x41 t85 XOR t138 x20 x30 XOR t139 x5 x9 XOR t140 x51 t50 XOR t141 t134 t135 XOR t142 x45 x50 XOR t143 t9 t10 XOR t144 x64 t143 XOR t145 t33 t41 XOR t146 t19 t139 XOR t147 t81 t84 XOR t148 t86 t147 XOR y46 t53 t148 XOR t149 x16 t76 XOR t150 t53 t90 XOR t151 t71 t149 XOR y20 t74 t151 XOR t152 t75 t145 XOR t153 t53 t152 XOR y16 t73 t153 XOR t154 t54 t89 XOR t155 t110 t111 XOR y38 t154 t155 XOR t156 x15 t90 XOR t157 t87 t156 XOR y48 t91 t157 XOR t158 t52 t115 XOR t159 t113 t158 XOR y40 t114 t159 XOR t160 t77 t96 XOR t161 t140 t160 XOR y21 t101 t161 XOR t162 t1 t135 XOR t163 t61 t77 XOR t164 t162 t163 XOR y50 t12 t164 XOR t165 t6 t95 XOR t166 x18 t142 XOR t167 t63 t98 XOR t168 t3 t167 XOR y18 t165 t168 XOR t169 x8 x52 XOR t170 t123 t169 XOR t171 x61 t111 XOR y61 t170 t171 XOR t172 t73 t88 XOR t173 t50 t102 XOR t174 t143 t172 XOR y32 t173 t174 XOR t175 t8 t108 XOR t176 t21 t175 XOR t177 t105 t176 XOR y26 t2 t177 XOR t178 x4 t66 XOR t179 t81 t88 XOR t180 t69 t178 XOR y51 t179 t180 XOR t181 t40 t109 XOR t182 x28 t29 XOR t183 t95 t181 XOR y62 t182 t183 XOR t184 t118 t120 XOR t185 x45 t119 XOR t186 t184 t185 XOR y28 x8 t186 XOR t187 t34 t70 XOR t188 x60 t187 XOR t189 t72 t188 XOR y30 t31 t189 XOR t190 t54 t64 XOR t191 t55 t59 XOR t192 t190 t191 XOR y8 t79 t192 XOR t193 x16 x53 XOR t194 t107 t193 XOR t195 x60 t92 XOR y53 t194 t195 XOR t196 t127 t128 XOR t197 t82 t196 XOR t198 t75 t197 XOR y60 t80 t198 XOR t199 t7 t14 XOR t200 t141 t199 XOR t201 t28 t166 XOR y3 t200 t201 XOR t202 x5 t98 XOR t203 t22 t202 XOR t204 t150 t203 XOR y39 t36 t204 XOR t205 x43 t78 XOR t206 t32 t74 XOR t207 t35 t206 XOR y54 t205 t207 XOR t208 t55 t99 XOR t209 t13 t58 XOR t210 x32 t208 XOR y24 t209 t210 XOR t211 t59 t131 XOR t212 t105 t211 XOR t213 x44 t4 XOR y44 t212 t213 XOR t214 x20 t117 XOR t215 t58 t214 XOR t216 t59 t215 XOR y29 x40 t216 XOR t217 t20 t132 XOR t218 x2 t134 XOR t219 t217 t218 XOR y47 t83 t219 XOR t220 t124 t126 XOR t221 t5 t123 XOR t222 t220 t221 XOR y17 t129 t222 XOR t223 x18 t79 XOR t224 t78 t223 XOR t225 t81 t82 XOR y2 t224 t225 XOR t226 t121 t144 XOR t227 x33 t120 XOR t228 t69 t227 XOR y34 t226 t228 XOR t229 t70 t71 XOR t230 t1 t55 XOR t231 t229 t230 XOR y42 x15 t231 XOR t232 t56 t113 XOR t233 x46 t111 XOR t234 t232 t233 XOR t235 x64 t26 XOR y56 t234 t235 XOR t236 x57 t217 XOR t237 x15 t89 XOR t238 t136 t236 XOR t239 t61 t238 XOR y4 t237 t239 XOR t240 t47 t100 XOR t241 t74 t136 XOR t242 x2 t104 XOR t243 t241 t242 XOR y11 t240 t243 XOR t244 t41 t110 XOR t245 t30 t244 XOR t246 x12 t245 XOR t247 t92 t246 XOR y59 x32 t247 XOR t248 t122 t150 XOR t249 x29 x38 XOR t250 t149 t249 XOR t251 x31 t248 XOR y63 t250 t251 XOR t252 x19 t63 XOR t253 t107 t144 XOR t254 t252 t253 XOR t255 t145 t254 XOR y36 t108 t255 XOR t256 t46 t125 XOR t257 x32 t256 XOR t258 t29 t106 XOR t259 x53 t258 XOR y37 t257 t259 XOR t260 x11 t94 XOR t261 t38 t260 XOR t262 x52 t30 XOR t263 t261 t262 XOR y22 t69 t263 XOR t264 t27 t87 XOR t265 t84 t124 XOR t266 t17 t264 XOR t267 x38 t266 XOR y64 t265 t267 XOR t268 t33 t65 XOR t269 x19 x44 XOR t270 x29 t268 XOR t271 t50 t270 XOR y14 t269 t271 XOR t272 t65 t77 XOR t273 t18 t75 XOR t274 t24 t272 XOR t275 x37 t274 XOR y7 t273 t275 XOR t276 x7 x44 XOR t277 x27 t235 XOR t278 t276 t277 XOR t279 t43 t278 XOR y27 t93 t279 XOR t280 x22 t109 XOR t281 x26 t122 XOR t282 t110 t280 XOR t283 x47 t282 XOR y10 t281 t283 XOR t284 t91 t102 XOR t285 t13 t284 XOR t286 t68 t124 XOR t287 x7 t286 XOR y23 t285 t287 XOR t288 t31 t260 XOR t289 t136 t288 XOR t290 t68 t100 XOR t291 x21 t290 XOR y5 t289 t291 XOR t292 t165 t166 XOR t293 t128 t292 XOR t294 t21 t138 XOR t295 t293 t294 XOR y35 x42 t295 XOR t296 x30 x48 XOR t297 t122 t296 XOR t298 t129 t297 XOR t299 t146 t298 XOR y52 x52 t299 XOR t300 t12 t58 XOR t301 x49 t49 XOR t302 x27 t130 XOR t303 x36 t302 XOR t304 t300 t303 XOR y6 x21 t304 XOR t305 t82 t83 XOR t306 t26 t53 XOR t307 t96 t118 XOR t308 t306 t307 XOR y55 t305 t308 XOR t309 x49 t6 XOR t310 t121 t309 XOR t311 t21 t310 XOR t312 t112 t311 XOR y33 t119 t312 XOR t313 t136 t301 XOR t314 x5 t28 XOR t315 t4 t314 XOR t316 t37 t313 XOR y58 t315 t316 XOR t317 t32 t166 XOR t318 x36 t317 XOR t319 x61 t318 XOR t320 x24 x30 XOR t321 x60 t319 XOR y45 t320 t321 XOR t322 x36 t140 XOR t323 t22 t144 XOR t324 t7 t322 XOR t325 t92 t324 XOR t326 t146 t323 XOR y25 t325 t326 XOR t327 x31 t17 XOR t328 t101 t327 XOR t329 t137 t328 XOR t330 x32 t24 XOR t331 x25 t330 XOR y57 t329 t331 XOR t332 t19 t50 XOR t333 t94 t99 XOR t334 t332 t333 XOR t335 x15 t42 XOR t336 t114 t335 XOR y31 t334 t336 XOR t337 x18 t30 XOR t338 x29 t42 XOR t339 t337 t338 XOR t340 x28 t133 XOR t341 x56 t340 XOR y13 t339 t341 XOR t342 x34 x43 XOR t343 x59 t342 XOR t344 x28 t343 XOR t345 t139 t344 XOR t346 t23 t125 XOR y43 t345 t346 XOR t347 x20 t8 XOR t348 t29 t347 XOR t349 t137 t348 XOR t350 x47 t349 XOR t351 t83 t350 XOR y41 t49 t351 XOR t352 x24 x28 XOR t353 t27 t48 XOR t354 t28 t130 XOR t355 t129 t353 XOR t356 t33 t355 XOR t357 t138 t356 XOR y15 t354 t357 XOR t358 t72 t301 XOR t359 t15 t358 XOR t360 t352 t359 XOR t361 t86 t300 XOR y12 t360 t361 XOR t362 x56 t214 XOR t363 x19 t362 XOR t364 t9 t348 XOR t365 x36 t86 XOR t366 t363 t365 XOR y19 t364 t366 XOR t367 t33 t131 XOR t368 t141 t346 XOR t369 t76 t168 XOR t370 t63 t368 XOR t371 t367 t369 XOR y9 t370 t371 XOR t372 x17 t353 XOR t373 t9 t352 XOR t374 t112 t372 XOR t375 t373 t374 XOR t376 t117 t375 XOR y49 t185 t376 XOR t377 t2 t10 XOR t378 t18 t127 XOR t379 t79 t377 XOR t380 t126 t379 XOR t381 x17 t378 XOR y1 t380 t381 end SLP end circuit