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:
09 February 2022
Eduardo Lopes Cominetti, Marcos Vinicius M. Silva, Marcos A. Simplicio Jr., Harsh Kupwade Patil, Jefferson E. Ricardini
Vehicular-to-Everything (V2X) communications enable vehicles to exchange messages with other entities, including nearby vehicles and pedestrians. V2X is, thus, essential for establishing an Intelligent Transportation System (ITS), where vehicles use information from their surroundings to reduce traffic congestion and improve safety. To avoid abuse, V2X messages should be digitally signed using valid digital certificates. Messages sent by unauthorized entities can then be discarded, while misbehavior can lead to the revocation of the corresponding certificates. One challenge in this scenario is that messages must be verified shortly after arrival (e.g., within centiseconds), whereas vehicles may receive thousands of them per second. To handle this issue, some solutions propose prioritization or delayed-verification mechanisms, while others involve signature schemes that support batch verification. In this manuscript, we discuss two mechanisms that complement such proposals, enabling the authentication of a sequence of messages from the same source with one single signature verification. Our analysis shows that the technique can reduce the number of verified signatures by around 90% for reliable communication channels, and by more than 65% for a maximum packet loss rate of 20%.
Christoph Egger, Russell W. F. Lai, Viktoria Ronge, Ivy K. Y. Woo, Hoover H. F. Yin
In a ring-signature-based anonymous cryptocurrency, signers of a transaction are hidden among a set of potential signers, called a ring, whose size is much smaller than the number of all users. The ring-membership relations specified by the sets of transactions thus induce bipartite transaction graphs, whose distribution is in turn induced by the ring sampler underlying the cryptocurrency.
Since efficient graph analysis could be performed on transaction graphs to potentially deanonymise signers, it is crucial to understand the resistance of (the transaction graphs induced by) a ring sampler against graph analysis. Of particular interest is the class of partitioning ring samplers. Although previous works showed that they provide almost optimal local anonymity, their resistance against global, e.g. graph-based, attacks were unclear.
In this work, we analyse transaction graphs induced by partitioning ring samplers. Specifically, we show (partly analytically and partly empirically) that, somewhat surprisingly, by setting the ring size to be at least logarithmic in the number of users, a graph-analysing adversary is no better than the one that performs random guessing in deanonymisation up to constant factor of 2.
Since efficient graph analysis could be performed on transaction graphs to potentially deanonymise signers, it is crucial to understand the resistance of (the transaction graphs induced by) a ring sampler against graph analysis. Of particular interest is the class of partitioning ring samplers. Although previous works showed that they provide almost optimal local anonymity, their resistance against global, e.g. graph-based, attacks were unclear.
In this work, we analyse transaction graphs induced by partitioning ring samplers. Specifically, we show (partly analytically and partly empirically) that, somewhat surprisingly, by setting the ring size to be at least logarithmic in the number of users, a graph-analysing adversary is no better than the one that performs random guessing in deanonymisation up to constant factor of 2.
Yue Qin, Ruoyu Ding, Chi Cheng, Nina Bindel, Yanbin Pan, Jintai Ding
Key exchange protocols from the learning with errors (LWE) problem share many similarities with the Diffie–Hellman–Merkle (DHM) protocol, which plays a central role in securing our Internet. Therefore, there has been a long time effort in designing authenticated key exchange directly from LWE to mirror the advantages of DHM-based protocols. In this paper, we revisit signal leakage attacks and show that the severity of these attacks against LWE-based (authenticated) key exchange is still underestimated.
In particular, by converting the problem of launching a signal leakage attack into a coding problem, we can significantly reduce the needed number of queries to reveal the secret key. Specifically, for DXL-KE we reduce the queries from 1,266 to only 29, while for DBS-KE, we need only 748 queries, a great improvement over the previous 1,074,434 queries. Moreover, our new view of signals as binary codes enables recognizing vulnerable schemes more easily. As such we completely recover the secret key of a password-based authenticated key exchange scheme by Dabra et al. with only 757 queries and partially reveal the secret used in a two-factor authentication by Wang et al. with only one query. The experimental evaluation supports our theoretical analysis and demonstrates the efficiency and effectiveness of our attacks. Our results caution against underestimating the power of signal leakage attacks as they are applicable even in settings with a very restricted number of interactions between adversary and victim.
Gideon Samid
Thousands of digital money protocols compete for attention; the vast majority of them are a minor variation of the Satoshi Nakamoto 2008 proposal. It is time to extract the underlying principles of the Bitcoin revolution and re-assemble them in a way that preserves its benefits and gets rid of its faults. BitMint*LeVeL is a move in this direction. It upholds the fundamental migration of money from hidden bank accounts to cryptographically protected publicly exposed digital coins; it enables a cyber version of peer-to-peer cash transactions. Bitcoin and its variants rely on a fixed public/private key algorithm. Being 'fixed' turns it into a resting target for advanced cryptanalysis. The LeVeL protocol assigns each coin holder to pick their own public/private key algorithm. An attacker would have to compromise all the algorithms used by all previous coin owners -- a substantial security upgrade relative to Bitcoin. LeVeL applies to self-referential money like Bitcoin or fiat currency, and to other-referential money, serving as a claim check for assets, like gold or fiat currency. Bitcoin decentralization is groundbreaking but it gives too much aid and comfort to wrongdoers. BitMint*LeVeL re-imagines decentralization via the notion of the InterMint: Money is minted by many smoothly interchangeable mints competing for traders. Lastly, BitMint*LeVeL is built on top of the original BitMint protocol which was implemented in the legacy banking system, and thus it offers a smooth migration into cyberspace. 1.2 Billion people around us have no bank account, but do have cell phones. The LeVeL offers social accountability and financial inclusion.
Michael Gruber, Georg Sigl
Protection against physical attacks is a major requirement for cryptographic implementations running on devices which are accessible to an attacker. Side-channel attacks are the most common types of physical attacks, the most frequent side-channel is the device's power consumption. In this work we propose a novel open-source tool called TOFU which synthesizes VCD simulation traces into power traces, with adjustable leakage models. Additionally, we propose a workflow which is only based on open-source tools. The functionality of TOFU and the proposed workflow was verified by a CPA of a AES hardware implementation. We also provide numbers for the required running time of TOFU for a trace synthesis with respect to the according VCD file size. Furthermore, we provide TOFU's source code.
Pierre Karpman, Charlotte Lefevre
We propose new algorithms for solving a class of large-weight syndrome decoding problems in random ternary codes. This is the main generic problem underlying the security of the recent Wave signature scheme (Debris-Alazard et al., 2019), and it has so far received limited attention. At SAC 2019 Bricout et al. proposed a reduction to a binary subset sum problem requiring many solutions, and used it to obtain the fastest known algorithm. However ---as is often the case in the coding theory literature--- its memory cost is proportional to its time cost, which makes it unattractive in most applications.
In this work we propose a range of memory-efficient algorithms for this problem, which describe a near-continuous time-memory tradeoff curve. Those are obtained by using the same reduction as Bricout et al. and carefully instantiating the derived subset sum problem with exhaustive-search algorithms from the literature, in particular dissection (Dinur et al., 2012) and dissection in tree (Dinur, 2019). We also spend significant effort adapting those algorithms to decrease their granularity, thereby allowing them to be smoothly used in a syndrome decoding context when not all the solutions to the subset sum problem are required. For a proposed parameter set for Wave, one of our best instantiations is estimated to cost $2^{177}$ bit operations and requiring $2^{88.5}$ bits of storage, while we estimate this to be $2^{152}$ and $2^{144}$ for the best algorithm from Bricout et al..
In this work we propose a range of memory-efficient algorithms for this problem, which describe a near-continuous time-memory tradeoff curve. Those are obtained by using the same reduction as Bricout et al. and carefully instantiating the derived subset sum problem with exhaustive-search algorithms from the literature, in particular dissection (Dinur et al., 2012) and dissection in tree (Dinur, 2019). We also spend significant effort adapting those algorithms to decrease their granularity, thereby allowing them to be smoothly used in a syndrome decoding context when not all the solutions to the subset sum problem are required. For a proposed parameter set for Wave, one of our best instantiations is estimated to cost $2^{177}$ bit operations and requiring $2^{88.5}$ bits of storage, while we estimate this to be $2^{152}$ and $2^{144}$ for the best algorithm from Bricout et al..
Gyu-Chol.Kim, Jae-Yong.Sin, Yong-Bok.Jong
In order to prove the ElGamal CCA (Chosen Ciphertext Attack) security in the random oracle model, it is necessary to use the group (i.e., ICDH group) where ICDH assumption holds. Until now, only bilinear group where ICDH assumption is equivalent to CDH assumption has been known as the ICDH group. In this paper, we introduce another ICDH group in which ICDH assumption holds under the RSA assumption. Based on this group, we propose the CCA secure ElGamal encryption. And we describe the possibility to speed up decryption by reducing CRT (Chinese Remainder Theorem) exponents in CCA secure ElGamal.
Andrei-Alexandru Brebu, Mihai Iacov, Emil Simion
Cloud computing has emerged as a necessity for hosting data on cloud servers so that information can be accessed and shared remotely. It was quickly adopted because it provides quality of service for various remotely available, easy-to-configure, and easy-to- use products, such as IaaS (Infrastructure as a Service) or PaaS (Platform as a Service). However, this new paradigm of data hosting brings new challenges. Some of the challenges related to the issue of security require independent audit services to verify the integrity of cloud-hosted data. With many end users and companies moving from on-premise to cloud models for their business, cloud data security is a critical concept that needs to be managed. First, we identify security requirements. Second, we look at potential solutions to ensure data integrity in cloud storage. Last, we propose a data auditing solution that can be used to detect corrupt data or file anomalies in the storage system.
Brice Colombier, Vlad-Florin Dragoi, Pierre-Louis Cayrel, Vincent Grosso
The NIST standardization process for post-quantum cryptography has been drawing the attention of researchers to the submitted candidates. One direction of research consists in implementing those candidates on embedded systems and that exposes them to physical attacks in return. The Classic McEliece cryptosystem, which is among the four finalists of round 3 in the Key Encapsulation Mechanism category, was recently targeted by a laser fault injection attack leading to message recovery. Regrettably, the attack setting is very restrictive. Indeed, it does not tolerate errors in the faulty syndrome. Moreover, it depends on the very strong attacker model of laser fault injection, and is not applicable to optimised implementations of the algorithm that make optimal usage of the machine words capacity. In this article, we propose a change of attack angle and perform a message-recovery attack that relies on side-channel information only. We improve on the previously published work in several key aspects. First, we show that side-channel information is sufficient to obtain a faulty syndrome in $\N$, as required by the attack. This is done by leveraging classic machine learning techniques that recover the Hamming weight information very accurately. Second, we put forward a computationally-efficient method, based on a simple dot product, to recover the message from the, possibly noisy, syndrome in $\N$. We show that this new method, which additionally leverages existing information-set decoding algorithms from coding theory, is very robust to noise. Finally, we present a countermeasure against the proposed attack.
Dor Salomon, Itamar Levi
Efficient implementations of software masked designs constitute both an important goal and a significant challenge to Side Channel Analysis attack (SCA) security. In this manuscript we discuss the shortfall between generic C implementations and optimized (inline-)assembler versions while providing a large spectrum of efficient and generic implementations, and exemplifying cryptographic algorithms and masking gadgets with reference to the state of the art. We show the prime performance gaps we can expect between different implementations and suggest how to harness the underlying hardware efficiently, a daunting task for any masking-order or masking algorithm (multiplications, refreshing etc.). This paper focuses on implementations targeting wide vector bitsliced designs such as the ISAP algorithm. We explore concrete instances of implementations utilizing processors enabled by wide-vector capability extensions of the Instruction Set Architecture (ISA); namely, the SSE2/3/4.1, AVX-2 and AVX-512 Streaming Single Instruction Multiple Data (SIMD) extensions. These extensions mainly enable efficient memory level parallelism and provide a gradual reduction in computation-time as a function of the level of extensions and the hardware support for instruction-level parallelism. We also evaluate the disparities between $\mathit{generic}$ high-level language masking implementations for optimized (inline) assemblers and conventional single execution path data-path architectures such as the ARM architecture. We underscore the crucial trade-off between state storage in the data-memory as compared to keeping it in the register-file (RF). This relates specifically to masked designs, and is particularly difficult to resolve because it requires inline-assembler manipulations and is not naively supported by compilers. Moreover, as the masking order ($d$) increases and the state gets larger, there must be an increase in data memory access for state handling since the RF is simply not large enough. This requires careful optimization which depends to a considerable extent on the underlying algorithm to implement. We discuss how full utilization of SSE extensions is not always possible; i.e. when $d$ is not a power of two, and pin-point the optimal $d$ values and very sub-optimal values of $d$ which aggressively under-utilize the hardware. More generally, this manuscript presents several different fully generic masked implementations for any order or multiple highly optimized (inline-)assembler instances which are quite generic (for a wide spectrum of ISAs), and provide very specific implementations targeting specific extensions. The goal is to promote open-source availability, research, improvement and implementations relating to SCA security and masked designs. The building blocks and methodologies provided here are portable and can be easily adapted to other algorithms.
Subhra Mazumdar, Sushmita Ruj
Payment Channel Networks or PCNs solve the problem of scalability in Blockchain by executing payments off-chain. Due to a lack of sufficient capacity in the network, high-valued payments are split and routed via multiple paths. Existing multi-path payment protocols either fail to achieve atomicity or are susceptible to wormhole attack. We propose a secure and privacy-preserving atomic multi-path payment protocol CryptoMaze. Our protocol avoids the formation of multiple off-chain contracts on edges shared by the paths routing partial payments. It also guarantees unlinkability between partial payments. We provide a formal definition of the protocol in the Universal Composability framework and analyze the security. We implement CryptoMaze on several instances of Lightning Network and simulated networks. Our protocol requires 11s for routing a payment of 0.04 BTC on a network instance comprising 25600 nodes. The communication cost is less than 1MB in the worst-case. On comparing the performance of CryptoMaze with several state-of-the-art payment protocols, we observed that our protocol outperforms the rest in terms of computational cost and has a feasible communication overhead.
Alexandru Gheorghiu, Tony Metger, Alexander Poremba
Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to be encoded in a quantum state in such a way that the program can be evaluated, but not copied. Many of these cryptographic primitives are two-party protocols, where one party, Bob, has full quantum computational capabilities, and the other party, Alice, is only required to send random BB84 states to Bob. In this work, we show how such protocols can generically be converted to ones where Alice is fully classical, assuming that Bob cannot efficiently solve the LWE problem. In particular, this means that all communication between (classical) Alice and (quantum) Bob is classical, yet they can still make use of cryptographic primitives that would be impossible if both parties were classical. We apply this conversion procedure to obtain quantum cryptographic protocols with classical communication for unclonable encryption, copy-protection, computing on encrypted data, and verifiable blind delegated computation.
The key technical ingredient for our result is a protocol for classically-instructed parallel remote state preparation of BB84 states. This is a multi-round protocol between (classical) Alice and (quantum polynomial-time) Bob that allows Alice to certify that Bob must have prepared $n$ uniformly random BB84 states (up to a change of basis on his space). Furthermore, Alice knows which specific BB84 states Bob has prepared, while Bob himself does not. Hence, the situation at the end of this protocol is (almost) equivalent to one where Alice sent $n$ random BB84 states to Bob. This allows us to replace the step of preparing and sending BB84 states in existing protocols by our remote-state preparation protocol in a generic and modular way.
The key technical ingredient for our result is a protocol for classically-instructed parallel remote state preparation of BB84 states. This is a multi-round protocol between (classical) Alice and (quantum polynomial-time) Bob that allows Alice to certify that Bob must have prepared $n$ uniformly random BB84 states (up to a change of basis on his space). Furthermore, Alice knows which specific BB84 states Bob has prepared, while Bob himself does not. Hence, the situation at the end of this protocol is (almost) equivalent to one where Alice sent $n$ random BB84 states to Bob. This allows us to replace the step of preparing and sending BB84 states in existing protocols by our remote-state preparation protocol in a generic and modular way.
Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, Adi Serendinschi
Consider a non-synchronous distributed protocol whose processes solve a decision task by (1) starting with their input values, (2) communicating with each other without synchrony, and (3) producing admissible output values despite arbitrary (Byzantine) failures.
Examples of such tasks are broad and range from consensus to reliable broadcast to state machine replication.
Unfortunately, it has been known that such distributed protocols cannot ensure safety as soon as more than $t_0$ processes fail.
By contrast, only recently did the community discover that some of these distributed protocols can be made accountable by ensuring that correct processes irrevocably detect at least $t_0 + 1$ faulty processes responsible for any safety violation. This realization is particularly surprising (and positive) given that accountability is a powerful tool to mitigate safety violations in distributed protocols. Indeed, exposing crimes and introducing punishments naturally incentivize exemplarity.
In this paper, we propose a generic transformation of any distributed protocol that solves a decision task into its accountable version. To this end, we first demonstrate that accountability in non-synchronous distributed protocols implies the ability to detect commission faults. Specifically, we show that (1) detections not based on committed commission faults can be wrong (i.e., "false positives''), and (2) (luckily!) whenever safety is violated, "enough'' processes have committed commission faults.
Then, we illustrate why some of these faults, called equivocation faults, are easier to detect than some others, called evasion faults, thus concluding that equivocation faults are preferable causes of safety violations. Finally, we observe that the approach exploited by the well-studied simulation of crash failures on top of Byzantine ones can be slightly modified in order to ensure that the safety of a protocol could only be violated due to equivocation faults. Hence, we base the transformation on the aforementioned approach. Our transformation increases the communication and message complexities of the original distributed protocol by a quadratic multiplicative factor.
By contrast, only recently did the community discover that some of these distributed protocols can be made accountable by ensuring that correct processes irrevocably detect at least $t_0 + 1$ faulty processes responsible for any safety violation. This realization is particularly surprising (and positive) given that accountability is a powerful tool to mitigate safety violations in distributed protocols. Indeed, exposing crimes and introducing punishments naturally incentivize exemplarity.
In this paper, we propose a generic transformation of any distributed protocol that solves a decision task into its accountable version. To this end, we first demonstrate that accountability in non-synchronous distributed protocols implies the ability to detect commission faults. Specifically, we show that (1) detections not based on committed commission faults can be wrong (i.e., "false positives''), and (2) (luckily!) whenever safety is violated, "enough'' processes have committed commission faults.
Then, we illustrate why some of these faults, called equivocation faults, are easier to detect than some others, called evasion faults, thus concluding that equivocation faults are preferable causes of safety violations. Finally, we observe that the approach exploited by the well-studied simulation of crash failures on top of Byzantine ones can be slightly modified in order to ensure that the safety of a protocol could only be violated due to equivocation faults. Hence, we base the transformation on the aforementioned approach. Our transformation increases the communication and message complexities of the original distributed protocol by a quadratic multiplicative factor.
Florette Martinez
Trifork is a family of pseudo-random number generators described in 2010 by Orue et al. It is based on Lagged Fibonacci Generators and has been claimed as cryptographically secure. In 2017 was presented a new family of lightweight pseudo-random number generators: Arrow. These generators are based on the same techniques as Trifork and designed to be light, fast and secure, so they can allow private communication between resource-constrained devices. The authors based their choices of parameters on NIST standards on lightweight cryptography and claimed these pseudo-random number generators were of cryptographic strength.
We present practical implemented algorithms that reconstruct the internal states of the Arrow generators for different parameters given in the original article. These algorithms enable us to predict all the following outputs and recover the seed. These attacks are all based on a simple guess-and-determine approach which is efficient enough against these generators.
We also present an implemented attack on Trifork, this time using lattice-based techniques. We show it cannot have more than 64 bits of security, hence it is not cryptographically secure.
Ambati Sathvik, Tirunagari Rahul, Anubhab Baksi, Vikramkumar Pudi
In this work, we present a hardware implementation of the lightweight Authenticated Encryption with Associated Data (AEAD) SpoC-128. Designed by AlTawy, Gong, He, Jha, Mandal, Nandi and Rohit; SpoC-128 was submitted to the Lightweight Cryptography (LWC) competition being organised by the National Institute of Standards and Technology (NIST) of the United States Department of Commerce. Our implementation follows the Application Programming Interface (API) specified by the cryptographic engineering research group in the George Mason University (GMU). The source codes are available over the public internet as an open-source project.
Vitaly Kiryukhin
Security of the many keyed hash-based cryptographic constructions (such as HMAC) depends on the fact that the underlying compression function $g(H,M)$ is a pseudorandom function (PRF). This paper presents key-recovery algorithms for 7 rounds (of 12) of Streebog compression function. Two cases were considered, as a secret key can be used: the previous state $H$ or the message block $M$. The proposed methods implicitly show that Streebog compression function has a large security margin as PRF in the above-mentioned secret-key settings.
Zhimei Sui, Joseph K. Liu, Jiangshan Yu, Man Ho Au, Jia Liu
Payment channels have been a promising solution to blockchain scalability. While payment channels for script-empowered blockchains (such as Bitcoin and Ethereum) have been well studied, developing payment channels for scriptless blockchains (such as Monero) is considered challenging. In particular, enabling bidirectional payment on scriptless blockchains remains an open challenge.
This work closes this gap by providing AuxChannel, the first bi-directional payment channel protocol for scriptless blockchains, meaning that building payment channels only requires the support of verifiably encrypted signature (aka adaptor signature) on the underlying blockchain. AuxChannel leverages verifiably encrypted signature to create a commitment for each off-chain payment and deploys a verifiable decentralised key escrow service to resolve dispute. To enable efficient construction of AuxChannel, we introduce a new cryptographic primitive, named Consecutive Verifiably Encrypted Signature (CVES), as a core building block and it can also be of independent interest for other applications. We provide and implement a provably secure instantiation on Schnorr-based CVES. We also provide a formal security analysis on the security of the proposed AuxChannel.
08 February 2022
NTNU, Trondheim, Norway
The Department of Mathematical Sciences at NTNU is looking for a postdoc in public-key cryptography. The position is hosted by Jiaxin Pan. This position is funded by a project from the Research Council of Norway with focus on provable security. Potential topics are, but not limited to, digital signatures, zero-knowledge proofs, and post-quantum cryptography.
The candidate will work on theoretical aspects of public-key cryptography and is expected to publish at IACR conferences (such as Crypto, Eurocrypt, Asiacrypt, etc.) and renowned security conferences (such as IEEE S&P, ACM CCS, etc.). Thus, a track record of publications at these conferences is preferrable for the successful candidate.
Further details: The position holder will participate in many activities of the Cryptology Lab at NTNU which has 9 faculty members working on both applied and theoretical aspects of cryptology. The working place is in Trondheim, Norway. Trondheim is a modern European city with a rich cultural scene. It offers great opportunities for education (including international schools) and possibilities to enjoy nature, culture and family life and has low crime rates and clean air quality.
Application: More details are given here: https://www.jobbnorge.no/en/available-jobs/job/220131/postdoctoral-fellow-in-cryptography. We only accept applications from this jobbnorge.no page.
The deadline for application is the 31st of March, 2022.
Closing date for applications:
Contact: Jiaxin Pan
More information: https://www.jobbnorge.no/en/available-jobs/job/220131/postdoctoral-fellow-in-cryptography
Wollongong, Australia, 13 July - 17 July 2022
Event date: 13 July to 17 July 2022
Submission deadline: 21 February 2022
Notification: 15 April 2022
Submission deadline: 21 February 2022
Notification: 15 April 2022
04 February 2022
Genua, Italien, 6 June 2022
Event date: 6 June 2022
Submission deadline: 4 March 2022
Notification: 8 April 2022
Submission deadline: 4 March 2022
Notification: 8 April 2022