International Association
for Cryptologic Research

Cuckoo hashing is a powerful primitive that enables storing items using small space with efficient lookups. At a high level, cuckoo hashing maps $n$ items into $b$ entries storing at most $\ell$ items such that each item is placed into one of $k$ randomly chosen entries. Additionally, there is an overflow stash that can store at most $s$ items. Many cryptographic primitives rely upon cuckoo hashing to privately and efficiently embed data. It is integral to ensure small failure probability for constructing cuckoo hashing tables as it directly relates to the privacy.

As our main result, we present a more efficient cuckoo hashing construction using more hash functions. For construction failure probability $\epsilon$, the query complexity of our cuckoo hashing scheme is $O(\sqrt{\log(1/\epsilon)/\log n})$. This is a quadratic improvement over previously known cuckoo hashing constructions that used larger stashes or entries. We also prove lower bounds matching our construction.

We also initiate the study of robust cuckoo hashing where the input set may be chosen with knowledge of the hash functions. We present a cuckoo hashing scheme with query overhead $\tilde{O}(\log \lambda)$ that is robust against PPT adversaries except with ${\bf negl}(\lambda)$ probability. Furthermore, we present lower bounds showing that this construction is tight and that extending previous approaches of large stashes or entries cannot obtain robustness except with $\Omega(n)$ query overhead. In other words, robust cuckoo hashing may only be obtained efficiently with a large number of hash functions.

As applications of our results, we obtain improved constructions for batch codes and private information retrieval. In particular, we present the most efficient explicit batch code and blackbox reduction from single-query PIR to batch PIR.

Users of decentralized financial networks suffer from inventive security exploits. Identity-based fraud prevention methods are inapplicable in these networks, as they contradict their privacy-minded design philosophy. Novel mitigation strategies are therefore needed. Their rollout, however, may damage other desirable network properties.

In this work, we introduce an evaluation framework for mitigation strategies in decentralized financial networks. This framework allows researchers and developers to examine and compare proposed protocol modifications along multiple axes, such as privacy, security, and user experience.

As an example, we focus on the jamming attack in the Lightning Network. Lightning is a peer-to-peer payment channel network on top of Bitcoin. Jamming is a cheap denial-of-service attack that allows an adversary to temporarily disable Lightning channels by flooding them with failing payments.

We propose a practical solution to jamming that combines unconditional fees and peer reputation. Guided by the framework, we show that, while discouraging jamming, our solution keeps the protocol incentive compatible. It also preserves security, privacy, and user experience, and is straightforward to implement. We support our claims analytically and with simulations. Moreover, our anti-jamming solution may help alleviate other Lightning issues, such as malicious channel balance probing.

Since their introduction in the 1970s, multi-party computation protocols have become the prevalent method for two or more parties to jointly compute an agreed upon function on private inputs without revealing them to other parties. While some efficiency gains in the offline phase of MPC protocols have been achieved, most works in the past have focused on optimising the online phase. Improvements to the online phase typically shifted significant workload to the offline phase. In this work we explore a novel approach to streamline the offline phase of secret sharing based MPC protocols by introducing a helper party that executes the preprocessing for the parties engaged in the online phase. We prove, that the security guarantees provided by the MPC protocols stay unchanged and demonstrate the efficiency of our approach in two sets of benchmarks. We furthermore give three examples of real world instantiations of the helper party to demonstrate that our approach is not only of a theoretical nature.

CRYSTALS-Kyber has been recently selected by the NIST as a new public-key encryption and key-establishment algorithm to be standardized. This makes it important to assess how well CRYSTALS-Kyber implementations withstand side-channel attacks. Software implementations of CRYSTALS-Kyber have been already analyzed and the discovered vulnerabilities were patched in the subsequently released versions. In this paper, we present a profiling side-channel attack on a hardware implementation of CRYSTALS-Kyber with the security parameter $k = 3$, Kyber768. Since hardware implementations carry out computation in parallel, they are typically more difficult to break than their software counterparts. We demonstrate a successful message (session key) recovery by deep learning-based power analysis. Our results indicate that currently available hardware implementations of CRYSTALS-Kyber need better protection against side-channel attacks.

