International Association
for Cryptologic Research

We introduce a new variant of malicious obfuscation. Our formalism is incomparable to the existing definitions by Canetti and Varia (TCC 2010), Canetti et al. (EUROCRYPT 2022) and Badrinarayanan et al. (ASIACRYPT 2016). We show that this concept is natural and applicable to obfuscation-as-a-service platforms. We next define a new notion called auditable obfuscation which provides security against malicious obfuscation. Finally, we construct a proof of concept of the developed notions based on well-studied theoretical obfuscation proposals.

We use tropical algebras as platforms for a very efficient digital signature protocol. Security relies on computational hardness of factoring one-variable tropical polynomials; this problem is known to be NP-hard.

Post-quantum signature schemes based on the MPC-in-the-Head (MPCitH) paradigm are recently attracting significant attention as their security solely depends on the one-wayness of the underlying primitive, providing diversity for the hardness assumption in post-quantum cryptography. Kim et al. proposed AIM as an MPCitH-friendly one-way function characterized by large algebraic S-boxes and parallel design, which lead to short signature size (CCS 2023).

Recently, Liu et al. proposed a fast exhaustive search attack on AIM (ePrint 2023), which degrades the security of AIM by up to 13 bits. While communicating with the authors, they pointed out another possible vulnerability on AIM. In this paper, we propose AIM2 which mitigates all the vulnerabilities, and analyze its security against algebraic attacks.

Auction and voting schemes play a crucial role in the Web3 ecosystem. Yet currently deployed implementations either do not offer bid/vote privacy or require at least two rounds, hindering usability and security. We introduce Cicada, a general framework for using linearly homomorphic time-lock puzzles (HTLPs) to enable provably secure, non-interactive private auction and voting protocols. We instantiate our framework with an efficient new HTLP construction and novel packing techniques that enable succinct ballot correctness proofs independent of the number of candidates. We demonstrate the practicality of our approach by implementing our protocols for the Ethereum Virtual Machine (EVM).

This work introduces the notion of naysayer proofs. We observe that in numerous (zero-knowledge) proof systems, it is significantly more efficient for the verifier to be convinced by a so-called naysayer that a false proof is invalid than it is to check that a genuine proof is valid. We show that every NP language has constant-size and constant-time naysayer proofs. We also show practical constructions for several example proof systems, including FRI polynomial commitments, post-quantum secure digital signatures, and verifiable shuffles. Naysayer proofs enable an interesting new optimistic verification mode potentially suitable for resource-constrained verifiers, such as smart contracts.

The NTRU assumption provides one of the most prominent problems on which to base post-quantum cryptography. Because of the efficiency and security of NTRU-style schemes, structured variants have been proposed, using modules. In this work, we create a structured form of NTRU using lattices obtained from orders in cyclic division algebras of index 2, that is, from quaternion algebras. We present a public-key encryption scheme, and show that its public keys are statistically close to uniform. We then prove IND-CPA security of a variant of our scheme when the discriminant of the quaternion algebra is not too large, assuming the hardness of Learning with Errors in cyclic division algebras.

Zero-knowledge proof or argument systems for generic NP statements (such as circuit satisfiability) have typically been instantiated with cryptographic commitment schemes; this implies that the security of the proof system (e.g., computational or statistical) depends on that of the chosen commitment scheme. The MPC-in-the-Head paradigm (Ishai et al., JoC 2009) uses the same approach to construct zero-knowledge systems from the simulated execution of secure multiparty computation protocols.

This paper presents a novel method to construct zero-knowledge protocols which takes advantage of the unique properties of MPC-in-the-Head and replaces commitments with an oblivious transfer protocol. The security of the new construction is proven in the Universal Composability framework of security and suitable choices of oblivious transfer protocols are discussed together with their implications on the security properties and computational efficiency of the zero-knowledge system.

