International Association
for Cryptologic Research

At FSE'15, Mennink introduced two tweakable block ciphers, $\widetilde{F}[1]$ and $\widetilde{F}[2]$, both utilizing an $n$-bit tweak. It was demonstrated that $\widetilde{F}[1]$ is secure for up to $2^{2n/3}$ queries, while $\widetilde{F}[2]$ is secure for up to $2^n$ queries, assuming the underlying block cipher is an ideal cipher with $n$-bit key and $n$-bit data. Later, at ASIACRYPT'16, Wang et al. showed a birthday bound attack on Mennink's design (which was later corrected in the eprint version {\textbf eprint 2015/363}) and proposed 32 new candidates for tweakable block ciphers that are derived from $n$-bit ideal block ciphers. It was shown that all the $32$ constructions are provably secure up to $2^n$ queries. All the proposed designs by both Mennink and Wang et al. admit only $n$-bit tweaks. In FSE'23, Shen and Standaert proposed a tweakable block cipher, $\widetilde{G2}$, which uses $2n$-bit tweaks and is constructed from three $n$-bit block cipher calls, proving its security up to $n$ bits, assuming that the underlying block cipher is an ideal cipher. They have also shown that it is impossible to design a tweakable block cipher with $2n$-bit tweaks using only two $n$-bit block cipher calls while achieving security beyond the birthday bound. In this paper, we advance this research further. We show that any tweakable block cipher design with $3n$-bit tweaks based on only three block cipher calls, where at least one key is tweak-independent, is vulnerable to a birthday bound distinguishing attack. We then propose a tweakable block cipher, $\widetilde{\textsf{G}_3}^*$ that uses three block cipher calls and admits $3n$-bit tweaks, achieves security up to $O(2^{2n/3})$ queries when all three block cipher keys are tweak-dependent. Furthermore, we prove that using four ideal block cipher calls, with at least one key being tweak-dependent, is necessary and sufficient to achieve $n$-bit security for a tweakable block cipher that admits $3n$-bit tweaks. Finally, we propose a tweakable block cipher, $\widetilde{\textsf{G}_r}$, which uses $(r+1)$ block cipher calls and processes $rn$-bit tweaks, achieving security up to $O(2^n)$ queries when at least one block cipher key is tweak-dependent.

Garbled Circuits are essential building blocks in cryptography, and extensive research has explored their construction from both applied and theoretical perspectives. However, a challenge persists: While theoretically designed garbled circuits offer optimal succinctness--remaining constant in size regardless of the underlying circuit’s complexit--and are reusable for multiple evaluations, their concrete computational costs are prohibitively high. On the other hand, practically efficient garbled circuits, inspired by Yao’s garbled circuits, encounter limitations due to substantial communication bottlenecks and a lack of reusability.

To strike a balance, we propose a novel concept: online-offline garbling. This approach leverages instance-independent and (partially) reusable preprocessing during an offline phase, to enable the creation of constant-size garbled circuits in an online phase, while maintaining practical efficiency. Specifically, during the offline stage, the garbler generates and transmits a reference string, independent of the computation to be performed later. Subsequently, in the online stage, the garbler efficiently transforms a circuit into a constant-size garbled circuit. The evaluation process relies on both the reference string and the garbled circuit.

We demonstrate that by leveraging existing tools such as those introduced by Applebaum et al. (Crypto’13) and Chongwon et al. (Crypto’17), online-offline garbling can be achieved under a variety of assumptions, including the hardness of Learning With Errors (LWE), Computational Diffie-Hellman (CDH), and factoring. In contrast, without the help of an offline phase, constant-size garbling is only feasible under the LWE and circular security assumptions, or the existence of indistinguishability obfuscation. However, these schemes are still very inefficient, several orders of magnitude more costly than Yao-style garbled circuits.

To address this, we propose a new online-offline garbling scheme based on Ring LWE. Our scheme offers both asymptotic and concrete efficiency. It serves as a practical alternative to Yao-style garbled circuits, especially in scenarios where online communication is constrained. Furthermore, we estimate the concrete latency using our approach in realistic settings and demonstrate that it is 2-20X faster than using Yao-style garbled circuits. This improvement is estimated without taking into account parallelization of computation, which can lead to further performance improvement using our scheme.

