26838 research outputs found
Sort by
Breaking XOR arbiter PUFs with chosen challenge attack
Get PDFThe XOR Arbiter PUF was introduced as a strong PUF in 2007 and was broken in 2015 by a Machine Learning (ML) attack, which allows the underlying Arbiter PUFs to be modeled individually by exploiting reliability information of the measured responses. To mitigate the reliability-based attacks, state-of-the-art understanding shows that the reliability of individual Arbiter PUFs and the overall XOR Arbiter PUF can be boosted to an arbitrarily high level, thus rendering all known reliability-based ML attacks infeasible; alternatively, an access control interface around the XOR Arbiter PUF can prevent the same challenge-response pairs from being accessed repeatedly, thus eliminating the leakage of reliability information. We show that, for the first time, a perfectly reliable XOR Arbiter PUF can be successfully attacked in a divide-and-conquer manner, meaning each underlying Arbiter PUF in an XOR Arbiter PUF can be attacked individually. This allows us to attack large XOR Arbiter PUFs efficiently, even without reliability information or any side-channel information. Our key insight is that, instead of reliability information, the responses of highly correlated challenges also reveal how close the responses are to the response decision boundary. This leads to a chosen challenge attack on XOR Arbiter PUFs by carefully choosing correlated challenges to measure and aggregate the collected information. We validate our attack by using PUF simulation, as well as an XOR Arbiter PUF implemented on FPGA. We also demonstrate that our chosen challenge methodology is compatible with the state-of-the-art combined gradient-based multi-objective optimization attack. Finally, we discuss an effective countermeasure that can prevent our attack but with a relatively large area overhead compared to the PUF itself
Multidimensional quantum walks and the multiplicative ladder adversary
Get PDFQuantum computing offers the potential to solve problems more efficiently than classical methods, yet understanding its capabilities requires new conceptual frameworks. This dissertation explores quantum algorithms with a focus on maintaining connections to classical intuition, clarifying both their strengths and limitations.
In Part I, we explore the capabilities of a class of quantum algorithms known as quantum walks. These quantum walks, the quantum analogs of classical random walks, serve as powerful yet accessible tools for solving a variety of computational problems. Our key contribution is the development of a novel way to construct quantum walks, resulting in multidimensional quantum walks. By applying these walks to the -distinctness problem, we achieve a time-efficient algorithm matching the best-known query upper bound up to polylogarithmic factors. Additionally, applying them to the welded tree problem results in exponential speedups, marking the first instance of a discrete quantum walk to do so. Furthermore, we extend the well-known link between quantum walks and electrical networks to the multidimensional quantum walks.
In Part II, we turn to the limitations of quantum algorithms by examining techniques for establishing quantum query lower bounds, representing the minimum computational cost required for any quantum algorithm to solve a given computational problem, regardless of the quantum algorithm used. To this goal, we introduce the multiplicative ladder adversary method, a simplified version of the multiplicative adversary method which unifies the compressed oracle technique within the broader adversary framework while extending its applicability, offering a more intuitive approach to establishing quantum lower bounds
Positive streamer discharge simulations in humid air: uncertainty in input data and sensitivity analysis
No full textWe study how the choice of input data affects simulations of positive streamers in humid air, focusing on H2O cross sections, photoionization models, and chemistry sets. Simulations are performed in air with a mole fraction of 0%, 3% or 10% H2O using an axisymmetric fluid model. Five H2O cross section sets are considered, which lead to significant differences in the resulting electron attachment coefficient. As a result, the streamer velocity can vary by up to about 50% with 10% H2O. We compare results with three photoionization models: the Naidis model for humid air, the Aints model for humid air, and the standard Zheleznyak model for dry air. With the Naidis and in particular the Aints model, there is a significant reduction in photoionization with higher humidities. This results in higher streamer velocities and maximal electric fields, and it can also cause streamer branching in our axisymmetric simulations. Three humid air chemistry sets are considered. Differences between these sets, particularly in the formation of water clusters around positive ions, cause the streamer velocity to vary by up to about 50% with 10% H2O. A sensitivity analysis is performed to identify the most important chemical reactions in these chemistries
Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding
Get PDFThe most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results: (1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 ≤ q ≤ √n, our algorithm takes q13n+o(n) time and requires poly(n) ̇ q16n/q2 memory. This tradeoff, which ranges from enumeration (q = √n) to sieving (q constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for SVP that runs in time 20.950n+o(n) and requires 20.5n+o(n) classical memory and poly(n) qubits. In a quantum random access memory (QRAM) model, this algorithm takes only 20.835n+o(n) time and requires a QRAM of size 20.293n+o(n), poly(n) qubits and 20.5n classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015, pp. 733-742] that has a time and space complexity 2n+o(n). (3) A classical algorithm for SVP that runs in time 21.669n+o(n) time and 20.5n+o(n) space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285-306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is 20.402n. We conjecture that for most lattices this quantity is a 2o(n). Assuming that this is the case, our classical algorithm runs in time 21.292n+o(n), our quantum algorithm runs in time 20.750n+o(n), and our quantum algorithm in a QRAM model runs in time 20.667n+o(n). As a direct application of our result, using the reduction in [L. Ducas, Des. Codes. Cryptogr., 92 (2024), pp. 909-916], we obtain a provable quantum algorithm for the lattice isomorphism problem in the case of the trivial lattice \BbbZn (\BbbZLIP) that runs in time 20.417n+o(n). Our algorithm requires a QRAM of size 20.147n+o(n), poly(n) qubits and 20.25n classical space
Wagner’s algorithm provably runs in subexponential time for SIS∞
Get PDFAt CRYPTO 2015, Kirchner and Fouque claimed that a
carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm
(JACM 2003) should solve the Learning with Errors problem (LWE) in
slightly subexponential time for modulus q = poly(n) and narrow er-
ror distribution, when given enough LWE samples. Taking a modular
view, one may regard BKW as a combination of Wagner’s algorithm
(CRYPTO 2002), run over the corresponding dual problem, and the
Aharonov-Regev distinguisher (JACM 2005). Hence the subexponential
Wagner step alone should be of interest for solving this dual problem –
namely, the Short Integer Solution problem (SIS) – but this appears to
be undocumented so far.
We re-interpret this Wagner step as walking backward through a chain of
projected lattices, zigzagging through some auxiliary superlattices. We
further randomize the bucketing step using Gaussian randomized round-
ing to exploit the powerful discrete Gaussian machinery. This approach
avoids sample amplification and turns Wagner’s algorithm into an ap-
proximate discrete Gaussian sampler for q-ary lattices.
For an SIS lattice with n equations modulo q, this algorithm runs in
subexponential time exp(O(n/ log log n)) to reach a Gaussian width pa-
rameter s = q/polylog(n) only requiring m = n + ω(n/ log log n) many
SIS variables. This directly provides a provable algorithm for solving the
Short Integer Solution problem in the infinity norm (SIS∞) for norm
bounds β = q/polylog(n). This variant of SIS underlies the security
of the NIST post-quantum cryptography standard Dilithium. Despite
its subexponential complexity, Wagner’s algorithm does not appear to
threaten Dilithium’s concrete security
Orthogonality broadcasting and quantum position verification
Get PDFThe no-cloning theorem leads to information-theoretic security in various quantum cryptographic protocols. However, this security typically derives from a possibly weaker property that classical information encoded in certain quantum states cannot be broadcast. To formally capture this property, we introduce the study of ‘orthogonality broadcasting.’ When attempting to broadcast the orthogonality of two different qubit bases, we establish that the power of classical and quantum communication is equivalent. However, quantum communication is shown to be strictly more powerful for broadcasting orthogonality in higher dimensions. We then relate orthogonality broadcasting to quantum position verification and provide a new method for establishing error bounds in the no pre-shared entanglement model that can address protocols previous methods could not. Our key technical contribution is an uncertainty relation that uses the geometric relation of the states that undergo broadcasting rather than the non-commutative aspect of the final measurements
Model-averaged Bayesian t tests
Get PDFOne of the most common statistical analyses in experimental psychology concerns the comparison of two means using the frequentist t test. However, frequentist t tests do not quantify evidence and require various assumption tests. Recently, popularized Bayesian t tests do quantify evidence, but these were developed for scenarios where the two populations are assumed to have the same variance. As an alternative to both methods, we outline a comprehensive t test framework based on Bayesian model averaging. This new t test framework simultaneously takes into account models that assume equal and unequal variances, and models that use t-likelihoods to improve robustness to outliers. The resulting inference is based on a weighted average across the entire model ensemble, with higher weights assigned to models that predicted the observed data well. This new t test framework provides an integrated approach to assumption checks and inference by applying a series of pertinent models to the data simultaneously rather than sequentially. The integrated Bayesian model-averaged t tests achieve robustness without having to commit to a single model following a series of assumption checks. To facilitate practical applications, we provide user-friendly implementations in JASP and via the RoBTT package in R. A tutorial video is available at https://www.youtube.com/watch?v=EcuzGTIcor
Assessing the development of internal disorders in pome fruit with X-ray CT before, during and after controlled atmosphere storage and shelf life
Get PDFThis study examined the use of X-ray computed tomography (CT) for the early detection of physiological disorders in pome fruit during controlled atmosphere (CA) storage and shelf life. The CT images of healthy and disordered ‘Braeburn’ apples, ‘Golden Delicious’ apples and ‘Conference’ pears were evaluated. ‘Braeburn’ apple (n = 80) were scanned with CT before and during browning-inducing CA conditions (0.5 °C, 1.5 kPa O2, 5 kPa CO2) and subsequent shelf life. ‘Conference’ pears (n = 70) were scanned following regular air storage that induced freezing injury (−2 °C) and additional CA storage (−0.6 °C, 3 kPa O2, <0.7 kPa CO2) and subsequent shelf life. ‘Golden Delicious’ apples (n = 60) were scanned after CA storage (1 °C, 1 kPa O2, 3 kPa CO2) and after 35 days of shelf life. The causes of postharvest losses after CA storage and shelf life were core browning, flesh browning and bitter pit for ‘Braeburn’, ‘Conference’ and ‘Golden Delicious’, respectively. After CA storage, the mean greyscale value (MGV) of CT images was higher in healthy ‘Braeburn’ and ‘Golden Delicious’ apples compared to those that appeared externally healthy but later developed a disorder during shelf life. The MGV decreased during storage and shelf life in affected ‘Braeburn’ and ‘Golden Delicious’ apples, whereas no change occurred during shelf life for healthy ‘Golden Delicious’ apples, and ‘Braeburn’ apples stored for 17 weeks. No difference in the MGV was found between healthy and disordered ‘Conference’ pears. For ‘Braeburn’, voids associated with core browning did not develop until fruit were removed from CA storage and subsequently kept in shelf life for at least seven days. Results of this study indicate that the MGV of CT images can be used to indicate ‘Braeburn’ and ‘Golden Delicious’ apple fruit marketability after CA storage before shelf life
Extreme values for the waiting time in large fork-join queues
Get PDFWe prove that the scaled maximum steady-state waiting time and the scaled maximum steady-state queue length among N GI/GI/1-queues in the N-server fork-join queue converge to a normally distributed random variable as N→∞. The maximum steady-state waiting time in this queueing system scales around 1γlogN, where γ is determined by the cumulant generating function Λ of the service times distribution and solves the Cramér–Lundberg equation with stochastic service times and deterministic interarrival times. This value 1γlogN is reached at a certain hitting time. The number of arrivals until that hitting time satisfies the central limit theorem, with standard deviation σAΛ′(γ)γ. By using the distributional form of Little’s law, we can extend this result to the maximum queue length. Finally, we extend these results to a fork-join queue with different classes of servers
