On Relaxation of Simon's Algorithm

ارائه مقاله آقای علی خسروی با عنوان "On Relaxation of Simon's Algorithm" در هجدمین کنفرانس بین المللی انجمن رمز ایران، اصفهان، دانشگاه اصفهان، شهریور 1400 Simon's algorithm is one of the most widely used quantum algorithms in cryptanalysis of symmetric ciphers, which has a significant advantage over its classical counterparts. However, if the number of unwanted collisions of the target function is large or if the number of adversary's quantum superposition queries is limited, the Simon's algorithm is not able to unambiguously compute the actual period. This problem can lead to the failure of period-finding-based quantum attacks. In this paper we first show that using Simon's algorithm, one can find proper partial periods of Boolean vector functions, such that the corresponding probabilities, independent of the target function, are directly related to the number of quantum queries. Next, we examine how to use the partial period instead of actual one in quantum period-finding-based attacks. As a result, the advantage of our proposed relaxing method is twofold: It improves success probabilities of quantum period-finding-based distinguishers, provided that the adversary is limited to a specified small number of queries, in contrast to the previous ones. On the other hand, our proposed method generalizes the previous forgery attacks on modes of operation for message authentication codes.

• #فناوری_و_رایانه
• #کنفرانس_رمز_1400
• #کنفرانس_رمز
• #دانشگاها_اصفهان
• #رمزنگاری_کوانتومی
• #رمز_متقارن