# File timestamp (UTC): 2021-02-25T00:07:28.441 # NIST Circuit Complexity Project # https://csrc.nist.gov/projects/circuit-complexity begin circuit M-4x4-GF16--rs=1 # Boolean Circuit for a linear system y = A.x defined by a 16x16 bit-matrix A # Matrix A weights (W): totalW=108, adjW=92, minWInRow=4, maxWInRow=8, minWInCol=4, maxWICol=8 # Matrix represented as 16 rows: vecRows=UInt16[0x5368, 0x37c4, 0x4812, 0xe531, 0x3586, 0x734c, 0x8421, 0x5e13, 0x6853, 0xc437, 0x1248, 0x31e5, 0x8635, 0x4c73, 0x2184, 0x135e] # Matrix represented as 16 columns: vecCols=UInt16[0x3bc8, 0xa394, 0xda32, 0x8421, 0xb38c, 0x3a49, 0xad23, 0x4812, 0xc83b, 0x94a3, 0x32da, 0x2184, 0x8cb3, 0x493a, 0x23ad, 0x1248] # 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, 36 gates (36 XOR) # Depth: 8 Inputs: x1:x16 Outputs: y1:y16 Internal: t1:t20 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 x10 x13 XOR t2 x8 x14 XOR t3 x2 x5 XOR t4 x6 x16 XOR t5 x12 t3 XOR y8 x15 t5 XOR t6 x1 t4 XOR y4 x11 t6 XOR t7 x4 t1 XOR y16 x7 t7 XOR t8 x9 t2 XOR y12 x3 t8 XOR t9 x8 y4 XOR y13 t5 t9 XOR t10 x16 y12 XOR y5 t7 t10 XOR t11 x12 y16 XOR y1 t8 t11 XOR t12 x4 y8 XOR y9 t6 t12 XOR t13 x9 t5 XOR y11 y1 t13 XOR t14 t4 t7 XOR y3 t12 t14 XOR t15 x9 t12 XOR y14 x6 t15 XOR t16 x14 t11 XOR y6 x1 t16 XOR t17 x5 y13 XOR y7 t8 t17 XOR t18 x5 x10 XOR y2 t10 t18 XOR t19 x13 t17 XOR y10 x12 t19 XOR t20 x13 y5 XOR y15 t6 t20 end SLP end circuit