The SPDM (Security Protocol and Data Model) protocol is a standard under development by the DMTF consortium, and supported by major industry players including Broadcom, Cisco, Dell, Google, HP, IBM, Intel, and NVIDIA. SPDM 1.2 is a complex protocol that aims to provide platform security, for example for communicating hardware components or cloud computing scenarios. In this work, we provide the first holistic, formal analysis of SPDM 1.2: we model the full protocol flow of SPDM considering all of its modes – especially the complex interaction between its different key-exchange modes – in the framework of the Tamarin prover, making our resulting model one of the most complex Tamarin models to date. To our surprise, Tamarin finds a cross-protocol attack that allows a network attacker to completely break authentication of the pre-shared key mode. We implemented our attack on the SPDM reference implementation, and reported the issue to the SPDM developers. DMTF registered our attack as a CVE with CVSS rating 9 (critical). We propose a fix and develop the first formal symbolic proof using the Tamarin prover for the fixed SPDM 1.2 protocol as a whole. The resulting model of the main modes and their interactions is highly complex, and we develop supporting lemmas to enable proving properties in the Tamarin prover, including the absence of all cross-protocol attacks. Our fix has been incorporated into both the reference implementation and the newest version of the standard. Our results highlight the need for a holistic analysis of other internet standards and the importance of providing generalized security guarantees across entire protocols.

The CRYSTALS-Dilithium digital signature scheme, selected by NIST as a post-quantum cryptography (PQC) standard under the name ML-DSA, employs a public key compression technique intended for performance optimization. Specifically, the module learning with error instance $({\bf A}, {\bf t})$ is compressed by omitting the low-order bits ${\bf t_0}$ of the vector ${\bf t}$. It was recently shown that knowledge of ${\bf t_0}$ enables more effective side-channel attacks on Dilithium implementations. Another recent work demonstrated a method for reconstructing ${\bf t_0}$ from multiple signatures. In this paper, we build on this method by applying profiled deep learning-assisted side-channel analysis to partially recover the least significant bit of ${\bf t_0}$ from power traces. As a result, the number of signatures required for the reconstruction of ${\bf t_0}$ can be reduced by roughly half. We demonstrate how the new ${\bf t_0}$ reconstruction method enhances the efficiency of recovering the secret key component ${\bf s}_1$, and thus facilitates digital signature forgery, on an ARM Cortex-M4 implementation of Dilithium.

We present the first public and in-depth cryptanalysis of TEA-3, a stream cipher used in TETRA radio networks that was kept secret until recently. While the same also holds for the six other TETRA encryption algorithms, we pick TEA-3 to start with as (i) it is not obviously weakened as TEA-{1,4,7} but (ii) in contrast to TEA-2 it is approved only for extra-European emergency service, and (iii) as already noted by [MBW23] the TEA-3 design surprisingly contains a non-bijective S-box. Most importantly, we show that the 80-bit non-linear feedback shift register operating on the key decomposes into a cascade of two 40-bit registers. Although this hints at an intentional weakness at first glance, we are not able to lift our results to a practical attack. Other than that, we show how the balanced non-linear feedback functions used in the state register of TEA-3 can be constructed.

Local Differential Privacy (LDP) mechanisms consist of (locally) adding controlled noise to data in order to protect the privacy of their owner. In this paper, we introduce a new cryptographic primitive called LDP commitment. Usually, a commitment ensures that the committed value cannot be modified before it is revealed. In the case of an LDP commitment, however, the value is revealed after being perturbed by an LDP mechanism. Opening an LDP commitment therefore requires a proof that the mechanism has been correctly applied to the value, to ensure that the value is still usable for statistical purposes. We also present a security model for this primitive, in which we define the hiding and binding properties. Finally, we present a concrete scheme for an LDP staircase mechanism (generalizing the randomized response technique), based on classical cryptographic tools and standard assumptions. We provide an implementation in Rust that demonstrates its practical efficiency (the generation of a commitment requires just a few milliseconds). On the application side, we show how our primitive can be used to ensure simultaneously privacy, usability and traceability of medical data when it is used for statistical studies in an open science context. We consider a scenario where a hospital provides sensitive patients data signed by doctors to a research center after it has been anonymized, so that the research center can verify both the provenance of the data (i.e. verify the doctors’ signatures even though the data has been noised) and that the data has been correctly anonymized (i.e. is usable even though it has been anonymized).

