Nonlinear functions, codes and quantum computation

本研究共分为三个部分。 在第一部分中，我将研究几类密码函数，它们是分组密码和流密码的重要组成部分。这些密码保护互联网、无线网络、移动的电话和其他网络上的通信的隐私和安全。它们还保护以数字方式存储的数据。因此，这些密码每天都被现代社会的大多数公民使用。我的预期成果是通过找到这些函数的公式，或者通过开发有效测试任何给定函数是否具有所需属性的计算方法，来构造新的最佳密码函数。 在第二部分中，我将研究线性码。错误控制码检测并纠正当信号通过噪声信道传输时，或当数据存储在计算机存储器或磁盘中或从计算机存储器或磁盘中检索时，由于噪声而发生的错误。噪音的来源是例如与其他设备的干扰、大气电力或硬件的制造缺陷及其折旧。差错控制码对于互联网、无线网络、移动的电话和计算机的正常运行至关重要。我的研究的预期成果是精确确定任何给定代码的错误检测和纠正能力的算法;我的算法将比迄今为止已知的算法快得多。我的算法将是重要的，不仅为实际建设的错误控制码，而且在其他领域的研究人员，因为许多理论问题可以减少到存在一定的线性码。我还将检查我的算法是否可能与攻击McEliece密码系统有关。 我研究的第三部分涉及量子计算。预计量子物理学的某些独特功能将使量子计算机的速度大大超过经典计算机。一个这样的功能是上下文，它是由Kochen-Specker集证明。我将通过寻找它们的公式或设计找到它们的算法来构造新的Kochen-Specker集族。我的算法还将证明在某些情况下这些集合不存在。可扩展量子计算机的实际工程存在重大挑战;预计量子纠错码在这一过程中将是重要的。我将构造出比目前已知的密码更好的量子密码。

The proposed research is divided into three parts. In the first part I will study several families of cryptographic functions, which are important components of block ciphers and stream ciphers. These ciphers protect privacy and security of communications on Internet, wireless networks, mobile telephony, and other networks. They also protect data that is stored digitally. Hence, these ciphers are used every day by most citizens of a modern society. My anticipated outcome is the construction of new optimal cryptographic functions, by finding formulas for these functions, or by developing computational methods that efficiently test whether any given function has the desired properties. In the second part I will study linear codes. Error control codes detect and correct errors that occur due to noise when a signal is transmitted over a noisy channel, or when data is stored in, and retrieved from, computer memory or disks. Sources of noise are for example interference with other devices, atmospheric electricity or manufacturing imperfections in hardware compounded with its depreciation. Error control codes are critical for the proper function of Internet, wireless networks, mobile telephony and computers. The anticipated outcome of my research are algorithms that exactly determine the error detection and correction capacity of any given code; my algorithms will be significantly faster than hitherto known algorithms. My algorithms will be important not only for practical construction of error control codes but also to researchers in other areas, since many theoretical problems can be reduced to the existence of a certain linear code. I will also examine whether my algorithms may be relevant to attacking McEliece cryptosystem. The third part of my research deals with quantum computing. It is anticipated that certain unique features of quantum physics will enable a dramatic speed-up of quantum computers over classical computers. One such feature is contextuality, and it is demonstrated by Kochen-Specker sets. I will construct new families of Kochen-Specker sets by finding formulas for them or designing algorithms that find them. My algorithms will also prove non-existence of these sets in certain cases. Significant challenges exist with practical engineering of scalable quantum computers; it is anticipated that quantum error-correcting codes will be important in this process. I will construct quantum codes that are better than hitherto known codes.