Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Độ phức tạp nhân của các hàm Boolean 6 biến
Tóm tắt
Độ phức tạp nhân của một hàm Boolean là số lượng tối thiểu của các cổng AND hai đầu vào cần thiết và đủ để triển khai hàm này trên cơ sở (AND, XOR, NOT). Việc tìm độ phức tạp nhân của một hàm đã cho là rất khó khăn về mặt tính toán, ngay cả đối với các hàm có số đầu vào nhỏ. Turan và cộng sự [1] đã chỉ ra rằng các hàm Boolean có n biến có thể được triển khai với tối đa $n-1$ cổng AND cho $n\leq 5$. Một lập luận đếm có thể được sử dụng để cho thấy rằng, đối với n ≥ 7, tồn tại các hàm Boolean với n biến có độ phức tạp nhân ít nhất là n. Trong nghiên cứu này, chúng tôi đề xuất một phương pháp để tìm độ phức tạp nhân của các hàm Boolean bằng cách phân tích các mạch với số lượng cổng AND nhất định và sử dụng tính tương đương affine của các hàm. Chúng tôi sử dụng phương pháp này để nghiên cứu độ phức tạp nhân của các hàm Boolean 6 biến, và tính toán độ phức tạp nhân của tất cả 150.357 lớp tương đương affine. Chúng tôi chỉ ra rằng bất kỳ hàm Boolean 6 biến nào cũng có thể được triển khai bằng tối đa 6 cổng AND. Ngoài ra, chúng tôi trình bày các hàm Boolean 6 biến cụ thể có độ phức tạp nhân là 6.
Từ khóa
#độ phức tạp nhân #hàm Boolean #cổng AND #tính tương đương affineTài liệu tham khảo
Sönmez, M.T., Peralta, R.: The Multiplicative Complexity of Boolean Functions on Four and Five Variables, pp. 21–33. Springer International Publishing, Cham (2015)
Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewic, I. (eds.) Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, volume 5126 of Lecture Notes in Computer Science, pp 486–498. Springer (2008)
Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S (ed.) Innovations in Theoretical Computer Science 2012, January 8–10, 2012, pp. 309–325. ACM, Cambridge (2012)
Boyar, J., Damgård, I., Peralta, R.: Short non-interactive cryptographic proofs. J Cryptol 13(4), 449–472 (2000)
Carlet, C., Goubin, L., Prouff, E., Quisquater, M., Rivain, M.: Higher-order masking schemes for s-boxes. In: Canteaut, A. (ed.) Fast Software Encryption—19th International Workshop, FSE 2012, Washington, DC, USA, March 19–21, 2012. Revised Selected Papers, volume 7549 of Lecture Notes in Computer Science, pages 366–384. Springer (2012)
Gausdal Find, M.: On the complexity of computing two nonlinearity measures. In: Computer Science—Theory and Applications—9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7–11, 2014. Proceedings, pp. 167–175 (2014)
Codish, M., Cruz-Filipe, L., Frank, M., Schneider-Kamp, P.: When six gates are not enough. CoRR arXiv:1508.05737 (2015)
Boyar, J., Peralta, R.: Tight bounds for the multiplicative complexity of symmetric functions. Theor. Comput. Sci. 396(1–3), 223–246 (2008)
Boyar, J., Peralta, R., Pochuev, D.: On the multiplicative complexity of Boolean functions over the basis (∧, \(\oplus \), 1). Theor. Comput. Sci. 235(1), 43–57 (2000)
Fuller, J.E.: Analysis of affine equivalent boolean functions for cryptography. PhD thesis, Queensland University of Technology (2003)
Berlekamp, E.R., Welch, L.R.: Weight distributions of the cosets of the (32, 6) Reed-Muller code. IEEE Trans. Inf. Theory 18(1), 203–207 (1972)
Maiorana, J.A.: A classification of the cosets of the Reed-Muller code \(\mathcal {R}\)(1,6). Math. Comput. 57(195), 403–414 (1991)
Braeken, A., Borissov, Y., Nikova, S., Preneel, B.: Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties, pp. 324–334. Berlin, Heidelberg (2005)
Hou, X.-D.: AGL (m, 2) acting on R (r, m)/R (s, m). J. Algebra 171(3), 927–938 (1995)
Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science and Engineering, chapter 8. Cambridge University Press, Cambridge (2010)
Knuth, D.E.: Subspaces, subsets, and partitions. J. Comb. Theory, Ser. A 10(2), 178–180 (1971)
Goldman, J., Rota, G.-C.: On the foundations of combinatorial theory iv finite vector spaces and eulerian generating functions. Stud. Appl. Math. 49(3), 239–258 (1970)
NIST Computer Security Division. SLP’s for 6-variable predicates, https://github.com/usnistgov/Circuits/tree/master/slp