Recent works on lattice-based extractable polynomial commitments can be grouped into two classes: (i) non-interactive constructions that stem from the functional commitment by Albrecht, Cini, Lai, Malavolta and Thyagarajan (CRYPTO 2022), and (ii) lattice adaptations of the Bulletproofs protocol (S&P 2018). The former class enjoys security in the standard model, albeit a knowledge assumption is desired. In contrast, Bulletproof-like protocols can be made secure under falsifiable assumptions, but due to technical limitations regarding subtractive sets, they only offer inverse-polynomial soundness error. This issue becomes particularly problematic when transforming these protocols to the non-interactive setting using the Fiat-Shamir paradigm. In this work, we propose the first lattice-based non-interactive extractable polynomial commitment scheme which achieves polylogarithmic proof size and verifier runtime (in the length of the committed message) under standard assumptions. At the core of our work lies a new tree-based commitment scheme, along with an efficient proof of polynomial evaluation inspired by FRI (ICALP 2018). Natively, the construction is secure under a “multi-instance version” of the Power-Ring BASIS assumption (Eprint 2023/846). We then fully reduce security to the Module-SIS assumption by introducing several re-randomisation techniques which can be of independent interest.

In 2023, Basso, Maino, and Pope proposed FESTA~(Fast Encryption from Supersingular Torsion Attacks), an isogeny-based public-key encryption (PKE) protocol that uses the SIDH attack for decryption. In the same paper, they proposed a parameter for that protocol, but the parameter requires high-degree isogeny computations. In this paper, we introduce QFESTA (Quaternion Fast Encapsulation from Supersingular Torsion Attacks), a new variant of FESTA that works with better parameters using quaternion algebras and achieves IND-CCA security in QROM. To realize our protocol, we construct a new algorithm to compute an isogeny of non-smooth degree using quaternion algebra and the SIDH attack. Our protocol relies solely on $(2,2)$-isogeny and $3$-isogeny computations, promising a substantial reduction in computational costs. In addition, our protocol has significantly smaller data sizes for public keys and ciphertexts, approximately one-third the size of the original FESTA.

Fully homomorphic encryption (FHE) can perform computations on encrypted data, allowing us to analyze sensitive data without losing its security. The main issue for FHE is its lower performance, especially for high-precision computations, compared to calculations on plaintext data. Making FHE viable for practical use requires both algorithmic improvements and hardware acceleration. Recently, Klemsa and Önen (CODASPY'22) presented fast homomorphic algorithms for high-precision integers, including addition, multiplication and some fundamental functions, by utilizing a technique called redundant representation. Their algorithms were applied on TFHE, which was proposed by Chillotti et al. (Asiacrypt'16).

In this paper, we further accelerate this method by extending their algorithms to multithreaded environments. The experimental results show that our approach performs 128-bit addition in 0.41 seconds, 32-bit multiplication in 4.3 seconds, and 128-bit Max and ReLU functions in 1.4 seconds using a Tesla V100S server.

We study verifiable outsourcing of computation in a model where the verifier has black-box access to the function being computed. We introduce the problem of oracle-aided batch verification of computation (OBVC) for a function class $\mathcal{F}$. This allows a verifier to efficiently verify the correctness of any $f \in \mathcal{F}$ evaluated on a batch of $n$ instances $x_1, \ldots, x_n$, while only making $\lambda$ calls to an oracle for $f$ (along with $O(n \lambda)$ calls to low-complexity helper oracles), for security parameter $\lambda$.

We obtain the following positive and negative results:

1.) We build OBVC protocols for the class of all functions that admit random-self-reductions. Some of our protocols rely on homomorphic encryption schemes.

2.) We show that there cannot exist OBVC schemes for the class of all functions mapping $\lambda$-bit inputs to $\lambda$-bit outputs, for any $n = \mathsf{poly}(\lambda)$.

The well-defined information leakage of Encrypted Search Algorithms (ESAs) is predominantly analyzed by crafting so-called leakage attacks. These attacks utilize adversarially known auxiliary data and the observed leakage to attack an ESA instance built on a user's data. Known-data attacks require the auxiliary data to be a subset of the user's data. In contrast, sampled-data attacks merely rely on auxiliary data that is, in some sense, statistically close to the user's data and hence reflect a much more realistic attack scenario where the auxiliary data stems from a publicly available data source instead of the private user's data.

Unfortunately, it is unclear what "statistically close" means in the context of sampled-data attacks. This leaves open how to measure whether data is close enough for attacks to become a considerable threat. Furthermore, sampled-data attacks have so far not been evaluated in the more realistic attack scenario where the auxiliary data stems from a source different to the one emulating the user's data. Instead, auxiliary and user data have been emulated with data from one source being split into distinct training and testing sets. This leaves open whether and how well attacks work in the mentioned attack scenario with data from different sources.