In attribute-based signatures (ABS) for inner products, the digital signature analogue of attribute-based encryption for inner products (Katz et al., EuroCrypt'08), a signing-key (resp. signature) is labeled with an $n$-dimensional vector $\mathbf{x}\in\mathbf{Z}_p^n$ (resp. $\mathbf{y}\in\mathbf{Z}_p^n$) for a prime $p$, and the signing succeeds iff their inner product is zero, i.e., $ \langle \mathbf{x}, \mathbf{y} \rangle=0 \pmod p$. We generalize it to ABS for range of inner product (ARIP), requiring the inner product to be within an arbitrarily-chosen range $[L,R]$. As security notions, we define adaptive unforgeablity and perfect signer-privacy. The latter means that any signature reveals no more information about $\mathbf{x}$ than $\langle \mathbf{x}, \mathbf{y} \rangle \in[L,R]$. We propose two efficient schemes, secure under some Diffie-Hellman type assumptions in the standard model, based on non-interactive proof and linearly homomorphic signatures. The 2nd (resp. 1st) scheme is independent of the parameter $n$ in secret-key size (resp. signature size and verification cost). We show that ARIP has many applications, e.g., ABS for range evaluation of polynomials/weighted averages, fuzzy identity-based signatures, time-specific signatures, ABS for range of Hamming/Euclidean distance and ABS for hyperellipsoid predicates.

Adaptor signatures are a new cryptographic primitive that binds the authentication of a message to the revelation of a secret value. In recent years, this primitive has gained increasing popularity both in academia and practice due to its versatile use-cases in different Blockchain applications such as atomic swaps and payment channels. The security of these applications, however, crucially relies on users storing and maintaining the secret values used by adaptor signatures in a secure way. For standard digital signature schemes, cryptographic wallets have been introduced to guarantee secure storage of keys and execution of the signing procedure. However, no prior work has considered cryptographic wallets for adaptor signatures.

In this work, we introduce the notion of adaptor wallets. Adaptor wallets allow parties to securely use and maintain adaptor signatures in the Blockchain setting. Our adaptor wallets are both deterministic and operate in the hot/cold paradigm, which was first formalized by Das et al. (CCS 2019) for standard signature schemes. We introduce a new cryptographic primitive called adaptor signatures with rerandomizable keys, and use it to generically construct adaptor wallets. We further show how to instantiate adaptor signatures with rerandomizable keys from the ECDSA signature scheme and discuss that they can likely be built for Schnorr and Katz-Wang schemes as well. Finally, we discuss the limitations of the existing ECDSA- and Schnorr-based adaptor signatures w.r.t. deterministic wallets in the hot/cold setting and prove that it is impossible to overcome these drawbacks given the current state-of-the-art design of adaptor signatures.

Threshold cryptographic algorithms achieve robustness against key and access compromise by distributing secret keys among multiple entities. Most prior work focuses on threshold public-key primitives, despite extensive use of authenticated encryption in practice. Though the latter can be deployed in a threshold manner using multi-party computation (MPC), doing so incurs a high communication cost. In contrast, dedicated constructions of threshold authenticated encryption algorithms can achieve high performance. However to date, few such algorithms are known, most notably DiSE (distributed symmetric encryption) by Agrawal et al. (ACM CCS 2018). To achieve threshold authenticated encryption} (TAE), prior work does not suffice, due to shortcomings in definitions, analysis, and design, allowing for potentially insecure schemes, an undesirable similarity between encryption and decryption, and insufficient understanding of the impact of parameters due to lack of concrete analysis. In response, we revisit the problem of designing secure and efficient TAE schemes. (1) We give new TAE security definitions in the fully malicious setting addressing the aforementioned concerns. (2) We construct efficient schemes satisfying our definitions and perform concrete and more modular security analyses. (3) We conduct an extensive performance evaluation of our constructions, against prior ones.