TU Wien is Austria's largest institution of research and higher education in the fields of technology and natural sciences. The Research Unit of Privacy Enhancing Technologies at TU Wien is offering a position as university assistant post-doc (all genders) limited to expected 6 years for 40 hours/week. Expected start: January 2025 but negotiable.

Topics of interest include (but are not limited to):
-Privacy preserving cryptocurrencies
-Efficient proof systems such as (non-interactive) zero-knowledge, SNARKs, etc.
-Cryptographic protocols
-Functional encryption
-Fully homomorphic encryption
-Information-theoretic approaches such as differential privacy

Your profile:
-Completion of an excellent doctorate in Computer Science or a closely related field
-Strong background in cryptography, privacy-preserving mechanisms, or data security
-In-depth knowledge and experience in at least one subject area: secure computation, differential privacy, anonymous communication systems, privacy-preserving machine learning, cryptocurrencies, cryptographic protocols, identity management, homomorphic encryption, or zero-knowledge proofs
- An outstanding publication record in top conferences, e.g., CCS, Crypto, Eurocrypt, Usenix Security, NDSS, EEE S&P,...

Salary: Entry level salary is determined by the pay grade B1 of the Austrian collective agreement for university staff. This is a minimum of currently EUR 4,932.90/month gross, 14 times/year for 40 hours/week.

Deadline: January 9th, 2025.

Application only via: https://jobs.tuwien.ac.at/Job/245103

Closing date for applications:

Contact: Univ. Prof. Dr. Dominique Schröder

More information: https://jobs.tuwien.ac.at/Job/245103

The University of Klagenfurt is pleased to announce the following open position at the Department of Artificial Intelligence and Cybersecurity, at the Faculty of Technical Sciences.

Assistant Professor (postdoc), non-tenure track (limited to 6 years)

Responsibilities:

• Independent research with the aim of habilitation, with a specific emphasis on research in cybersecurity such as cryptography, side-channel analysis, efficient implementation, high-assurance software
• Independent delivery of courses using established and innovative methods (e.g. digital teaching)
• Participation in the research and teaching projects run by the organisational unit
• Supervision of students
• Participation in organisational and administrative tasks and in quality assurance measures
• Contribution to expanding the international scientific and cultural contacts of the organisational unit
• Participation in public relations activities

Requirements:

• Doctoral degree in computer science or a related field, completed at a domestic or foreign higher education institution.
• Strong background and practical experience in one or more of the following fields: cryptography, side-channel analysis, efficient implementation, high-assurance software
• Proven academic track record via accepted papers in a reputable cybersecurity venue or in venues (journals) of a comparable standing in the areas of cybersecurity
• Solid communication and dissemination skills
• Fluency in English (both written and spoken)

Application deadline: 22nd January 2025

For more information and how to apply, please visit: https://jobs.aau.at/en/job/12-2/

Closing date for applications:

Contact: Chitchanok Chuengsatiansup (chitchanok.chuengsatiansup@aau.at)

More information: https://jobs.aau.at/en/job/12-2/

The University of Klagenfurt invites applications for PhD positions at the Digital Age Research Center and at the Department of Artificial Intelligence and Cybersecurity (Faculty of Technical Sciences).

Responsibilities:

• Autonomous scientific work including the publication of research articles in the field of cybersecurity, with a specific emphasis on cryptography, side-channel analysis, efficient implementation, high-assurance software and related areas
• Independent teaching and assessment
• Contribution to organisational and administrative tasks
• Participation in public relations activities

Requirements:

• Master’s degree at a domestic or foreign higher education institution in computer science or a related field
• Strong background and practical experience in one or more of the following fields: cryptography, side-channel analysis, efficient implementation, high-assurance software
• Solid communication and dissemination skills
• Fluency in English (both written and spoken)

Application deadline: 29th January 2025

For more information and how to apply, please visit: https://jobs.aau.at/job/university-assistant-predoctoral-all-genders-welcome-13/

Closing date for applications:

Contact: Chitchanok Chuengsatiansup (chitchanok.chuengsatiansup@aau.at)

