Topics in Cryptology – CT-RSA 2021

Frontmatter

Secure Fast Evaluation of Iterative Methods: With an Application to Secure PageRank

Abstract

Iterative methods are a standard technique in many areas of scientific computing. The key idea is that a function is applied repeatedly until the resulting sequence converges to the correct answer. When applying such methods in a secure computation methodology (for example using MPC, FHE, or SGX) one either needs to perform enough steps to ensure convergence irrespective of the input data, or one needs to perform a convergence test within the algorithm, and this itself leads to a leakage of data. Using the Banach Fixed Point theorem, and its extensions, we show that this data-leakage can be quantified. We then apply this to a secure (via MPC) implementation of the PageRank methodology. For PageRank we show that allowing this small amount of data-leakage produces a much more efficient secure implementation, and that for many underlying graphs this ‘leakage’ is already known to any attacker.

Daniele Cozzo, Nigel P. Smart, Younes Talibi Alaoui

Compilation of Function Representations for Secure Computing Paradigms

Abstract

This paper introduces M-Circuits, a program representation which generalizes arithmetic and binary circuits. This new representation is motivated by the way modern multi-party computation (MPC) systems based on linear secret sharing schemes actually operate. We then show how this representation also allows one to construct zero knowledge proof (ZKP) systems based on the MPC-in-the-head paradigm. The use of the M-Circuit program abstraction then allows for a number of program-specific optimizations to be applied generically. It also allows to separate complexity and security optimizations for program compilation from those for application protocols (MPC or ZKP).

Karim Baghery, Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Nigel P. Smart, Titouan Tanguy

Oblivious TLS via Multi-party Computation

Abstract

In this paper, we describe Oblivious TLS: an MPC protocol that we prove UC secure against a majority of actively corrupted parties. The protocol securely implements TLS 1.3. Thus, any party P who runs TLS can communicate securely with a set of servers running Oblivious TLS; P does not need to modify anything, or even be aware that MPC is used.

Applications of this include communication between servers who offer MPC services and clients, to allow the clients to easily and securely provide inputs or receive outputs. Also, an organization could use Oblivious TLS to improve in-house security while seamlessly connecting to external parties.

Our protocol runs in the preprocessing model, and we did a preliminary non-optimized implementation of the on-line phase. In this version, the hand-shake completes in about 1 s. Based on implementation results from other work, performance of the record protocol using the standard AES-GCM can be expected to achieve an online throughput of about 3 MB/s.

Damiano Abram, Ivan Damgård, Peter Scholl, Sven Trieflinger

Noisy Simon Period Finding

Abstract