The longest-chain paradigm introduced by the Bitcoin protocol allows Byzantine consensus with fluctuating participation where nodes can spontaneously become active and inactive anytime. Since then, there have been several follow-up works that aim to achieve similar guarantees without Bitcoin's computationally expensive proof of work. However, existing solutions do not fully inherit Bitcoin's dynamic participation support. Specifically, they have to assume malicious nodes are always active, i.e., no late joining or leaving is allowed for malicious nodes, due to a problem known as costless simulation. Another problem of Bitcoin is its notoriously large latency. A series of works try to improve the latency while supporting dynamic participation. The work of Momose-Ren (CCS 2022) eventually achieved constant latency, but its concrete latency is still large. This work addresses both of these problems by presenting a protocol that has $3$ round latency, tolerates one-third malicious nodes, and allows fully dynamic participation of both honest and malicious nodes. We also present a protocol with $2$ round latency with slightly lower fault tolerance.

We present a protocol for checking the values of a committed polynomial $\phi(X)$ over a mutliplicative subgroup $V\subset \mathbb{F}$ of size $m$ are contained in a table $T\in \mathbb{F}^N$. After an $O(N \log^2 N)$ preprocessing step, the prover algorithm runs in *quasilinear* time $O(m\log ^2 m)$. We improve upon the recent breakthrough results Caulk[ZBK+22] and Caulk+[PK22], which were the first to achieve the complexity sublinear in the full table size $N$ with prover time being $O(m^2+m\log N)$ and $O(m^2)$, respectively. We pose further improving this complexity to $O(m\log m)$ as the next important milestone for efficient zk-SNARK lookups.

This article explores the connection between radical isogenies and modular curves. Radical isogenies are formulas introduced by Castryck, Decru, and Vercauteren at Asiacrypt 2020, designed for the computation of chains of isogenies of fixed small degree $N.$ An important advantage of radical isogeny formulas over other formulas with a similar purpose, is that there is no need to generate a point of order $N$ that generates the kernel of the isogeny. Radical isogeny formulas were originally developed using elliptic curves in Tate normal form, while Onuki and Moriya have proposed radical isogenies formulas of degrees $3$ and $4$ on Montgomery curves. Furthermore, they attempted to obtain a simpler form of radical isogenies using enhanced elliptic and modular curves. In this article, we translate the original setup of radical isogenies (using Tate normal form) to the language of modular curves. In addition, we solve an open problem introduced by Onuki and Moriya regarding radical isogeny formulas on $X_0(N).$

Iterated Even-Mansour (IEM) schemes consist of a small number of fixed permutations separated by round key additions. They enjoy provable security, assuming the permutations are public and random. In particular, regarding chosen-key security in the sense of sequential indifferentiability (seq-indifferentiability), Cogliati and Seurin (EUROCRYPT 2015) showed that without key schedule functions, the 4-round Even-Mansour with Independent Permutations and no key schedule $EMIP_4(k,u) = k \oplus p_4 ( k \oplus p_3( k \oplus p_2( k\oplus p_1(k \oplus u))))$ is sequentially indifferentiable. Minimizing IEM variants for classical strong (tweakable) pseudorandom security has stimulated an attractive line of research. In this paper, we seek for minimizing the $EMIP_4$ construction while retaining seq-indifferentiability. We first consider $EMSP$, a natural variant of $EMIP$ using a single round permutation. Unfortunately, we exhibit a slide attack against $EMSP$ with any number of rounds. In light of this, we show that the 4-round $EM2P_4^{p_1,p_2} (k,u)=k\oplus p_1(k \oplus p_2(k\oplus p_2(k\oplus p_1(k\oplus u))))$ using 2 independent random permutations $p_1,p_2$ is seq-indifferentiable. This provides the minimal seq-indifferentiable IEM without key schedule.