In this work, we address these open questions by providing a measurable metric for statistical closeness in encrypted keyword search. Using real-world data, we show a clear exponential relation between our metric and attack performance. We uncover new data that are intuitively similar yet stem from different sources. We discover that said data are not "close enough" for sampled-data attacks to perform well. Furthermore, we provide a re-evaluation of sampled-data keyword attacks with varying evaluation parameters and uncover that some evaluation choices can significantly affect evaluation results.

An hard homogeneous space (HHS) is a finite group acting on a set with the group action being hard to invert and the set lacking any algebraic structure. As such HHS could potentially replace finite groups where the discrete logarithm is hard for building cryptographic primitives and protocols in a post-quantum world.

Threshold HHS-based primitives typically require parties to compute the group action of a secret-shared input on a public set element. On one hand this could be done through generic MPC techniques, although they incur in prohibitive costs due to the high complexity of circuits evaluating group actions known to date. On the other hand round-robin protocols only require black box usage of the HHS. However these are highly sequential procedures, taking as many rounds as parties involved. The high round complexity appears to be inherent due the lack of homomorphic properties in HHS, yet no lower bounds were known so far.

In this work we formally show that round-robin protocols are optimal. In other words, any at least passively secure distributed computation of a group action making black-box use of an HHS must take a number of rounds greater or equal to the threshold parameter. We furthermore study fair protocols in which all users receive the output in the same round (unlike plain round-robin), and prove communication and computation lower bounds of $\Omega(n \log_2 n)$ for $n$ parties. Our results are proven in Shoup's Generic Action Model (GAM), and hold regardless of the underlying computational assumptions.

The University of Birmingham’s Centre for Cyber Security and Privacy is looking for a research fellow (postdoc) to work on our EPSRC-funded project on the security analysis of post-quantum cryptography algorithms.

The successful candidate will be employed on a full-time, fixed-term contract up to September 2026. Full-time starting salary is normally in the range £34,980 to £44,263. (Some) remote work is possible, depending on the circumstances. The University provides a range of employee benefits, as well as opportunities for career development and training. The project includes substantial funding for conference travel.

Applicants should have a PhD, or be close to completing a PhD, in a relevant subject (crypto, computer algebra, maths, etc.). We are particularly keen on applications with a quantum cryptanalysis or quantum algorithm background, but strong candidates with other backgrounds will also be given due consideration. Prior track record on post-quantum cryptography and cryptanalysis is also a plus.

The post-doc will be working in the Centre for Cyber Security and Privacy, which currently has 14 permanent academics as well as 21 postdocs/PhD students.

The application deadline is 16 Oct 2023. Applications have to be made online at: https://edzz.fa.em3.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_6001/job/3185/

Closing date for applications:

Contact: Informal enquiries can be made to Christophe Petit C.Petit.1@bham.ac.uk

More information: https://edzz.fa.em3.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_6001/job/3185/

My group is hiring Ph.D. students on AI security and Homomorphic Encryption accelerators.

We are seeking students who are passionate about research, motivated to explore new ideas, and willing to work in a team environment. You will be expected to work diligently, communicate your results in writing, and publish research papers in top conferences/journals in the field of hardware security.

A strong background in one or more of these topics is required: linear algebra, probability theory, cryptography, or digital hardware design. Prior experience with Verilog hardware description language (HDL), electronic design automation (EDA) tools for application-specific integrated circuit (ASIC) design, or/and field programmable gate arrays (FPGAs) is preferred.

The candidate is expected to have excellent verbal and written communication skills. International applications: check the department website for GPA, TOEFL, and GRE requirements; visa sponsorship will be provided.

Closing date for applications:

Contact: The deadline to apply is January 15, 2024. Please contact Dr. Seetal Potluri (spotluri@albany.edu) for more information.

Event date: 1 December to 3 December 2023