Let \(f: \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n\) be a Boolean function with period \(\mathbf {s}\). It is well-known that Simon’s algorithm finds \(\mathbf {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 \(\tau (n)\) we measure erroneous vectors that are not orthogonal to \(\mathbf {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 \(\tau (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 \(\tau (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.

Alexander May, Lars Schlieper, Jonathan Schwinger

A Bunch of Broken Schemes: A Simple yet Powerful Linear Approach to Analyzing Security of Attribute-Based Encryption

Abstract

Verifying security of advanced cryptographic primitives such as attribute-based encryption (ABE) is often difficult. In this work, we show how to break eleven schemes: two single-authority and nine multi-authority (MA) ABE schemes. Notably, we break DAC-MACS, a highly-cited multi-authority scheme, published at TIFS. This suggests that, indeed, verifying security of complex schemes is complicated, and may require simpler tools. The multi-authority attacks also illustrate that mistakes are made in transforming single-authority schemes into multi-authority ones. To simplify verifying security, we systematize our methods to a linear approach to analyzing generic security of ABE. Our approach is not only useful in analyzing existing schemes, but can also be applied during the design and reviewing of new schemes. As such, it can prevent the employment of insecure (MA-)ABE schemes in the future.

Marloes Venema, Greg Alpár

Zero-Correlation Linear Cryptanalysis with Equal Treatment for Plaintexts and Tweakeys

Abstract

The original zero-correlation linear attack on a tweakable block cipher \(E_{K, T}\) (\(E_{K, T}\) is an ordinary block cipher when \(|T| = 0\)) with key K and tweak T exploits linear approximations \(\langle \alpha , x \rangle \oplus \langle \beta , E_{K,T}(x) \rangle \) with correlation zero for any fixed K and T, where the correlation is computed over all possible plaintexts x. Obviously, the plaintexts, keys, and tweaks are not treated equally. In this work, we regard the tweakable block cipher as a vectorial Boolean function \(F: \mathbb {F}_2^{ n+m+l } \rightarrow \mathbb {F}_2^{n}\) mapping \((x, K, T) \in \mathbb {F}_2^{ n+m+l }\) to \(E_{K,T}(x) \in \mathbb F_2^n\), and try to find zero-correlation linear approximations of F of the form

$$ \langle \alpha , x \rangle \oplus \langle \gamma , K \rangle \oplus \langle \lambda , T \rangle \oplus \langle \beta , F(K, T, x) \rangle , $$

where the correlation is computed over all possible (x, K, T)’s. Standard tools based on SAT and SMT can be employed to search for this type of zero-correlation linear approximations under a unified framework of which Ankele et al.’s work on zero-correlation analysis at ToSC 2019 by taking tweaks into account can be seen as a special case with linear tweak schedules and \(\gamma = 0\). Due to the links between zero-correlation linear approximations and integral distinguishers, we can convert the new type of zero-correlation linear distinguishers into related-tweakey integral distinguishers. We apply our method to TWINE, LBlock, and SKINNY with both linear and nonlinear tweakey schedules. As a result, we obtain the longest distinguishers for TWINE and longer zero-correlation linear distinguishers for LBlock and SKINNY when considering key/tweak schedule. The correctness of our method is verified by recovering the results of Ankele et al. and experiments on a toy cipher.

Chao Niu, Muzhou Li, Siwei Sun, Meiqin Wang

SoK: Game-Based Security Models for Group Key Exchange

Abstract

Group key exchange (GKE) protocols let a group of users jointly establish fresh and secure key material. Many flavors of GKE have been proposed, differentiated by, among others, whether group membership is static or dynamic, whether a single key or a continuous stream of keys is established, and whether security is provided in the presence of state corruptions (forward and post-compromise security). In all cases, an indispensable ingredient to the rigorous analysis of a candidate solution is a corresponding formal security model. We observe, however, that most GKE-related publications are more focused on building new constructions that have more functionality or are more efficient than prior proposals, while leaving the job of identifying and working out the details of adequate security models a subordinate task.

In this systematization of knowledge we bring the formal modeling of GKE security to the fore by revisiting the intuitive goals of GKE, critically evaluating how these goals are reflected (or not) in the established models, and how they would be best considered in new models. We classify and compare characteristics of a large selection of game-based GKE models that appear in the academic literature, including those proposed for GKE with post-compromise security. We observe a range of shortcomings in some of the studied models, such as dependencies on overly restrictive syntactical constrains, unrealistic adversarial capabilities, or simply incomplete definitions. Our systematization enables us to identify a coherent suite of desirable characteristics that we believe should be represented in all general purpose GKE models. To demonstrate the feasibility of covering all these desirable characteristics simultaneously in one concise definition, we conclude with proposing a new generic reference model for GKE.

Bertram Poettering, Paul Rösler, Jörg Schwenk, Douglas Stebila

EPID with Malicious Revocation

Abstract

EPID systems are anonymous authentication protocols where a device can be revoked by including one of its signatures in a revocation list. Such protocols are today included in the ISO/IEC 20008-2 standard and are embedded in billions of chips, which make them a flagship of advanced cryptographic tools. Yet, their security analysis is based on a model that suffers from several important limitations, which either questions the security assurances EPID can provide in the real world or prevents such systems from achieving their full impact. The most prominent example is the one of revocation lists. Although they could be managed locally by verifiers, which would be natural in most use-cases, the security model assumes that they are managed by a trusted entity, a requirement that is not easily met in practice and that is thus tempting to ignore, as illustrated in the corresponding standard.

In this paper, we propose to revisit the security model of EPID, by removing some limitations of previous works but mostly by answering the following question: what can we achieve when revocation lists are generated by a malicious entity?

Surprisingly, even in this disadvantageous context, we show that it is possible to retain strong properties that we believe to better capture the spirit of EPID systems. Moreover, we show that we can construct very efficient schemes resisting such powerful adversaries by essentially tweaking previous approaches. In particular, our constructions do not require to perform any significant test on the revocation lists during the signature generation process. These constructions constitute the second contribution of this paper.

Olivier Sanders, Jacques Traoré

Signed Diffie-Hellman Key Exchange with Tight Security

Abstract

We propose the first tight security proof for the ordinary two-message signed Diffie-Hellman key exchange protocol in the random oracle model. Our proof is based on the strong computational Diffie-Hellman assumption and the multi-user security of a digital signature scheme. With our security proof, the signed DH protocol can be deployed with optimal parameters, independent of the number of users or sessions, without the need to compensate any security loss. We abstract our approach with a new notion called verifiable key exchange.

In contrast to a known tight three-message variant of the signed Diffie-Hellman protocol (Gjøsteen and Jager, CRYPTO 2018), we do not require any modification to the original protocol, and our tightness result is proven in the “Single-Bit-Guess” model which we known can be tightly composed with symmetric cryptographic primitives to establish a secure channel.

Jiaxin Pan, Chen Qian, Magnus Ringerud

Lattice-Based Proof of Shuffle and Applications to Electronic Voting

Abstract

A verifiable shuffle of known values is a method for proving that a collection of commitments opens to a given collection of known messages, without revealing a correspondence between commitments and messages. We propose the first practical verifiable shuffle of known values for lattice-based commitments.

Shuffles of known values have many applications in cryptography, and in particular in electronic voting. We use our verifiable shuffle of known values to build a practical lattice-based cryptographic voting system that supports complex ballots. Our scheme is also the first construction from candidate post-quantum secure assumptions to defend against compromise of the voter’s computer using return codes.

We implemented our protocol and present benchmarks of its computational runtime. The size of the verifiable shuffle is \(17\tau \) KB and takes time \(33\tau \) ms for \(\tau \) voters. This is around 5 times faster and at least 50% smaller per vote than the lattice-based voting scheme by del Pino et al. (ACM CCS 2017), which can only handle yes/no-elections.

Diego F. Aranha, Carsten Baum, Kristian Gjøsteen, Tjerand Silde, Thor Tunge

More Efficient Shuffle Argument from Unique Factorization

Abstract

Efficient shuffle arguments are essential in mixnet-based e-voting solutions. Terelius and Wikström (TW) proposed a 5-round shuffle argument based on unique factorization in polynomial rings. Their argument is available as the Verificatum software solution for real-world developers, and has been used in real-world elections. It is also the fastest non-patented shuffle argument. We will use the same basic idea as TW but significantly optimize their approach. We generalize the TW characterization of permutation matrices; this enables us to reduce the communication without adding too much to the computation. We make the TW shuffle argument computationally more efficient by using Groth’s coefficient-product argument (JOC 2010). Additionally, we use batching techniques. The resulting shuffle argument is the fastest known \(\le \)5-message shuffle argument, and, depending on the implementation, can be faster than Groth’s argument (the fastest 7-message shuffle argument).

Toomas Krips, Helger Lipmaa

Cryptanalysis of a Dynamic Universal Accumulator over Bilinear Groups

Abstract

In this paper we cryptanalyse the two accumulator variants proposed by Au et al. [1], which we call the \(\alpha \)-based construction and the common reference string-based (\(\mathcal {CRS}\) -based) construction. We show that if non-membership witnesses are issued according to the \(\alpha \)-based construction, an attacker that has access to multiple witnesses is able to efficiently recover the secret accumulator parameter \(\alpha \) and completely break its security. More precisely, if p is the order of the underlying bilinear group, the knowledge of \(O(\log p\log \log p)\) non-membership witnesses permits to successfully recover \(\alpha \). Further optimizations and different attack scenarios allow to reduce the number of required witnesses to \(O(\log p)\), together with practical attack complexity. Moreover, we show that accumulator’s collision resistance can be broken if just one of these non-membership witnesses is known to the attacker. We then show how all these attacks for the \(\alpha \)-based construction can be easily prevented by using instead a corrected expression for witnesses.

Although outside the original security model assumed by Au et al. but motivated by some possible concrete application of the scheme where the Manager must have exclusive rights for issuing witnesses (e.g. white/black list based authentication mechanisms), we show that if non-membership witnesses are issued using the \(\mathcal {CRS}\)-based construction and the \(\mathcal {CRS}\) is kept secret by the Manager, an attacker accessing multiple witnesses can reconstruct the \(\mathcal {CRS}\) and compute witnesses for arbitrary new elements. In particular, if the accumulator is initialized by adding m secret elements, the knowledge of m non-membership witnesses allows to succeed in such attack.

Alex Biryukov, Aleksei Udovenko, Giuseppe Vitto

FAN: A Lightweight Authenticated Cryptographic Algorithm

Abstract

The wide application of the low-end embedded devices has largely stimulated the development of lightweight ciphers. In this paper, we propose a new lightweight authenticated encryption with additional data (AEAD) algorithm, named as Fan, which is based on a first non-Grain-like small-state stream cipher that adopts a novel block-wise structure, inspired by the 4-blade daily electric fan. It takes a 128-bit key, a 64-bit initial vector (IV), and a 192-bit state, promising 128-bit security and up to 72-bit authentication tag with the IV-respecting restriction. It consists of a nonlinear spindle, four linear blades and an accumulator, and updates by constant mutual feedbacks between the linear and nonlinear parts, which rapidly provides highly confused level by parallel diffusing the fastest-changing state of spindle. The key is used both in the initialization and generation phases as part of input and state respectively, making Fan suitable for resource-constrained scenarios with internal state diminishment but no security loss. A thorough security evaluation of the entire AEAD mode is provided, which shows that Fan can achieve enough security margin against known attacks. Furthermore, Fan can be implemented efficiently not only in hardware environments but also in software platforms, whose operations are carefully chosen for bit-slice technique, especially the S-box is newly designed efficiently implemented by logic circuit. The hardware implementation requires about 2327 GE on 90 nm technology with a throughput of 9.6 Gbps. The software implementation runs about 8.0 cycle/byte.

Lin Jiao, Dengguo Feng, Yonglin Hao, Xinxin Gong, Shaoyu Du

Related-Key Analysis of Generalized Feistel Networks with Expanding Round Functions

Abstract

We extend the prior provable related-key security analysis of (generalized) Feistel networks (Barbosa and Farshim, FSE 2014; Yu et al., Inscrypt 2020) to the setting of expanding round functions, i.e., n-bit to m-bit round functions with \(n<m\). This includes Expanding Feistel Networks( \(\mathsf {EFN}\text {s}\) ) that purely rely on such expanding round functions, and Alternating Feistel Networks( \(\mathsf {AFN}\text {s}\) ) that alternate expanding and contracting round functions. We show that, when two independent keys \(K_1,K_2\) are alternatively used in each round, (a) \(2\lceil \frac{m}{n}\rceil +2\) rounds are sufficient for related-key security of \(\mathsf {EFN}\text {s}\), and (b) a constant number of 4 rounds are sufficient for related-key security of \(\mathsf {AFN}\text {s}\). Our results complete the picture of provable related-key security of GFNs, and provide additional theoretical support for the \(\mathsf {AFN}\)-based NIST format preserving encryption standards FF1 and FF3.

Yuqing Zhao, Wenqi Yu, Chun Guo

The Key-Dependent Message Security of Key-Alternating Feistel Ciphers

Abstract

Key-Alternating Feistel (KAF) ciphers are a popular variant of Feistel ciphers whereby the round functions are defined as \(x \mapsto \mathsf {F}(k_i \oplus x)\), where \(k_i\) are the round keys and \(\mathsf {F}\) is a public random function. Most Feistel ciphers, such as DES, indeed have such a structure. However, the security of this construction has only been studied in the classical CPA/CCA models. We provide the first security analysis of KAF ciphers in the key-dependent message (KDM) attack model, where plaintexts can be related to the private key. This model is motivated by cryptographic schemes used within application scenarios such as full-disk encryption or anonymous credential systems.

We show that the four-round KAF cipher, with a single function \(\mathsf {F}\) reused across the rounds, provides KDM security for a non-trivial set of KDM functions. To do so, we develop a generic proof methodology, based on the H-coefficient technique, that can ease the analysis of other block ciphers in such strong models of security.

Pooya Farshim, Louiza Khati, Yannick Seurin, Damien Vergnaud

Mesh Messaging in Large-Scale Protests: Breaking Bridgefy

Abstract

Mesh messaging applications allow users in relative proximity to communicate without the Internet. The most viable offering in this space, Bridgefy, has recently seen increased uptake in areas experiencing large-scale protests (Hong Kong, India, Iran, US, Zimbabwe, Belarus), suggesting its use in these protests. It is also being promoted as a communication tool for use in such situations by its developers and others. In this work, we report on a security analysis of Bridgefy. Our results show that Bridgefy, as analysed, permitted its users to be tracked, offered no authenticity, no effective confidentiality protections and lacked resilience against adversarially crafted messages. We verified these vulnerabilities by demonstrating a series of practical attacks on Bridgefy. Thus, if protesters relied on Bridgefy, an adversary could produce social graphs about them, read their messages, impersonate anyone to anyone and shut down the entire network with a single maliciously crafted message.

Martin R. Albrecht, Jorge Blasco, Rikke Bjerg Jensen, Lenka Mareková

Inverse-Sybil Attacks in Automated Contact Tracing

Abstract

Automated contract tracing aims at supporting manual contact tracing during pandemics by alerting users of encounters with infected people. There are currently many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized” ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly broadcast (using low energy Bluetooth) some values, and at the same time store (a function of) incoming messages broadcasted by users in their proximity. In the existing proposals one can trigger false positives on a massive scale by an “inverse-Sybil” attack, where a large number of devices (malicious users or hacked phones) pretend to be the same user, such that later, just a single person needs to be diagnosed (and allowed to upload) to trigger an alert for all users who were in proximity to any of this large group of devices.

We propose the first protocols that do not succumb to such attacks assuming the devices involved in the attack do not constantly communicate, which we observe is a necessary assumption. The high level idea of the protocols is to derive the values to be broadcasted by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil attack will not be able to connect their respective chains and thus only one of them will be able to upload. Our protocols also achieve security against replay, belated replay, and one of them even against relay attacks.

Benedikt Auerbach, Suvradip Chakraborty, Karen Klein, Guillermo Pascual-Perez, Krzysztof Pietrzak, Michael Walter, Michelle Yeo

On the Effectiveness of Time Travel to Inject COVID-19 Alerts

Abstract

Digital contact tracing apps allow to alert people who have been in contact with people who may be contagious. The Google/Apple Exposure Notification (GAEN) system is based on Bluetooth proximity estimation. It has been adopted by many countries around the world. However, many possible attacks are known. The goal of some of them is to inject a false alert on someone else’s phone. This way, an adversary can eliminate a competitor in a sport event or a business in general. Political parties can also prevent people from voting.

In this report, we review several methods to inject false alerts. One of them requires to corrupt the clock of the smartphone of the victim. For that, we build a time-traveling machine to be able to remotely set up the clock on a smartphone and experiment our attack. We show how easy this can be done. We successfully tested several smartphones with either the Swiss or the Italian app (SwissCovid or Immuni). We confirm it also works on other GAEN-based apps: NHS COVID-19 (in England and Wales), Corona-Warn-App (in Germany), and Coronalert (Belgium).

The time-machine can also be used in active attack to identify smartphones. We can recognize smartphones that we have passively seen in the past. We can passively recognize in the future smartphones that we can see in present. We can also make smartphones identify themselves with a unique number.

Finally, we report a simpler attack which needs no time machine but relies on the existence of still-valid keys reported on the server. We observed the case in several countries. The attack is made trivial in Austria, Denmark, Spain, Italy, the Netherlands, Alabama, Delaware, Wyoming, Canada, and England & Wales. Other regions are affected by interoperability too.

Vincenzo Iovino, Serge Vaudenay, Martin Vuagnoux

SoK: How (not) to Design and Implement Post-quantum Cryptography

Abstract

Post-quantum cryptography has known a Cambrian explosion in the last decade. What started as a very theoretical and mathematical area has now evolved into a sprawling research field, complete with side-channel resistant embedded implementations, large scale deployment tests and standardization efforts. This study systematizes the current state of knowledge on post-quantum cryptography. Compared to existing studies, we adopt a transversal point of view and center our study around three areas: (i) paradigms, (ii) implementation, (iii) deployment. Our point of view allows to cast almost all classical and post-quantum schemes into just a few paradigms. We highlight trends, common methodologies, and pitfalls to look for and recurrent challenges.

James Howe, Thomas Prest, Daniel Apon

Dual Lattice Attacks for Closest Vector Problems (with Preprocessing)

Abstract

The dual attack has long been considered a relevant attack on lattice-based cryptographic schemes relying on the hardness of learning with errors (LWE) and its structured variants. As solving LWE corresponds to finding a nearest point on a lattice, one may naturally wonder how efficient this dual approach is for solving more general closest vector problems, such as the classical closest vector problem (CVP), the variants bounded distance decoding (BDD) and approximate CVP, and preprocessing versions of these problems. While primal, sieving-based solutions to these problems (with preprocessing) were recently studied in a series of works on approximate Voronoi cells [Laa16b, DLdW19, Laa20, DLvW20], for the dual attack no such overview exists, especially for problems with preprocessing. With one of the take-away messages of the approximate Voronoi cell line of work being that primal attacks work well for approximate CVP(P) but scale poorly for BDD(P), one may further wonder if the dual attack suffers the same drawbacks, or if it is perhaps a better solution when trying to solve BDD(P).

In this work we provide an overview of cost estimates for dual algorithms for solving these “classical” closest lattice vector problems. Heuristically we expect to solve the search version of average-case CVPP in time and space \(2^{0.293d + o(d)}\) in the single-target model. The distinguishing version of average-case CVPP, where we wish to distinguish between random targets and targets planted at distance (say) \(0.99 \cdot g_d\) from the lattice, has the same complexity in the single-target model, but can be solved in time and space \(2^{0.195d + o(d)}\) in the multi-target setting, when given a large number of targets from either target distribution. This suggests an inequivalence between distinguishing and searching, as we do not expect a similar improvement in the multi-target setting to hold for search-CVPP. We analyze three slightly different decoders, both for distinguishing and searching, and experimentally obtain concrete cost estimates for the dual attack in dimensions 50 to 80, which confirm our heuristic assumptions, and show that the hidden order terms in the asymptotic estimates are quite small.

Our main take-away message is that the dual attack appears to mirror the approximate Voronoi cell line of work – whereas using approximate Voronoi cells works well for approximate CVP(P) but scales poorly for BDD(P), the dual approach scales well for BDD(P) instances but performs poorly on approximate CVP(P).

Thijs Laarhoven, Michael Walter

On the Hardness of Module-LWE with Binary Secret

Abstract

We prove that the Module Learning With Errors (\(\mathrm {M\text {-}LWE}\)) problem with binary secrets and rank d is at least as hard as the standard version of \(\mathrm {M\text {-}LWE}\) with uniform secret and rank k, where the rank increases from k to \(d \ge (k+1)\log _2 q + \omega (\log _2 n)\), and the Gaussian noise from \(\alpha \) to \(\beta = \alpha \cdot \varTheta (n^2\sqrt{d})\), where n is the ring degree and q the modulus. Our work improves on the recent work by Boudgoust et al. in 2020 by a factor of \(\sqrt{md}\) in the Gaussian noise, where m is the number of given \(\mathrm {M\text {-}LWE}\) samples, when q fulfills some number-theoretic requirements. We use a different approach than Boudgoust et al. to achieve this hardness result by adapting the previous work from Brakerski et al. in 2013 for the Learning With Errors problem to the module setting. The proof applies to cyclotomic fields, but most results hold for a larger class of number fields, and may be of independent interest.

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen

Multi-party Revocation in Sovrin: Performance through Distributed Trust

Abstract

Accumulators provide compact representations of large sets and compact membership witnesses. Besides constant-size witnesses, public-key accumulators provide efficient updates of both the accumulator itself and the witness. However, bilinear group based accumulators come with drawbacks: they require a trusted setup and their performance is not practical for real-world applications with large sets.

In this paper, we introduce multi-party public-key accumulators dubbed dynamic (threshold) secret-shared accumulators. We present an instantiation using bilinear groups having access to more efficient witness generation and update algorithms that utilize the shares of the secret trapdoors sampled by the parties generating the public parameters. Specifically, for the \(q\)-SDH-based accumulators, we provide a maliciously-secure variant sped up by a secure multi-party computation (MPC) protocol (IMACC’19) built on top of SPDZ and a maliciously secure threshold variant built with Shamir secret sharing. For these schemes, a performant proof-of-concept implementation is provided, which substantiates the practicability of public-key accumulators in this setting.

We explore applications of dynamic (threshold) secret-shared accumulators to revocation schemes of group signatures and credentials system. In particular, we consider it as part of Sovrin’s system for anonymous credentials where credentials are issued by the foundation of trusted nodes.

Lukas Helminger, Daniel Kales, Sebastian Ramacher, Roman Walch

Balancing Privacy and Accountability in Blockchain Identity Management

Abstract

The lack of privacy in the first generation of cryptocurrencies such as Bitcoin, Ethereum, etc. is a well known problem in cryptocurrency research. To overcome this problem, several new cryptocurrencies were designed to guarantee transaction privacy and anonymity for their users (examples include ZCash, Monero, etc.).

However, the anonymity provided by such systems appears to be fundamentally problematic in current business and legislation settings: banks and other financial institutions must follow rules such as “Know Your Customer” (KYC), “Anti Money Laundering” (AML), etc. It is also well known that the (alleged or real) anonymity guarantees provided by cryptocurrencies have attracted ill-intentioned individuals to this space, who look at cryptocurrencies as a way of facilitating illegal activities (tax-evasion, ransom-ware, trading of illegal substances, etc.).

The fact that current cryptocurrencies do not comply with such regulations can in part explain why traditional financial institutions have so far been very sceptical of the ongoing cryptocurrency and Blockchain revolution.

In this paper, we propose a novel design principle for identity management in Blockchains. The goal of our design is to maintain privacy, while still allowing compliance with current regulations and preventing exploitations of Blockchain technology for purposes which are incompatible with the social good.

Ivan Damgård, Chaya Ganesh, Hamidreza Khoshakhlagh, Claudio Orlandi, Luisa Siniscalchi

Non-interactive Half-Aggregation of EdDSA and Variants of Schnorr Signatures

Abstract

Schnorr’s signature scheme provides an elegant method to derive signatures with security rooted in the hardness of the discrete logarithm problem, which is a well-studied assumption and conducive to efficient cryptography. However, unlike pairing-based schemes which allow arbitrarily many signatures to be aggregated to a single constant sized signature, achieving significant non-interactive compression for Schnorr signatures and their variants has remained elusive. This work shows how to compress a set of independent EdDSA/Schnorr signatures to roughly half their naive size. Our technique does not employ generic succinct proofs; it is agnostic to both the hash function as well as the specific representation of the group used to instantiate the signature scheme. We demonstrate via an implementation that our aggregation scheme is indeed practical. Additionally, we give strong evidence that achieving better compression would imply proving statements specific to the hash function in Schnorr’s scheme, which would entail significant effort for standardized schemes such as SHA2 in EdDSA. Among the others, our solution has direct applications to compressing Ed25519-based blockchain blocks because transactions are independent and normally users do not interact with each other.

Konstantinos Chalkias, François Garillot, Yashvanth Kondi, Valeria Nikolaenko

A Framework to Optimize Implementations of Matrices

Abstract

In this paper, we propose several reduction rules to optimize the given implementation of a binary matrix over \(\mathbb {F}_{2}\). Moreover, we design a top-layer framework which can make use of the existing search algorithms for solving SLP problems as well as our proposed reduction rules. Thus, efficient implementations of matrices with fewer Xor gates can be expected with the framework. Our framework outperforms algorithms such as Paar1, RPaar1, BP, BFI, RNBP, A1 and A2 when tested on random matrices with various densities and those matrices designed in recent literature. Notably, we find an implementation of AES MixColumns using only 91 Xors, which is currently the shortest implementation to the best of our knowledge.

Da Lin, Zejun Xiang, Xiangyong Zeng, Shasha Zhang

Improvements to RSA Key Generation and CRT on Embedded Devices

Abstract

RSA key generation requires devices to generate large prime numbers. The naïve approach is to generate candidates at random, and then test each one for (probable) primality. However, it is faster to use a sieve method, where the candidates are chosen so as not to be divisible by a list of small prime numbers \(\{p_i\}\).

Sieve methods can be somewhat complex and time-consuming, at least by the standards of embedded and hardware implementations, and they can be tricky to defend against side-channel analysis. Here we describe an improvement on Joye et al.’s sieve based on the Chinese Remainder Theorem (CRT). We also describe a new sieve method using quadratic residuosity which is simpler and faster than previously known methods, and which can produce values in desired RSA parameter ranges such as \((2^{n-1/2}, 2^n)\) with minimal additional work. The same methods can be used to generate strong primes and DSA moduli.

We also demonstrate a technique for RSA private key operations using the Chinese Remainder Theorem (RSA-CRT) without \(q^{-1}\) mod p. This technique also leads to inversion-free batch RSA and inversion-free RSA mod \(p^k q\).

We demonstrate how an embedded device can use our key generation and RSA-CRT techniques to perform RSA efficiently without storing the private key itself: only a symmetric seed and one or two short hints are required.

Mike Hamburg, Mike Tunstall, Qinglai Xiao

On the Cost of ASIC Hardware Crackers: A SHA-1 Case Study

Abstract

In February 2017, the SHA-1 hashing algorithm was practically broken using an identical-prefix collision attack implemented on a GPU cluster, and in January 2020 a chosen-prefix collision was first computed with practical implications on various security protocols. These advances opened the door for several research questions, such as the minimal cost to perform these attacks in practice. In particular, one may wonder what is the best technology for software/hardware cryptanalysis of such primitives. In this paper, we address some of these questions by studying the challenges and costs of building an ASIC cluster for performing attacks against a hash function. Our study takes into account different scenarios and includes two cryptanalytic strategies that can be used to find such collisions: a classical generic birthday search, and a state-of-the-art differential attack using neutral bits for SHA-1.

We show that for generic attacks, GPU and ASIC poses a serious practical threat to primitives with security level \(\sim 64\) bits, with rented GPU a good solution for a one-off attack, and ASICs more efficient if the attack has to be run a few times. ASICs also pose a non-negligible security risk for primitives with 80-bit security. For differential attacks, GPUs (purchased or rented) are often a very cost-effective choice, but ASIC provides an alternative for organizations that can afford the initial cost and look for a compact, energy-efficient, reusable solution. In the case of SHA-1, we show that an ASIC cluster costing a few millions would be able to generate chosen-prefix collisions in a day or even in a minute. This extends the attack surface to TLS and SSH, for which the chosen-prefix collision would need to be generated very quickly.

Anupam Chattopadhyay, Mustafa Khairallah, Gaëtan Leurent, Zakaria Najm, Thomas Peyrin, Vesselin Velichkov

Backmatter