Recent zbMATH articles in MSC 08Ahttps://zbmath.org/atom/cc/08A2024-02-28T19:32:02.718555ZWerkzeugOn the impossibility of key agreements from quantum random oracleshttps://zbmath.org/1527.810372024-02-28T19:32:02.718555Z"Austrin, Per"https://zbmath.org/authors/?q=ai:austrin.per"Chung, Hao"https://zbmath.org/authors/?q=ai:chung.hao"Chung, Kai-Min"https://zbmath.org/authors/?q=ai:chung.kai-min"Fu, Shiuan"https://zbmath.org/authors/?q=ai:fu.shiuan"Lin, Yao-Ting"https://zbmath.org/authors/?q=ai:lin.yaoting"Mahmoody, Mohammad"https://zbmath.org/authors/?q=ai:mahmoody.mohammadSummary: We study the following question, first publicly posed by \textit{A. Hosoyamada} and \textit{T. Yamakawa} in [Lect. Notes Comput. Sci. 12491, 3--32 (2020; Zbl 07666628)]. Can parties \textsf{A}, \textsf{B} with quantum computing power and classical communication rely only on a random oracle (that can be queried in quantum superposition) to agree on a key that is private from eavesdroppers?
We make the first progress on the question above and prove the following.
\begin{itemize}
\item When only one of the parties \textsf{A} is classical and the other party \textsf{B} is quantum powered, as long as they ask a total of \(d\) oracle queries and agree on a key with probability 1, then there is always a way to break the key agreement by asking \(O(d^2)\) number of classical oracle queries.
\item When both parties can make quantum queries to the random oracle, we introduce a natural conjecture, which if true would imply attacks with \({\operatorname{poly}}(d)\) classical queries to the random oracle. Our conjecture, roughly speaking, states that the multiplication of any two degree-\(d\) real-valued polynomials over the Boolean hypercube of influence at most \(\delta =1/{\operatorname{poly}}(d)\) is nonzero. We then prove our conjecture for exponentially small influences, which leads to an (unconditional) classical \(2^{O(md)} \)-query attack on any such key agreement protocol, where \(m\) is the oracle's output length.
\item Since our attacks are classical, we then ask whether it is always possible to find classical attacks on key agreements with imperfect completeness in the quantum random oracle model. We prove a barrier for this approach, by showing that if the folklore ``Simulation Conjecture'' (first formally stated by \textit{S. Aaronson} and \textit{A. Ambainis} in [``The need for structure in quantum speedups'', Preprint, \url{arXiv:0911.0996 }]) about the possibility of simulating efficient-query quantum algorithms using efficient-query classical algorithms is false, then there is in fact such a secure key agreement in the quantum random oracle model that cannot be broken classically.
\end{itemize}
For the entire collection see [Zbl 1514.94002].Hopf structure for the \(q\)-Lévy-Meixner oscillator algebrahttps://zbmath.org/1527.810832024-02-28T19:32:02.718555Z"Riahi, Anis"https://zbmath.org/authors/?q=ai:riahi.anis"Rebei, Habib"https://zbmath.org/authors/?q=ai:rebei.habib"Ettaieb, Amine"https://zbmath.org/authors/?q=ai:ettaieb.amine"Alhussain, Ziyad Ali"https://zbmath.org/authors/?q=ai:alhussain.ziyad-ali"Elmonser, Hedi Ben"https://zbmath.org/authors/?q=ai:elmonser.hedi-benSummary: The main purpose of this paper is to investigate a generalized oscillator algebra, naturally associated with the \(q\)-Lévy-Meixner polynomials. We solve the problem of the Hopf algebraic structure for the \(q\)-deformed Lévy-Meixner oscillator algebra based on the one-parameter deformation of canonical commutation relations.