More information: https://jobs.aau.at/job/university-assistant-predoctoral-all-genders-welcome-13/

The Institute of Cybersecurity and Cryptology at the University of Wollongong (Australia) is recruiting two PhD students to carry out cutting-edge research in privacy-preserving post-quantum cryptography. The positions are fully funded for up to 4 years. Applicants are expected to have a strong background in computer science, cryptography and mathematics, as well as proficiency in English. Applications will be processed continuously until the positions are filled.

Closing date for applications:

Contact: Applications (CV, transcripts, contacts for references) can be emailed to Dr Khoa Nguyen (khoa@uow.edu.au).

The Gentry-Peikert-Vaikuntanathan (GPV) framework is utilized for constructing digital signatures, which is proven to be secure in the classical/quantum random-oracle model. Falcon is such a signature scheme, recognized as a compact and efficient signature among NIST-standardized signature schemes. Although a signature scheme based on the GPV framework is theoretically highly secure, it could be vulnerable to side-channel attacks and hence further research on physical attacks is required to make a robust signature scheme. We propose a general secret key recovery attack on GPV signatures using partial information about signatures obtained from side-channel attack. The three main contributions are summarized as follows. First, we introduce, for the first time, a concept of vulnerable partial information of GPV signatures and propose a secret key recovery attack, called OLS attack, which effectively utilizes partial information. In contrast to the approaches of Guerreau et al. (CHES 2022) and Zhang et al. (Eurocrypt 2023), which utilize filtered (or processed) signatures with hidden parallelepiped or learning slice schemes, the OLS attack leverages all the available signatures without filtering. We prove that the secret key recovered by the OLS attack converges to the real secret key in probability as the number of samples increases. Second, we utilize Gaussian leakage as partial information for the OLS attack on Falcon. As a result, the OLS attack shows a significantly higher success rate with fewer samples than the existing attack schemes. Furthermore, by incorporating the DDGR attack, the OLS attack can recover the secret key using much less samples with a success rate close to 100%. Moreover, we propose more efficient OLS attack on Falcon, which reduces the number of required side-channel attacks. Third, we propose an error-tolerant power analysis attack using MAP decoding, which effectively corrects the errors in samples to utilize Gaussian leakage correctly. In conclusion, the OLS attack is expected to strengthen the security of the GPV signatures including Falcon.

In PKC'24, de Saint Guilhem and Pedersen give a pseudorandom function basing on a relaxed group action assumption in the semi-honest setting. Basing on the assumption, they build an oblivious pseudorandom function (OPRF). Later, a recent paper by Levin and Pedersen uses the same function to build a verifiable random function (VRF), using the same assumption.

We give a structural attack on this problem by reducing it to a few group action inverse problems (GAIP/DLog) over small subgroups. This reduction allows us to apply a CRT-based attack to recover the secret key, ultimately lowering the problem’s effective security strength to under 70 classical bits when using CSIDH-512. Hence the strength of their pseudorandom functions is bounded above by the GAIP over the largest prime order subgroup. Clearly, Kuperberg’s subexponential attack can be used to further reduce its quantum security.

Information-theoretic or unconditional security provides the highest level of security --- independent of the computational capability of an adversary. Secret-sharing techniques achieve information-theoretic security by splitting a secret into multiple parts (called shares) and storing the shares across non-colluding servers. However, secret-sharing-based solutions suffer from high overheads due to multiple communication rounds among servers and/or information leakage due to access-patterns (i.e.., the identity of rows satisfying a query) and volume (i.e., the number of rows satisfying a query).

We propose SeaSearch, an information-theoretically secure approach that uses both additive and multiplicative secret-sharing, to efficiently support a large class of selection queries involving conjunctive, disjunctive, and range conditions. Two major contributions of SeaSearch are: (i) a new search algorithm using additive shares based on fingerprints, which were developed for string-matching over cleartext; and (ii) two row retrieval algorithms: one is based on multiplicative shares and another is based on additive shares. SeaSearch does not require communication among servers storing shares and does not reveal any information to an adversary based on access-patterns and volume.

