# File timestamp (UTC): 2021-02-22T18:39:33.293 # NIST Circuit Complexity Project # https://csrc.nist.gov/projects/circuit-complexity begin circuit SS16-4x4-GF16--rs=111 # Boolean Circuit for a linear system y = A.x defined by a 16x16 bit-matrix A # Matrix A weights (W): totalW=74, adjW=58, minWInRow=4, maxWInRow=6, minWInCol=4, maxWICol=6 # Matrix represented as 16 rows: vecRows=UInt16[0xc161, 0x12c2, 0x2414, 0x4828, 0x1611, 0x2c22, 0x4144, 0x8288, 0x6112, 0xc224, 0x1448, 0x2889, 0x112c, 0x2241, 0x4482, 0x8894] # Matrix represented as 16 columns: vecCols=UInt16[0x2811, 0x4122, 0x9244, 0x1c88, 0x8114, 0x1229, 0x2443, 0xc882, 0x1141, 0x2292, 0x4434, 0x8828, 0x1412, 0x2924, 0x4349, 0x8281] # 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: 16 inputs, 16 outputs, 41 gates (41 XOR) # Depth: 5 Inputs: x1:x16 Outputs: y1:y16 Internal: t1:t25 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 x1 x10 XOR t2 x6 x15 XOR t3 x4 t1 XOR t4 x8 x12 XOR t5 x2 x11 XOR t6 x12 x14 XOR t7 x3 x5 XOR t8 x7 x13 XOR t9 x2 t4 XOR t10 x5 t6 XOR y1 x1 t10 XOR t11 x13 t5 XOR y13 x5 t11 XOR t12 x1 t8 XOR y9 x9 t12 XOR t13 x9 t7 XOR y5 x16 t13 XOR t14 x16 t1 XOR y16 x8 t14 XOR t15 x6 t3 XOR y6 x13 t15 XOR t16 x9 t2 XOR y2 x2 t16 XOR t17 t8 t16 XOR y15 y6 t17 XOR t18 t11 t12 XOR y7 x14 t18 XOR t19 x12 t14 XOR y12 t15 t19 XOR t20 t5 y2 XOR y11 t13 t20 XOR t21 t1 t9 XOR y10 y1 t21 XOR t22 x3 t14 XOR y3 t12 t22 XOR t23 x15 t14 XOR y8 t21 t23 XOR t24 t9 t11 XOR y4 x4 t24 XOR t25 x6 t13 XOR y14 t10 t25 end SLP end circuit