State-machine replication (SMR) allows a state machine to be replicated across a set of replicas and handle clients' requests as a single machine. Most existing SMR protocols are leader-based, i.e., requiring a leader to order requests and coordinate the protocol. This design places a disproportionately high load on the leader, inevitably impairing the scalability. If the leader fails, a complex and bug-prone fail-over protocol is needed to switch to a new leader. An adversary can also exploit the fail-over protocol to slow down the protocol. In this paper, we propose a crash-fault tolerant SMR named Cascade, with the following properties: • Leaderless: it does not require a leader, hence completely get rid of the fail-over protocol. • Scalable: it can scale to a large number of replicas. %its throughput increases with the number of replicas. • Robust: it behaves well even under a poor network connection. We provide a full-fledged implementation of Cascade and systematically evaluate its performance. Our benchmark results show that Cascade achieves a peak throughput of around two million TPS, up to 8.7$\times$ higher than the state-of-the-art leaderless SMR.

A prevalent issue in the residue number system (RNS) variant of the Cheon-Kim-Kim-Song (CKKS) homomorphic encryption (HE) scheme is the challenge of efficiently achieving high precision on hardware architectures with a fixed, yet smaller, word-size of bit-length $W$, especially when the scaling factor satisfies $\log\Delta > W$. In this work, we introduce an efficient solution termed composite scaling. In this approach, we group multiple RNS primes as $q_\ell:= \prod_{j=0}^{t-1} q_{\ell,j}$ such that $\log q_{\ell,j} < W$ for $0\le j < t$, and use each composite $q_\ell$ in the rescaling procedure as $\mathsf{ct}\mapsto \lfloor \mathsf{ct} / q_\ell\rceil$. Here, the number of primes, denoted by $t$, is termed the composition degree. This strategy contrasts the traditional rescaling method in RNS-CKKS, where each $q_\ell$ is chosen as a single $\log\Delta$-bit prime, a method we designate as single scaling. To achieve higher precision in single scaling, where $\log\Delta > W$, one would either need a novel hardware architecture with word size $W' > \log\Delta$ or would have to resort to relatively inefficient solutions rooted in multi-precision arithmetic. This problem, however, doesn't arise in composite scaling. In the composite scaling approach, the larger the composition degree $t$, the greater the precision attainable with RNS-CKKS across an extensive range of secure parameters tailored for workload deployment. We have integrated composite scaling RNS-CKKS into both OpenFHE and Lattigo libraries. This integration was achieved via a concrete implementation of the method and its application to the most up-to-date workloads, specifically, logistic regression training and convolutional neural network inference. Our experiments demonstrate that single and composite scaling approaches are functionally equivalent, both theoretically and practically.

Blockchain users who submit transactions through private pools are guaranteed pre-trade privacy but face execution risk. We argue that private pools serve the intended purpose of eliminating frontrunning risk, only if such risk is high. Otherwise, some validators may decide to avoid monitoring private pools to preserve rents extracted from frontrunning bots. Private pools intensify the execution arms race for bots, thus decreasing their payoffs {and increasing validators' rents}. The private pool option reduces blockspace allocative inefficiencies and raises aggregate welfare.

Dual attacks aiming at decoding generic linear codes have been found recently to outperform for certain parameters information set decoding techniques which have been for $60$ years the dominant tool for solving this problem and choosing the parameters of code-based cryptosystems. However, the analysis of the complexity of these dual attacks relies on some unproven assumptions that are not even fully backed up with experimental evidence.

These dual attacks can actually be viewed as the code-based analogue of dual attacks in lattice based cryptography. Here too, dual attacks have been found out those past years to be strong competitors to primal attacks and a controversy has emerged whether similar heuristics made for instance on the independence of certain random variables really hold.

We will show that the dual attacks in coding theory can be studied by providing in a first step a simple alternative expression of the fundamental quantity used in these dual attacks. We then show that this expression can be studied without relying on independence assumptions whatsoever.

This study leads us to discover that there is indeed a problem with the latest and most powerful dual attack introduced in the recent Asiacrypt 2022 paper "Statistical decoding 2.0: Reducing Decoding to LPN" (RLPN) and that for the parameters chosen in this algorithm there are indeed false candidates which are produced and which are not predicted by the analysis provided there which relies on independence assumptions.

We then suggest a slight modification of this algorithm consisting in a further verification step, analyze it thoroughly, provide experimental evidence that our analysis is accurate and show that the complexity claims made in RLPN are indeed valid for this modified algorithm. This approach provides a simple methodology for studying rigorously dual attacks which could turn out to be useful for further developing the subject.