Differential privacy (DP) has become the gold standard for privacy-preserving data analysis, but implementing it correctly has proven challenging. Prior work has focused on verifying DP at a high level, assuming the foundations are correct and a perfect source of randomness is available. However, the underlying theory of differential privacy can be very complex and subtle. Flaws in basic mechanisms and random number generation have been a critical source of vulnerabilities in real-world DP systems.

In this paper, we present SampCert, the first comprehensive, mechanized foundation for differential privacy. SampCert is written in Lean with over 12,000 lines of proof. It offers a generic and extensible notion of DP, a framework for constructing and composing DP mechanisms, and formally verified implementations of Laplace and Gaussian sampling algorithms. SampCert provides (1) a mechanized foundation for developing the next generation of differentially private algorithms, and (2) mechanically verified primitives that can be deployed in production systems. Indeed, SampCert’s verified algorithms power the DP offerings of Amazon Web Services (AWS), demonstrating its real-world impact.

SampCert’s key innovations include: (1) A generic DP foundation that can be instantiated for various DP definitions (e.g., pure, concentrated, Rényi DP); (2) formally verified discrete Laplace and Gaussian sampling algorithms that avoid the pitfalls of floating-point implementations; and (3) a simple probability monad and novel proof techniques that streamline the formalization. To enable proving complex correctness properties of DP and random number generation, SampCert makes heavy use of Lean’s extensive Mathlib library, leveraging theorems in Fourier analysis, measure and probability theory, number theory, and topology.

In this paper, we investigate the security of lightweight block ciphers, focusing on those that utilize the ADD-Rotate-XOR (ARX) and AND-Rotate-XOR (AND-RX) design paradigms. More specifically, we examine their resilience against boomerang-style attacks. First, we propose an automated search strategy that leverages the boomerang connectivity table (BCT) for AND operations ($\wedge BCT$) to conduct a complete search for boomerang and rectangle distinguishers for AND-RX ciphers. The proposed search strategy automatically considers all possible $\wedge BCT$ switches in the middle of the boomerang to optimise distinguishing probability. The correctness of the search strategy was verified experimentally. We were able to find the best boomerang and rectangle distinguishers to date in the single-key model for lightweight block ciphers KATAN32/48/64} and SIMON32/48. Next, we investigated BCT properties of ARX ciphers and discovered that a truncated boomerang switch could be formulated for the lightweight ARX cipher, CHAM. We were able to find the best single-key and related-key rectangle distinguishers to date for Cham. Our findings provide more accurate security margins of these lightweight ciphers against boomerang-style attacks.

Proving knowledge soundness of an interactive proof from scratch is often a challenging task. This has motivated the evelopment of various special soundness frameworks which, in a nutshell, separate knowledge extractors into two parts: (1) an extractor to produce a set of accepting transcripts conforming to some structure; (2) a witness recovery algorithm to recover a witness from a set of transcripts with said structure. These frameworks take care of (1), so it suffices for a protocol designer to specify (2) which is often simple(r).

Recently, works by Bünz–Fisch (TCC’23) and Aardal et al. (CRYPTO’24) provide new frameworks, called almost special soundness and predicate special soundness, respectively. To handle insufficiencies of special soundness, they deviate from its spirit and augment it in different ways. The necessity for their changes is that special soundness does not allow the challenges for useful sets of transcripts to depend on the transcripts themselves, but only on the challenges in the transcripts. As a consequence, (generalised) special soundness cannot express extraction strategies which reduce a computational problem to finding “inconsistent” accepting transcripts, for example in PCP/IOP-based or lattice-based proof systems, and thus provide (very) sub-optimal extractors. In this work, we introduce adaptive special soundness which captures extraction strategies exploiting inconsistencies between transcripts, e.g. transcripts containing different openings of the same commitment. Unlike (generalised) special soundness (Attema, Fehr, and Resch (TCC’23)), which specifies a target transcript structure, our framework allows specifying an extraction strategy which guides the extractor to sample challenges adaptively based on the history of prior transcripts. We extend the recent (almost optional) extractor of Attema, Fehr, Klooß and Resch (EPRINT 2023/1945) to our notion, and argue that it encompasses almost special soundness and predicate special soundness in many cases of interest.

As a challenging application, we modularise and generalise the lattice Bulletproofs analysis by Bünz–Fisch (TCC’23) using the adaptive special soundness framework. Moreover, we extend their analysis to the ring setting for a slightly wider selection of rings than rational integers.