Conventional bit-based division property (CBDP) and bit- based division property using three subsets (BDPT) introduced by Todo et al. at FSE 2016 are the most effective techniques for finding integral characteristics of symmetric ciphers. At ASIACRYPT 2019, Wang et al. proposed the idea of modeling the propagation of BDPT, and recently Liu et al. described a model set method that characterized the BDPT propagation. However, the linear layers of the block ciphers which are analyzed using the above two methods of BDPT propagation are restricted to simple bit permutation. Thus the feasibility of the MILP method of BDPT propagation to analyze ciphers with complex linear layers is not settled. In this paper, we focus on constructing an automatic search algorithm that can accurately characterize BDPT propagation for ciphers with complex linear layers. We first introduce BDPT propagation rule for the binary diffusion layer and model that propagation in MILP efficiently. The solutions to these inequalities are exact BDPT trails of the binary diffusion layer. Next, we propose a new algorithm that models Key-Xor operation in BDPT based on MILP technique. Based on these ideas, we construct an automatic search algorithm that accurately characterizes the BDPT propagation and we prove the correctness of our search algorithm. We demonstrate our model for the block ciphers with non-binary diffusion layers by decomposing the non-binary linear layer trivially by the COPY and XOR operations. Therefore, we apply our method to search integral distinguishers based on BDPT of SIMON, SIMON(102), PRINCE, MANTIS, PRIDE, and KLEIN block ciphers. For PRINCE and MANTIS, we find (2 + 2) and (3 + 3) round integral distinguishers respectively which are longest to date. We also improve the previous best integral distinguishers of PRIDE and KLEIN. For SIMON, SIMON(102), the integral distinguishers found by our method are consistent with the existing longest distinguishers.

In recent years, many major economies have paid close attention to central bank digital currency (CBDC). As an optional attribute of CBDC, dual offline transaction is considered to have great practical value under the circumstances for payment without network connection. However, there is no public report or paper on how to securely design or implement the dual offline transaction function specifically for CBDC. In this paper, we propose DOT-M, a practical dual offline transaction scheme designed for the mobile device user as either a payer or a payee. Precisely, adopting secure element (SE) and trusted execution environment (TEE), the architecture of trusted mobile device is constructed to protect security-sensitive keys and execution of the transaction protocol. According to the trusted architecture, the data structure for offline transaction is designed as well. On this basis, we describe the core procedures of DOT-M in detail, including registration, account synchronization, dual offline transaction, and online data updating. We also enumerate the exceptional situations that may occur during the dual offline transaction, and give specific handling methods for each situation. Moreover, six security properties of the scheme are analyzed under realistic assumptions. A prototype system is implemented and finally tested with possible parameters. The security analysis and experimental results indicate that our scheme could meet the practical requirement of CBDC offline transaction for mobile users from both aspects of security and efficiency.

We present “FairPoS”, the first blockchain protocol that achieves input fairness with adaptive security. Here, we introduce a novel notion of “input fairness”: the adversary cannot learn the plain-text of any finalized client input before it is include in a block in the chain’s common-prefix. Should input fairness hold, input ordering attacks which depend on the knowledge of plain-text of client inputs are thwarted. In FairPoS, input fairness with adaptive security is achieved by means of the delay encryption scheme of DeFeo et al., a recent cryptographic primitive related to time-lock puzzles, allowing all client inputs in a given round to be encrypted under the same key, which can only be extracted after enough time has elapsed. In contrast, alternative proposals that prevent input order attacks by encrypting user inputs are not adaptively secure as they rely on small static committees to perform distributed key generation and threshold decryption for efficiency’s sake. Such small committees are easily corrupted by an adaptive adversary with a corruption budget applicable over a large set of participants in a permissionless blockchain system. The key extraction task in delay encryption can, in principle, be performed by any party and is secure upon adaptive corruption, as no secret key material is learned. However, the key extraction requires highly specialized hardware in practice. Thus, FairPoS requires resource-rich, staking parties to insert extracted keys to blocks which enables light-clients to decrypt past inputs. Note that naive application of key extraction can result in chain stalls lasting the entire key extraction period. In FairPoS, this is addressed by a novel longest-extendable-chain rule. We formally prove that FairPoS achieves input fairness and the original security of Ouroborous Praos against an adaptive adversary.

In CRYPTO 2012, Zhandry developed generic semi-constant oracle technique and proved security of an identity-based encryption scheme, GPV-IBE, and full domain hash (FDH) signature scheme in the quantum random oracle model (QROM). However, the reduction provided by Zhandry incurred a quadratic reduction loss. In this work, we provide a much tighter proof, with linear reduntion loss, for the FDH, probabilistc FDH (PFDH), and GPV-IBE in the QROM. Our proof is based on the measure-and-reprogram technique developed by Don, Fehr, Majenz and Schaffner.

