# File timestamp (UTC): 2021-03-21T12:20:35.719 # NIST Circuit Complexity Project # https://csrc.nist.gov/projects/circuit-complexity begin circuit JPST17-4x4-GF256-inv--XOR=83--XZLBZ20 # SLP Source: https://doi.org/10.13154/tosc.v2020.i2.120-145 --- https://github.com/xiangzejun/Optimizing_Implementations_of_Linear_Layers # The preamble, metadata, SLP syntax and variable names have been adjusted here to the NIST format # Boolean Circuit for a linear system y = A.x defined by a 32x32 bit-matrix A # Matrix A weights (W): totalW=168, adjW=136, minWInRow=4, maxWInRow=7, minWInCol=7, maxWICol=4 # Matrix represented as 32 rows: vecRows=UInt32[0x010d0102, 0x02090204, 0x04010408, 0x08020803, 0x10d01020, 0x20902040, 0x40104080, 0x80208030, 0x0d090401, 0x09010802, 0x01020304, 0x02040608, 0xd0904010, 0x90108020, 0x10203040, 0x20406080, 0x01040f01, 0x02080d02, 0x04030904, 0x08060108, 0x1040f010, 0x2080d020, 0x40309040, 0x80601080, 0x02010109, 0x04020201, 0x08040402, 0x03080804, 0x20101090, 0x40202010, 0x80404020, 0x30808040] # Matrix represented as 32 columns: vecCols=UInt32[0x03010108, 0x04020209, 0x08040402, 0x01080804, 0x30101080, 0x40202090, 0x80404020, 0x10808040, 0x010f0401, 0x02010c02, 0x04030904, 0x08070208, 0x10f04010, 0x2010c020, 0x40309040, 0x80702080, 0x01040307, 0x020c0408, 0x04090801, 0x08020103, 0x10403070, 0x20c04080, 0x40908010, 0x80201030, 0x08010701, 0x09020802, 0x02040104, 0x04080308, 0x80107010, 0x90208020, 0x20401040, 0x40803080] # 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)) # Tally: 32 inputs, 32 outputs, 83 gates (83 XOR) # Circuit depth: 6 Inputs: x1:x32 Outputs: y1:y32 Internal: t1:t51 GateSyntax: GateName Output Inputs # Regex to obtain gate (\1), output var (\2) and input vars (\3, \4): (XOR)\s([ty]\d+)\s([tyx]\d+)\s([tyx]\d+).*$ begin SLP XOR t1 x32 x6 XOR t2 x12 x17 XOR t3 x25 x17 XOR t4 x11 x2 XOR t5 x2 x28 XOR t6 x28 x19 XOR t7 x17 t6 XOR t8 x31 x5 XOR t9 x6 x21 XOR t10 x21 x29 XOR t11 x14 x22 XOR t12 x5 x22 XOR t13 x10 x18 XOR y3 t6 t4 XOR t14 t12 x13 XOR t15 x13 t10 XOR t16 x18 x9 XOR t17 x29 x16 XOR t18 x22 t17 XOR t19 x9 t3 XOR t20 x16 x30 XOR t21 t9 x15 XOR t22 t13 x4 XOR t23 t4 x26 XOR t24 x15 x23 XOR t25 x30 t15 XOR t26 x26 t19 XOR t27 t19 t5 XOR t28 t3 x3 XOR t29 t15 t24 XOR y7 t24 t1 XOR t30 x3 x27 XOR y10 t23 t2 XOR t31 t17 x24 XOR t32 x27 x1 XOR t33 x1 t16 XOR y14 t20 t21 XOR t34 x23 t25 XOR y5 t25 x8 XOR t35 t16 t2 XOR y11 t30 t35 XOR t36 t21 t11 XOR y26 t35 t27 XOR t37 t11 t8 XOR t38 t27 x20 XOR y30 t18 t1 XOR y24 t1 t14 XOR t39 t8 t10 XOR t40 t10 x7 XOR t41 t14 x24 XOR t42 x24 t29 XOR t43 t2 x20 XOR y22 t42 y5 XOR y31 t34 t40 XOR y13 t29 t41 XOR t44 t38 y3 XOR t45 x19 t26 XOR y1 t26 x4 XOR y23 t39 t31 XOR y8 t31 x7 XOR y6 t37 x8 XOR y27 t45 t28 XOR y12 t7 t22 XOR y2 t22 t32 XOR y19 t32 t43 XOR t46 x20 t33 XOR y20 t5 t33 XOR y4 t43 t28 XOR t47 x4 y20 XOR t48 t47 y12 XOR y9 t33 t44 XOR y18 t44 y1 XOR t49 x8 y7 XOR y17 t28 t48 XOR t50 t40 y7 XOR y25 t48 y3 XOR y28 t46 y2 XOR t51 x7 t41 XOR y16 t49 t36 XOR y32 t41 y6 XOR y29 t36 y24 XOR y15 t51 y23 XOR y21 t50 y29 end SLP end circuit