Multilateral Trade Credit Set-off (MTCS) is a process run by a service provider that collects trade credit data (i.e. obligations from a firm to pay another firm) from a network of firms and detects cycles of debts that can be removed from the system. The process yields liquidity savings for the participants, who can discharge their debts without relying on expensive loans. We propose an MTCS protocol that protects firms' sensitive data, such as the obligation amount or the identity of the firms they trade with. Mathematically, this is analogous to solving the Minimum Cost Flow (MCF) problem over a graph of $n$ firms, where the $m$ edges are the obligations. State-of-the-art techniques for Secure MCF have an overall complexity of $O(n^{10} \log n)$ communication rounds, making it barely applicable even to small-scale instances. Our solution leverages novel secure techniques such as Graph Anonymization and Network Simplex to reduce the complexity of the MCF problem to $O(max(n, \log\log{n+m}))$ rounds of interaction per pivot operations in which $O(max(n^2, nm))$ comparisons and multiplications are performed. Experimental results show the tradeoff between privacy and optimality.

The COOL protocol of Chen (DISC'21) is a major advance that enables perfect security for various tasks (in particular, Byzantine Agreement in Synchrony and Reliable Broadcast in Asynchrony). For an input of size $L$ bits, its communication complexity is $O(nL+n^2 \log n)$, which is optimal up to a $\log n$ factor. Unfortunately, Chen’s analysis is rather intricate and complex.

Our main contribution is a simple analysis of a new variant of COOL based on elementary counting arguments. Our main consistency proof takes less than two pages (instead of over 20 pages), making the COOL protocol much more accessible. In addition, the simple analysis allows us to improve the protocol by reducing one round of communication and reducing the communication complexity by 40%.

In addition, we suggest a new way of extracting the core properties of COOL as a new primitive, which we call Graded Dispersal. We show how Graded Dispersal can then be used to obtain efficient solutions for Byzantine Agreement, Verifiable Information Dispersal, Gradecast, and Reliable Broadcast (in both Synchrony and Asynchrony, where appropriate). Our improvement of COOL directly applies here, and we improve the state-of-the-art in all those primitives by reducing at least one round and 40% communication.

The question of whether the complexity class P equals NP is a major unsolved problem in theoretical computer science. In this paper, we introduce a new language, the Add and XNOR (the negation of exclusive or (XOR)) problem, which has the simplest structure and perfect randomness, by extending the subset sum problem. We prove that P $\neq$ NP as it shows that an exhaustive search is necessary to solve the Add and XNOR problem. That is, problems that are verifiable in polynomial time are not necessarily solvable in polynomial time.

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). To our knowledge, it is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem; the circuit also achieves sublinear depth and nearly linear gate count. We build on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. Our circuit completely factors any number $N$, whose prime decomposition has distinct exponents, and finds at least one non-trivial factor if not all exponents are the same. In particular, to factor an $n$-bit integer $N=P^2 Q$ (with $P$ and $Q$ prime, and $Q<2^m$ for some $m$), our circuit uses $\widetilde{O}(m)$ qubits and has depth at most $\widetilde{O}(m + n/m)$, with $\widetilde{O}(n)$ quantum gates. When $m=\Theta(n^a)$ with $2/3 < a < 1$, the space and depth are sublinear in $n$, yet no known classical algorithms exploit the relatively small size of $Q$ to run faster than general-purpose factoring algorithms. We thus believe that factoring such numbers has potential to be the most concretely efficient classically-verifiable proof of quantumness currently known.

The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Crucially, our circuit reads the bits of the classical value $B$ in a streaming fashion, never storing more than $\widetilde{O}(\log A)$ qubits of quantum information at one time. In the context of the larger Jacobi algorithm for factoring $N = P^2Q$, this reduces the overall qubit count to be roughly proportional to the length of $Q$, rather than the length of $N$. Our circuit for computing the Jacobi symbol is also highly gate-efficient and parallelizable, achieving gate count $\widetilde{O}(\log B)$ and depth at most $\widetilde{O}(\log A + \log B/\log A)$. Finally, we note that our circuit for computing the Jacobi symbol generalizes to related problems, such as computing the greatest common divisor, and thus could be of independent interest.