While online interactions and exchanges have grown exponentially over the past decade, most commercial infrastructures still operate through centralized protocols, and their success essentially depends on trust between different economic actors. Digital advances such as blockchain technology has led to a massive wave of Decentralized Ledger Technology (DLT) initiatives, protocols and solutions. This advance makes it possible to implement trustless systems in the real world, which, combined with appropriate economic and participatory incentives, would foster the proper functioning and drive the adoption of a decentralized platform among different actors. This paper describes an alternative to current commercial structures and networks by introducing Lyzis Labs, which is is an incentive-driven and democratic protocol designed to support a decentralized online marketplace, based on blockchain technology. The proposal, Lyzis Marketplace, allows to connect two or more people in a decentralized and secure way without having to rely on a Trusted Third Party (TTP) in order to perform physical asset exchanges while mainly providing transparent and fully protected data storage. This approach can potentially lead to the creation of a permissionless, efficient, secure and transparent business environment where each user can gain purchasing and decision-making power by supporting the collective welfare while following their personal interests during their various interactions on the network.

We revisit the problem of finding two consecutive $B$-smooth integers by giving an optimised implementation of the Conrey-Holmstrom-McLaughlin ``smooth neighbors'' algorithm. While this algorithm is not guaranteed to return the complete set of $B$-smooth neighbors, in practice it returns a very close approximation to the complete set, but does so in a tiny fraction of the time of its exhaustive counterparts. We exploit this algorithm to find record-sized solutions to the pure twin smooth problem. Though these solutions are still not large enough to be cryptographic parameters themselves, we feed them as input into known methods of searching for twins to yield cryptographic parameters that are much smoother than those given in prior works. Our methods seem especially well-suited to finding parameters for the SQISign signature scheme, particularly those that are geared towards high-security levels.

Asiacrypt 2022 will take place on December 5-9, Regent Hotel, Taipei, Taiwan.

More information and registration instructions can be found at https://asiacrypt.iacr.org/2022/

Some rooms at the venue + nearby hotels reserved for attendees at cut prices.
Stipends may still be available.

The Department of Computer Science and Technology is seeking to recruit a new faculty member at the Assistant or Associate Professor level who can contribute to research and teaching in the area of Privacy and/or Security. We aim to substantially broaden coverage of security-related research and teaching in the Department and we welcome applications relating to a wide range of security and privacy topics, including cryptography, cryptographic protocols and verification, distributed-systems security, malware analysis, forensics, machine learning, privacy, software security, computer hardware security, human factors, ledger technologies, security economics.

Closing date for applications:

Contact: Interested applicants are encouraged to make informal enquiries about the post to Dr Alice Hutchings and Professor Robert Watson, Alice.Hutchings@cst.cam.ac.uk Robert.Watson@cst.cam.ac.uk

More information: https://www.jobs.cam.ac.uk/job/37371/

Multiple Post-Docs in Post-Quantum Cryptography Academia Sinica, at the very edge of Taipei, is the national research institute of Taiwan. Here we have an active group of cryptography researchers, including Dr. Bo-Yin Yang, Dr. Kai-Min Chung, Dr. Tung Chou, and Dr. Ruben Niederhagen, covering wide research topics in cryptography and actively collaborating with researchers from related research areas such as program verification. We are looking for Post-Docs in PQC (Post-Quantum Cryptography). Here PQC is broadly defined. Starting date is early 2023, for terms of 1 year, renewable. Potential PQC research topics include cryptanalysis, implementation, and theory. Bo-Yin is in particular interested in people who have hands on experience with the design, implementation and/or analysis of cryptosystems submitted to NIST\'s post-quantum standardization project, and Kai-Min is looking for people interested in theoretical aspects of Post-Quantum Cryptography, such as security in the QROM model and novel (post-)quantum primitives and protocols. We are also particularly interested in people with diverse background to facilitate collaboration among our group members. Requires background in mathematics, computer science and cryptography. We desire a research track record in some aspects of post-quantum cryptography, but are especially looking for researchers with a broad research spectrum going from mathematical aspects to the practical side such as implementation aspects. We offer about 2200 USD (~2200 EUR) per month (commensurate with what a starting assistant professor makes locally) in salary and include a 5000 USD per year personal academic travel budget.

Closing date for applications:

Contact: Bo-Yin Yang (by at crypto.tw)

Kai-Min Chung (kmchung at iis.sinica.edu.tw)