Alexander May

Leon O. H. Kroczek, Alexander May, Selina Hettenkofer et al.

Large Language Models (LLMs) have demonstrated remarkable capabilities in conversational tasks. Embodying an LLM as a virtual human allows users to engage in face-to-face social interactions in Virtual Reality. However, the influence of person- and task-related factors in social interactions with LLM-controlled agents remains unclear. In this study, forty-six participants interacted with a virtual agent whose persona was manipulated as extravert or introvert in three different conversational tasks (small talk, knowledge test, convincing). Social-evaluation, emotional experience, and realism were assessed using ratings. Interactive engagement was measured by quantifying participants' words and conversational turns. Finally, we measured participants' willingness to ask the agent for help during the knowledge test. Our findings show that the extraverted agent was more positively evaluated, elicited a more pleasant experience and greater engagement, and was assessed as more realistic compared to the introverted agent. Whereas persona did not affect the tendency to ask for help, participants were generally more confident in the answer when they had help of the LLM. Variation of personality traits of LLM-controlled embodied virtual agents, therefore, affects social-emotional processing and behavior in virtual interactions. Embodied virtual agents allow the presentation of naturalistic social encounters in a virtual environment.

Julian Speith, Florian Schweins, Maik Ender et al.

Modern hardware systems are composed of a variety of third-party Intellectual Property (IP) cores to implement their overall functionality. Since hardware design is a globalized process involving various (untrusted) stakeholders, a secure management of the valuable IP between authors and users is inevitable to protect them from unauthorized access and modification. To this end, the widely adopted IEEE standard 1735-2014 was created to ensure confidentiality and integrity. In this paper, we outline structural weaknesses in IEEE 1735 that cannot be fixed with cryptographic solutions (given the contemporary hardware design process) and thus render the standard inherently insecure. We practically demonstrate the weaknesses by recovering the private keys of IEEE 1735 implementations from major Electronic Design Automation (EDA) tool vendors, namely Intel, Xilinx, Cadence, Siemens, Microsemi, and Lattice, while results on a seventh case study are withheld. As a consequence, we can decrypt, modify, and re-encrypt all allegedly protected IP cores designed for the respective tools, thus leading to an industry-wide break. As part of this analysis, we are the first to publicly disclose three RSA-based white-box schemes that are used in real-world products and present cryptanalytical attacks for all of them, finally resulting in key recovery.

Alexander May, Lars Schlieper, Jonathan Schwinger

Let $f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ be a Boolean function with period $\vec s$. It is well-known that Simon's algorithm finds $\vec s$ in time polynomial in $n$ on quantum devices that are capable of performing error-correction. However, today's quantum devices are inherently noisy, too limited for error correction, and Simon's algorithm is not error-tolerant. We show that even noisy quantum period finding computations may lead to speedups in comparison to purely classical computations. To this end, we implemented Simon's quantum period finding circuit on the $15$-qubit quantum device IBM Q 16 Melbourne. Our experiments show that with a certain probability $τ(n)$ we measure erroneous vectors that are not orthogonal to $\vec s$. We propose new, simple, but very effective smoothing techniques to classically mitigate physical noise effects such as e.g. IBM Q's bias towards the $0$-qubit. After smoothing, our noisy quantum device provides us a statistical distribution that we can easily transform into an LPN instance with parameters $n$ and $τ(n)$. Hence, in the noisy case we may not hope to find periods in time polynomial in $n$. However, we may still obtain a quantum advantage if the error $τ(n)$ does not grow too large. This demonstrates that quantum devices may be useful for period finding, even before achieving the level of full error correction capability.

Andre Esser, Alexander May

We propose a new heuristic algorithm for solving random subset sum instances $a_1, \ldots, a_n, t \in \mathbb{Z}_{2^n}$, which play a crucial role in cryptographic constructions. Our algorithm is search tree-based and solves the instances in a divide-and-conquer method using the representation method. From a high level perspective, our algorithm is similar to the algorithm of Howgrave-Graham-Joux (HGJ) and Becker-Coron-Joux (BCJ), but instead of enumerating the initial lists we sample candidate solutions. So whereas HGJ and BCJ are based on combinatorics, our analysis is stochastic. Our sampling technique introduces variance that increases the amount of representations and gives our algorithm more optimization flexibility. This results in the remarkable and natural property that we improve with increasing search tree depth. Whereas BCJ achieves the currently best known (heuristic) run time $2^{0.291n}$ for random subset sum, we improve (heuristically) down to $2^{0.255n}$ using a search tree of depth at least $13$. We also apply our subset algorithm to the decoding of random binary linear codes, where we improve the best known run time of the Becker-Joux-May-Meurer algorithm from $2^{0.048n}$ in the half distance decoding setting down to $2^{0.042n}$.

Alexander May, Lars Schlieper

We study quantum period finding algorithms such as Simon and Shor (and its variants Ekerå-Håstad and Mosca-Ekert). For a periodic function $f$ these algorithms produce -- via some quantum embedding of $f$ -- a quantum superposition $\sum_x |x\rangle|f(x)\rangle$, which requires a certain amount of output qubits that represent $|f(x)\rangle$. We show that one can lower this amount to a single output qubit by hashing $f$ down to a single bit in an oracle setting. Namely, we replace the embedding of $f$ in quantum period finding circuits by oracle access to several embeddings of hashed versions of $f$. We show that on expectation this modification only doubles the required amount of quantum measurements, while significantly reducing the total number of qubits. For example, for Simon's algorithm that finds periods in $f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ our hashing technique reduces the required output qubits from $n$ down to $1$, and therefore the total amount of qubits from $2n$ to $n+1$. We also show that Simon's algorithm admits real world applications with only $n+1$ qubits by giving a concrete realization of a hashed version of the cryptographic Even-Mansour construction. Moreover, for a variant of Simon's algorithm on Even-Mansour that requires only classical queries to Even-Mansour we save a factor of (roughly) $4$ in the qubits. Our oracle-based hashed version of the Ekerå-Håstad algorithm for factoring $n$-bit RSA reduces the required qubits from $(\frac 3 2 + o(1))n$ down to $(\frac 1 2 + o(1))n$. We also show a real-world (non-oracle) application in the discrete logarithm setting by giving a concrete realization of a hashed version of Mosca-Ekert for the Decisional Diffie Hellman problem in $\mathbb{F}_{p^m}$, thereby reducing the number of qubits by even a linear factor from $m \log p$ downto $\log p$.