IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
07 March 2022
Nick Frymann, Daniel Gardham, Mark Manulis
The W3C's WebAuthn standard employs digital signatures to offer phishing protection and unlinkability on the web using authenticators which manage keys on behalf of users. This introduces challenges when the account owner wants to delegate certain rights to a proxy user, such as to access their accounts or perform actions on their behalf, as delegation must not undermine the decentralisation, unlinkability, and attestation properties provided by WebAuthn.
We present two approaches, called remote and direct delegation of WebAuthn credentials, maintaining the standard's properties. Both approaches are compatible with Yubico's recent Asynchronous Remote Key Generation (ARKG) primitive proposed for backing up credentials. For remote delegation, the account owner stores delegation credentials at the relying party on behalf of proxies, whereas the direct variant uses a delegation-by-warrant approach, through which the proxy receives delegation credentials from the account owner and presents them later to the relying party. To realise direct delegation we introduce Proxy Signature with Unlinkable Warrants (PSUW), a new proxy signature scheme that extends WebAuthn's unlinkability property to proxy users and can be constructed generically from ARKG.
We discuss an implementation of both delegation approaches, designed to be compatible with WebAuthn, including extensions required for CTAP, and provide a software-based prototype demonstrating overall feasibility. On the performance side, we observe only a minor increase of a few milliseconds in the signing and verification times for delegated WebAuthn credentials based on ARKG and PSUW primitives. We also discuss additional functionality, such as revocation and permissions management, and mention usability considerations.
We present two approaches, called remote and direct delegation of WebAuthn credentials, maintaining the standard's properties. Both approaches are compatible with Yubico's recent Asynchronous Remote Key Generation (ARKG) primitive proposed for backing up credentials. For remote delegation, the account owner stores delegation credentials at the relying party on behalf of proxies, whereas the direct variant uses a delegation-by-warrant approach, through which the proxy receives delegation credentials from the account owner and presents them later to the relying party. To realise direct delegation we introduce Proxy Signature with Unlinkable Warrants (PSUW), a new proxy signature scheme that extends WebAuthn's unlinkability property to proxy users and can be constructed generically from ARKG.
We discuss an implementation of both delegation approaches, designed to be compatible with WebAuthn, including extensions required for CTAP, and provide a software-based prototype demonstrating overall feasibility. On the performance side, we observe only a minor increase of a few milliseconds in the signing and verification times for delegated WebAuthn credentials based on ARKG and PSUW primitives. We also discuss additional functionality, such as revocation and permissions management, and mention usability considerations.
Sílvia Casacuberta, Julia Hesse, Anja Lehmann
In recent years, oblivious pseudorandom functions (OPRFs) have become a ubiquitous primitive used in cryptographic protocols and privacy-preserving technologies. The growing interest in OPRFs, both theoretical and applied, has produced a vast number of different constructions and functionality variations. In this paper, we provide a systematic overview of how to build and use OPRFs. We first categorize existing OPRFs into essentially four families based on their underlying PRF (Naor-Reingold, Dodis-Yampolskiy, Hashed Diffie-Hellman, and generic constructions). This categorization allows us to give a unified presentation of all oblivious evaluation methods in the literature, and to understand which properties OPRFs can (or cannot) have. We further demonstrate the theoretical and practical power of OPRFs by visualizing them in the landscape of cryptographic primitives, and by providing a comprehensive overview of how OPRFs are leveraged for improving the privacy of internet users.
Our work systematizes 15 years of research on OPRFs and provides inspiration for new OPRF constructions and applications thereof.
Jakub Breier, Xiaolu Hou
Fault injection attacks (FIA) are a class of active physical attacks, mostly used for malicious purposes such as extraction of cryptographic keys, privilege escalation, attacks on neural network implementations. There are many techniques that can be used to cause the faults in integrated circuits, many of them coming from the area of failure analysis.
In this paper we tackle the topic of practicality of FIA. We analyze the most commonly used techniques that can be found in the literature, such as voltage/clock glitching, electromagnetic pulses, lasers, and Rowhammer attacks. To summarize, FIA can be mounted on most commonly used architectures from ARM, Intel, AMD, by utilizing injection devices that are often below the thousand dollar mark. Therefore, we believe these attacks can be considered practical in many scenarios, especially when the attacker can physically access the target device.
Irem Keskinkurt Paksoy, Murat Cenk
The Number Theoretic Transform (NTT), Toom-Cook, and
Karatsuba are the most commonly used algorithms for implementing
lattice-based ?nalists of the NIST PQC competition. In this paper, we
propose Toeplitz matrix-vector product (TMVP) based algorithms for
multiplication for all parameter sets of NTRU. We implement the pro-
posed algorithms on ARM Cortex-M4. The results show that TMVP-
based multiplication algorithms using the four-way TMVP formula are
more e?cient for NTRU. Our algorithms outperform the Toom-Cook
method by up to 25.3%, and the NTT method by up to 19.8%. More-
over, our algorithms require less stack space than the others in most
cases. We also observe the impact of these improvements on the overall
performance of NTRU. We speed up the encryption, decryption, en-
capsulation, and decapsulation by up to 13.7%,17.5%,3.5%, and 14.1%,
respectively, compared to state-of-the-art implementation.
Yanhong Fan,Muzhou Li,Chao Niu,Zhenyu Lu,Meiqin Wang
SKINNY-AEAD is one of the second-round candidates of the Lightweight Cryptography Standardization project held by NIST. SKINNY-AEAD M1 is the primary member of six SKINNY-AEAD schemes, while SKINNY-AEAD M3 is another member with a small tag. In the design document, only security analyses of their underlying primitive SKINNY-128-384 are provided. Besides, there are no valid third-party analyses on SKINNY-AEAD M1/M3 according to our knowledge. Therefore, this paper focuses on constructing the first third-party security analyses on them under a nonce-respecting scenario. By taking the encryption mode of SKINNY-AEAD
into consideration and exploiting several properties of SKINNY, we can deduce some necessary constraints on the input and tweakey differences of related-tweakey impossible differential distinguishers. Under these constraints, we can find distinguishers suitable for mounting powerful tweakey recovery attacks. With the help of the automatic searching algorithms based on STP, we find some 14-round distinguishers. Based on one of these distinguishers, we mount a 20-round and an 18-round tweakey recovery attack on SKINNY-AEAD M1/M3. To the best of our knowledge, all these attacks are the best ones so far.
Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai
Is it possible to convert classical reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interactive reductions do carry over. However, when considering quantum auxiliary input, this conversion results in a non-constructive post-quantum reduction that requires duplicating the quantum auxiliary input, which is in general inefficient or even impossible. This violates the win-win premise of provable cryptography: an attack against a cryptographic primitive should lead to an algorithmic advantage.
We initiate the study of constructive quantum reductions and present positive and negative results for converting large classes of classical reductions to the post-quantum setting in a constructive manner. We show that any non-interactive non-adaptive reduction from assumptions with a polynomial solution space (such as decision assumptions) can be made post-quantum constructive. In contrast, assumptions with super-polynomial solution space (such as general search assumptions) cannot be generally converted.
Along the way, we make several additional contributions:
1. We put forth a framework for reductions (or general interaction) with stateful solvers for a computational problem, that may change their internal state between consecutive calls. We show that such solvers can still be utilized. This framework and our results are meaningful even in the classical setting. 2. A consequence of our negative result is that quantum auxiliary input that is useful against a problem with a super-polynomial solution space cannot be generically ``restored'' post-measurement. This shows that the novel rewinding technique of Chiesa et al. (FOCS 2021) is tight in the sense that it cannot be extended beyond a polynomial measurement space.
We initiate the study of constructive quantum reductions and present positive and negative results for converting large classes of classical reductions to the post-quantum setting in a constructive manner. We show that any non-interactive non-adaptive reduction from assumptions with a polynomial solution space (such as decision assumptions) can be made post-quantum constructive. In contrast, assumptions with super-polynomial solution space (such as general search assumptions) cannot be generally converted.
Along the way, we make several additional contributions:
1. We put forth a framework for reductions (or general interaction) with stateful solvers for a computational problem, that may change their internal state between consecutive calls. We show that such solvers can still be utilized. This framework and our results are meaningful even in the classical setting. 2. A consequence of our negative result is that quantum auxiliary input that is useful against a problem with a super-polynomial solution space cannot be generically ``restored'' post-measurement. This shows that the novel rewinding technique of Chiesa et al. (FOCS 2021) is tight in the sense that it cannot be extended beyond a polynomial measurement space.
Yi Deng, Shunli Ma, Xinxuan Zhang, Hailong Wang, Xuyang Song, Xiang Xie
Threshold Signatures allow $n$ parties to share the ability of issuing digital signatures so that any coalition of size at least $t+1$ can sign, whereas groups of $t$ or fewer players cannot. The currently known class-group-based threshold ECDSA constructions are either inefficient (requiring parallel-repetition of the underlying zero knowledge proof with small challenge space) or requiring rather non-standard low order assumption. In this paper, we present efficient threshold ECDSA protocols from encryption schemes based on class groups with neither assuming the low order assumption nor parallel repeating the underlying zero knowledge proof, yielding a significant efficiency improvement in the key generation over previous constructions.
Along the way we introduce a new notion of promise $\Sigma$-protocol that satisfies only a weaker soundness called promise extractability. An accepting promise $\Sigma$-proof for statements related to class-group-based encryptions does not establish the truth of the statement but provides security guarantees (promise extractability) that are sufficient for our applications. We also show how to simulate homomorphic operations on a (possibly invalid) class-group-based encryption whose correctness has been proven via our promise $\Sigma$-protocol. We believe that these techniques are of independent interest and applicable to other scenarios where efficient zero knowledge proofs for statements related to class-group is required.
Along the way we introduce a new notion of promise $\Sigma$-protocol that satisfies only a weaker soundness called promise extractability. An accepting promise $\Sigma$-proof for statements related to class-group-based encryptions does not establish the truth of the statement but provides security guarantees (promise extractability) that are sufficient for our applications. We also show how to simulate homomorphic operations on a (possibly invalid) class-group-based encryption whose correctness has been proven via our promise $\Sigma$-protocol. We believe that these techniques are of independent interest and applicable to other scenarios where efficient zero knowledge proofs for statements related to class-group is required.
Vasyl Ustimenko
New explicit constructions of infinite families of finite small world graphs of large girth with well defined projective limits which is an infinite tree are described. The applications of these objects to constructions of LDPC codes and cryptographic algorithms are shortly observed.
We define families of homogeneous algebraic graphs of large girth over commutative ring K.
For each commutative integrity ring K with |K|>2 we introduce a family of bipartite homogeneous algebraic graphs of large girth over K
formed by graphs with sets of points and lines isomorphic K^n, n>1 and cycle indicator ≥ 2n+2 such that their projective limit is well defined and isomorphic to an infinite forest.
Alexander Poremba
Quantum information has the property that measurement is an inherently destructive process. This feature is most apparent in the principle of complementarity, which states that mutually incompatible observables cannot be measured at the same time. Recent work by Broadbent and Islam (TCC 2020) builds on this aspect of quantum mechanics to realize a cryptographic notion called certified deletion. While this remarkable notion enables a classical verifier to be convinced that a (private-key) quantum ciphertext has been deleted by an untrusted party, it offers no additional layer of functionality.
In this work, we augment the proof-of-deletion paradigm with fully homomorphic encryption (FHE). This results in a new and powerful cryptographic notion called fully homomorphic encryption with certified deletion -- an interactive protocol which enables an untrusted quantum server to compute on encrypted data and, if requested, to simultaneously prove data deletion to a client. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors (LWE) distribution in the form of a quantum state was deleted. We introduce an encoding based on Gaussian coset states which is highly generic and suggests that essentially any LWE-based cryptographic primitive admits a classically-verifiable quantum proof of deletion.
As an application of our protocol, we construct a Dual-Regev public-key encryption scheme with certified deletion, which we then extend towards a (leveled) FHE scheme of the same type. In terms of security, we distinguish between two types of attack scenarios: a semi-honest adversary that follows the protocol exactly, and a fully malicious adversary that is allowed to deviate arbitrarily from the protocol. In the former case, we achieve indistinguishable ciphertexts, even if the secret key is later revealed after deletion has taken place. In the latter case, we provide entropic uncertainty relations for Gaussian cosets which limit the adversary's ability to guess the delegated ciphertext once deletion has taken place. Our results enable a form of everlasting cryptography and give rise to new privacy-preserving quantum cloud applications, such as private machine learning on encrypted data with certified data deletion.
In this work, we augment the proof-of-deletion paradigm with fully homomorphic encryption (FHE). This results in a new and powerful cryptographic notion called fully homomorphic encryption with certified deletion -- an interactive protocol which enables an untrusted quantum server to compute on encrypted data and, if requested, to simultaneously prove data deletion to a client. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors (LWE) distribution in the form of a quantum state was deleted. We introduce an encoding based on Gaussian coset states which is highly generic and suggests that essentially any LWE-based cryptographic primitive admits a classically-verifiable quantum proof of deletion.
As an application of our protocol, we construct a Dual-Regev public-key encryption scheme with certified deletion, which we then extend towards a (leveled) FHE scheme of the same type. In terms of security, we distinguish between two types of attack scenarios: a semi-honest adversary that follows the protocol exactly, and a fully malicious adversary that is allowed to deviate arbitrarily from the protocol. In the former case, we achieve indistinguishable ciphertexts, even if the secret key is later revealed after deletion has taken place. In the latter case, we provide entropic uncertainty relations for Gaussian cosets which limit the adversary's ability to guess the delegated ciphertext once deletion has taken place. Our results enable a form of everlasting cryptography and give rise to new privacy-preserving quantum cloud applications, such as private machine learning on encrypted data with certified data deletion.
Saikrishna Badrinarayanan, Ranjit Kumaresan, Mihai Christodorescu, Vinjith Nagaraja, Karan Patel, Srinivasan Raghuraman, Peter Rindal, Wei Sun, Minghua Xu
Motivated by the recent advances in practical secure computation, we design
and implement a framework for scaling solutions for the problem of private set
intersection (PSI) into the realm of big data. A protocol for PSI enables two
parties each holding a set of elements to jointly compute the intersection of
these sets without revealing the elements that are not in the intersection.
Following a long line of research, recent protocols for PSI only have $\approx
5\times$ computation and communication overhead over an insecure set
intersection. However, this performance is typically demonstrated for set sizes
in the order of ten million. In this work, we aim to scale these protocols to
efficiently handle set sizes of one billion elements or more.
We achieve this via a careful application of a binning approach that enables parallelizing any arbitrary PSI protocol. Building on this idea, we designed and implemented a framework that takes a pair of PSI executables (i.e., for each of the two parties) that typically works for million-sized sets, and then scales it to billion-sized sets (and beyond). For example, our framework can perform a join of billion-sized sets in 83 minutes compared to 2000 minutes of Pinkas et al. (ACM TPS 2018), an improvement of $25\times$. Furthermore, we present an end-to-end Spark application where two enterprises, each possessing private databases, can perform a restricted class of database join operations (specifically, join operations with only an on clause which is a conjunction of equality checks involving attributes from both parties, followed by a where clause which can be split into conjunctive clauses where each conjunction is a function of a single table) without revealing any data that is not part of the output.
We achieve this via a careful application of a binning approach that enables parallelizing any arbitrary PSI protocol. Building on this idea, we designed and implemented a framework that takes a pair of PSI executables (i.e., for each of the two parties) that typically works for million-sized sets, and then scales it to billion-sized sets (and beyond). For example, our framework can perform a join of billion-sized sets in 83 minutes compared to 2000 minutes of Pinkas et al. (ACM TPS 2018), an improvement of $25\times$. Furthermore, we present an end-to-end Spark application where two enterprises, each possessing private databases, can perform a restricted class of database join operations (specifically, join operations with only an on clause which is a conjunction of equality checks involving attributes from both parties, followed by a where clause which can be split into conjunctive clauses where each conjunction is a function of a single table) without revealing any data that is not part of the output.
Ivan Damgård, Divya Ravi, Luisa Siniscalchi, Sophia Yakoubov
In this paper we consider two-round secure computation protocols which use different communication channels in different rounds: namely, protocols where broadcast is available in neither round, both rounds, only the first round, or only the second round. The prior works of Cohen, Garay and Zikas (Eurocrypt 2020) and Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021) give tight characterizations of which security guarantees are achievable for various thresholds in each of the communication structures.
In this paper, we determine what is possible in the honest majority setting without a PKI, closing a question left open by Damgård et al. We show that without a PKI, having an honest majority does not make it possible to achieve stronger security guarantees compared to the dishonest majority setting. However, if two thirds of the parties are guaranteed to be honest, identifiable abort is additionally achievable using broadcast only in the second round.
We use fundamentally different techniques from the previous works in order to avoid relying on private communication in the first round when a PKI is not available, since assuming such private channels without the availability of public encryption keys is unrealistic. We also show that, somewhat surprisingly, the availability of private channels in the first round does not enable stronger security guarantees unless the corruption threshold is one. In that case, prior work has shown that with private channels in the first round, guaranteed output delivery is always achievable; we show that without these channels, fairness is unachievable even with broadcast in both rounds, and unanimous abort is unachievable without broadcast in the second round.
In this paper, we determine what is possible in the honest majority setting without a PKI, closing a question left open by Damgård et al. We show that without a PKI, having an honest majority does not make it possible to achieve stronger security guarantees compared to the dishonest majority setting. However, if two thirds of the parties are guaranteed to be honest, identifiable abort is additionally achievable using broadcast only in the second round.
We use fundamentally different techniques from the previous works in order to avoid relying on private communication in the first round when a PKI is not available, since assuming such private channels without the availability of public encryption keys is unrealistic. We also show that, somewhat surprisingly, the availability of private channels in the first round does not enable stronger security guarantees unless the corruption threshold is one. In that case, prior work has shown that with private channels in the first round, guaranteed output delivery is always achievable; we show that without these channels, fairness is unachievable even with broadcast in both rounds, and unanimous abort is unachievable without broadcast in the second round.
Michael Amar, Amit Kama, Kang Wang, Yossi Oren
The cloud-based Internet of Things (IoT) creates opportunities for more direct integration of the physical world and computer-based systems, allowing advanced applications based on sensing, analyzing and controlling the physical world.
IoT deployments, however, are at a particular risk of counterfeiting, through which an adversary can corrupt the entire ecosystem. Therefore, entity authentication of edge devices is considered an essential part of the security of IoT systems.
A recent paper of Farha et al. suggested an entity authentication scheme suitable for low-resource IoT edge devices, which relies on SRAM-based physically unclonable functions (PUFs). In this paper we analyze this scheme. We show that, while it claims to offer strong PUF functionality, the scheme creates only a weak PUF: an active attacker can completely read out the secret PUF response of the edge device after a very small amount of queries, converting the scheme into a weak PUF scheme which can then be counterfeited easily. After analyzing the scheme, we propose an alternative construction for an authentication method based on SRAM-PUF which better protects the secret SRAM startup state.
A recent paper of Farha et al. suggested an entity authentication scheme suitable for low-resource IoT edge devices, which relies on SRAM-based physically unclonable functions (PUFs). In this paper we analyze this scheme. We show that, while it claims to offer strong PUF functionality, the scheme creates only a weak PUF: an active attacker can completely read out the secret PUF response of the edge device after a very small amount of queries, converting the scheme into a weak PUF scheme which can then be counterfeited easily. After analyzing the scheme, we propose an alternative construction for an authentication method based on SRAM-PUF which better protects the secret SRAM startup state.
Vadim Tsypyschev, Iliya Morgasov
In this article it is investigated security of the cipher feedback mode of operation with regular
external serial re-keying aiming to construct lightweight pseudo-random sequences generator.
For this purpose it was introduced new mode of operation called Multi-key CFB, MCFB, and
was obtained the estimations of provable security of this new mode in the LOR-CPA model.
Besides that. it was obtained counterexample to well-known result of AbdallaBellare about
security of encryption scheme with external re-keying.
Anna Lysyanskaya, Leah Namisa Rosenbloom
Numerous cryptographic applications require efficient non-interactive zero-knowledge proofs of knowledge (NIZK PoK) as a building block. Typically they rely on the Fiat-Shamir heuristic to do so, as security in the random-oracle model is considered good enough in practice. However, there is a troubling disconnect between the stand-alone security of such a protocol and its security as part of a larger, more complex system where several protocols may be running at the same time. Provable security in the universal composition (UC) model of Canetti is the best guarantee that nothing will go wrong when a system is part of a larger whole. In this paper, we show how to achieve efficient UC-secure NIZK PoK in the global random-oracle model of Canetti, Jain, and Scafuro.
Joachim Neu, Ertem Nusret Tas, David Tse
We present two attacks targeting the Proof-of-Stake (PoS) Ethereum consensus protocol. The first attack suggests a fundamental conceptual incompatibility between PoS and the Greedy Heaviest-Observed Sub-Tree (GHOST) fork choice paradigm employed by PoS Ethereum. In a nutshell, PoS allows an adversary with a vanishing amount of stake to produce an unlimited number of equivocating blocks. While most equivocating blocks will be orphaned, such orphaned `uncle blocks' still influence fork choice under the GHOST paradigm, bestowing upon the adversary devastating control over the canonical chain. While the Latest Message Driven (LMD) aspect of current PoS Ethereum prevents a straightforward application of this attack, our second attack shows how LMD specifically can be exploited to obtain a new variant of the balancing attack that overcomes a recent protocol addition that was intended to mitigate balancing-type attacks. Thus, in its current form, PoS Ethereum without and with LMD is vulnerable to our first and second attack, respectively.
Aaron Feickert, Aram Jivanyan
In privacy-preserving transaction protocols, confidential asset designs permit transfer of quantities of distinct asset types in a way that obscures their types and values. Spark is a protocol that provides flexible privacy properties relating to addressing, transaction sources and recipients, and value transfer; however, it does not natively support the use of multiple confidential asset types. Here we describe Spats, a new design for confidential assets compatible with Spark that focuses on efficient and modular implementation. It does so by extending coin value commitments to bind and mask an asset type, and asserting in zero knowledge that this type is maintained throughout transactions. We describe the cryptographic components and changes to the Spark protocol necessary for the design of Spats.
Simin Ghesmati, Walid Fdhila, Edgar Weippl
This paper studies users’ privacy perceptions of UTXO-based blockchains such as Bitcoin.
In particular, it elaborates -- based on interviews and questionnaires -- on a mental model about employing privacy-preserving techniques when doing blockchain transactions. Additionally, it evaluates users' awareness of blockchain privacy issues and examines their preferences towards existing privacy-enhancing solutions, i.e., add-on techniques to Bitcoin versus built-in techniques in privacy coins. Using Bitcoin as an example, we shed light on existing discrepancies between users' privacy perceptions and preferences and current implementations.
Csanád Bertók, Andrea Huszti, Szabolcs Kovács, Norbert Oláh
One of the most significant challenges is the secure user authentication. If it becomes breached, confidentiality and integrity of the data or services may be compromised. The most widespread solution for entity authentication is the password-based scheme. It is easy to use and deploy. During password registration typically users create or activate their account along with their password through their verification email, and service providers are authenticated based on their SSL/TLS certificate. We propose a password registration scheme based on identity-based cryptography, i.e. both the user and the service provider are authenticated by their short-lived identity-based secret key. For secure storage a bilinear map with a salt is applied, therefore in case of an offline attack the adversary is forced to calculate a computationally expensive bilinear map for each password candidate and salt that slows down the attack. New adversarial model with new secure password registration scheme are introduced. We show that the proposed protocol is based on the assumptions that Bilinear Diffie-Hellman problem is computationally infeasible, bilinear map is a one-way function and Mac is existentially unforgeable under an adaptive chosen-message attack.
Simin Ghesmati, Walid Fdhila, Edgar Weippl
Over the past years, the interest in Blockchain technology and its applications has tremendously increased.
This increase of interest was however accompanied by serious threats that raised concerns over user data privacy. Prominent examples include transaction traceability and identification of senders, receivers, and transaction amounts.
This resulted in a multitude of privacy-preserving techniques that offer different guarantees in terms of trust, decentralization, and traceability. CoinJoin is one of the promising techniques that adopts a decentralized approach to achieve privacy on the Unspent Transaction Output (UTXO) based blockchain. Despite the advantages of such a technique in obfuscating user transaction data, making them usable to common users requires considerable development and integration efforts.
This paper provides a comprehensive usability study of three main Bitcoin wallets that integrate the CoinJoin technique, i.e., Joinmarket, Wasabi, and Samourai. The evaluation includes usability and fundamental design criteria to find the ease of use of these wallets \textcolor {black}{based on cognitive walkthrough during coin mixing. The comparison of the wallets with respect to usability and privacy criteria can be used for future evaluation of privacy wallets. The finding of this study can provide better insights for UTXO-based wallet developers.
Vadim Lyubashevsky, Ngoc Khanh Nguyen, Maxime Plancon
We present a much-improved practical protocol, based on the hardness of Module-SIS and Module-LWE problems, for proving knowledge of a short vector $s$ satisfying $As=t\bmod q$. The currently most-efficient technique for constructing such a proof works by showing that the $\ell_\infty$ norm of $s$ is small. It creates a commitment to a polynomial vector $m$ whose CRT coefficients are the coefficients of $s$ and then shows that (1) $A\cdot \mathsf{CRT}(m)=t\bmod\,q$ and (2) in the case that we want to prove that the $\ell_\infty$ norm is at most $1$, the polynomial product $(m - 1)\cdot m\cdot(m+1)$ equals to $0$. While these schemes are already quite good for practical applications, the requirement of using the CRT embedding and only being naturally adapted to proving the $\ell_\infty$-norm, somewhat hinders the efficiency of this approach.
In this work, we show that there is a more direct and more efficient way to prove that the coefficients of $s$ have a small $\ell_2$ norm which does not require an equivocation with the $\ell_\infty$ norm, nor any conversion to the CRT representation. We observe that the inner product between two vectors $ r$ and $s$ can be made to appear as a coefficient of a product (or sum of products) between polynomials which are functions of $r$ and $s$. Thus, by using a polynomial product proof system and hiding all but one coefficient, we are able to prove knowledge of the inner product of two vectors modulo $q$. Using a cheap, approximate range proof, one can then lift the proof to be over $\mathbb{Z}$ instead of $\mathbb{Z}_q$. Our protocols for proving short norms work over all (interesting) polynomial rings, but are particularly efficient for rings like $\mathbb{Z}[X]/(X^n+1)$ in which the function relating the inner product of vectors and polynomial products happens to be a ``nice'' automorphism.
The new proof system can be plugged into constructions of various lattice-based privacy primitives in a black-box manner. As examples, we instantiate a verifiable encryption scheme and a group signature scheme which are more than twice as compact as the previously best solutions.
In this work, we show that there is a more direct and more efficient way to prove that the coefficients of $s$ have a small $\ell_2$ norm which does not require an equivocation with the $\ell_\infty$ norm, nor any conversion to the CRT representation. We observe that the inner product between two vectors $ r$ and $s$ can be made to appear as a coefficient of a product (or sum of products) between polynomials which are functions of $r$ and $s$. Thus, by using a polynomial product proof system and hiding all but one coefficient, we are able to prove knowledge of the inner product of two vectors modulo $q$. Using a cheap, approximate range proof, one can then lift the proof to be over $\mathbb{Z}$ instead of $\mathbb{Z}_q$. Our protocols for proving short norms work over all (interesting) polynomial rings, but are particularly efficient for rings like $\mathbb{Z}[X]/(X^n+1)$ in which the function relating the inner product of vectors and polynomial products happens to be a ``nice'' automorphism.
The new proof system can be plugged into constructions of various lattice-based privacy primitives in a black-box manner. As examples, we instantiate a verifiable encryption scheme and a group signature scheme which are more than twice as compact as the previously best solutions.