IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
20 February 2021
Yunwen Liu, Siwei Sun, Chao Li
ePrint Report
The differential-linear attack, combining the power of the two most effective techniques for symmetric-key cryptanalysis, was pro- posed by Langford and Hellman at CRYPTO 1994. From the exact for- mula for evaluating the bias of a differential-linear distinguisher (JoC 2017), to the differential-linear connectivity table (DLCT) technique for dealing with the dependencies in the switch between the differential and linear parts (EUROCRYPT 2019), and to the improvements in the con- text of cryptanalysis of ARX primitives (CRYPTO 2020), we have seen significant development of the differential-linear attack during the last four years. In this work, we further extend this framework by replacing the differential part of the attack by rotational-xor differentials. Along the way, we establish the theoretical link between the rotational-xor dif- ferential and linear approximations, revealing that it is nontrivial to directly apply the closed formula for the bias of ordinary differential- linear attack to rotational differential-linear cryptanalysis. We then re- visit the rotational cryptanalysis from the perspective of differential- linear cryptanalysis and generalize Morawiecki et al.s technique for an- alyzing Keccak, which leads to a practical method for estimating the bias of a (rotational) differential-linear distinguisher in the special case where the output linear mask is a unit vector. Finally, we apply the rota- tional differential-linear technique to the permutations involved in FRIET, Xoodoo, Alzette, and SipHash. This gives significant improvements over existing cryptanalytic results, or offers explanations for previous exper- imental distinguishers without a theoretical foundation. To confirm the validity of our analysis, all distinguishers with practical complexities are verified experimentally.
Alessandro Chiesa, Eylon Yogev
ePrint Report
Succinct non-interactive arguments (SNARGs) in the random oracle model (ROM) have several attractive features: they are plausibly post-quantum; they can be heuristically instantiated via lightweight cryptography; and they have a transparent (public-coin) parameter setup.
The canonical construction of a SNARG in the ROM is due to Micali (FOCS 1994), who showed how to use a random oracle to compile any probabilistically checkable proof (PCP) with sufficiently-small soundness error into a corresponding SNARG. Yet, while Micali's construction is a seminal result, it has received little attention in terms of analysis in the past 25 years.
In this paper, we observe that prior analyses of the Micali construction are not tight and then present a new analysis that achieves tight security bounds. Our result enables reducing the random oracle's output size, and obtain corresponding savings in concrete argument size.
Departing from prior work, our approach relies on precisely quantifying the cost for an attacker to find several collisions and inversions in the random oracle, and proving that any PCP with small soundness error withstands attackers that succeed in finding a small number of collisions and inversions in a certain tree-based information-theoretic game.
The canonical construction of a SNARG in the ROM is due to Micali (FOCS 1994), who showed how to use a random oracle to compile any probabilistically checkable proof (PCP) with sufficiently-small soundness error into a corresponding SNARG. Yet, while Micali's construction is a seminal result, it has received little attention in terms of analysis in the past 25 years.
In this paper, we observe that prior analyses of the Micali construction are not tight and then present a new analysis that achieves tight security bounds. Our result enables reducing the random oracle's output size, and obtain corresponding savings in concrete argument size.
Departing from prior work, our approach relies on precisely quantifying the cost for an attacker to find several collisions and inversions in the random oracle, and proving that any PCP with small soundness error withstands attackers that succeed in finding a small number of collisions and inversions in a certain tree-based information-theoretic game.
Fukang Liu, Takanori Isobe, Willi Meier, Kosei Sakamoto
ePrint Report
AEGIS-128 and Tiaoxin are two AES-based primitives submitted to the CAESAR competition. Among them, AEGIS-128 has been selected in the final portfolio for high-performance applications, while Tiaoxin is a third-round candidate.
Although both primitives adopt a stream cipher based design, they are quite different from the well-known bit-oriented stream ciphers like Trivium and the Grain family. Their common feature consists in the round update function, where the state is divided into several 128-bit words and each word has the option to pass through an AES round or not. During the 6-year CAESAR competition, it is surprising that for both primitives there is no third-party cryptanalysis of the initialization phase. Due to the similarities in both primitives, we are motivated to investigate whether there is a common way to evaluate the security of their initialization phases.
Our technical contribution is to write the expressions of the internal states in terms of the nonce and the key by treating a 128-bit word as a unit and then carefully study how to simplify these expressions by adding proper conditions. As a result, we found that there are several groups of weak keys with $2^{96}$ keys each in 5-round AEGIS-128 and 8-round Tiaoxin, which allows us to construct integral distinguishers with time complexity $2^{32}$ and data complexity $2^{32}$. Based on the distinguisher, the time complexity to recover the weak key is $2^{72}$ for 5-round AEGIS-128. However, the weak key recovery attack on 8-round Tiaoxin will require the usage of a weak constant occurring with probability $2^{-32}$. We expect that this work can advance the understanding of the designs similar to AEGIS and Tiaoxin.
Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Tom Suad, Mingyuan Wang
ePrint Report
Efficient Reed-Solomon code reconstruction algorithms, for example, by Guruswami and Wootters (STOC--2016), translate into local leakage attacks on Shamir secret-sharing schemes over characteristic-2 fields. However, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO--2018) showed that the Shamir secret sharing scheme over prime-fields is leakage resilient to one-bit local leakage if the reconstruction threshold is roughly 0.87 times the total number of parties. In several application scenarios, like secure multi-party multiplication, the reconstruction threshold must be at most half the number of parties. Furthermore, the number of leakage bits that the Shamir secret sharing scheme is resilient to is also unclear.
Towards this objective, we study the Shamir secret-sharing scheme's leakage-resilience over a prime-field $F$. The parties' secret-shares, which are elements in the finite field $F$, are naturally represented as $\lambda$-bit binary strings representing the elements $\{0,1,\dotsc,p-1\}$. In our leakage model, the adversary can independently probe $m$ bit-locations from each secret share. The inspiration for considering this leakage model stems from the impact that the study of oblivious transfer combiners had on general correlation extraction algorithms, and the significant influence of protecting circuits from probing attacks has on leakage-resilient secure computation.
Consider arbitrary reconstruction threshold $k\geq 2$, physical bit-leakage parameter $m\geq 1$, and the number of parties $n\geq 1$. We prove that Shamir's secret-sharing scheme with random evaluation places is leakage-resilient with high probability when the order of the field $F$ is sufficiently large; ignoring polylogarithmic factors, one needs to ensure that $\log \abs F \geq n/k$. Our result, excluding polylogarithmic factors, states that Shamir's scheme is secure as long as the total amount of leakage $m\cdot n$ is less than the entropy $k\cdot\lambda$ introduced by the Shamir secret-sharing scheme. Note that our result holds even for small constant values of the reconstruction threshold $k$, which is essential to several application scenarios.
To complement this positive result, we present a physical-bit leakage attack for $m=1$ physical bit-leakage from $n=k$ secret shares and any prime-field $F$ satisfying $\abs F=1\mod k$. In particular, there are (roughly) $\abs F^{n-k+1}$ such vulnerable choices for the $n$-tuple of evaluation places. We lower-bound the advantage of this attack for small values of the reconstruction threshold, like $k=2$ and $k=3$, and any $\abs F=1\mod k$. In general, we present a formula calculating our attack's advantage for every $k$ as $\abs F\rightarrow\infty.$
Technically, our positive result relies on Fourier analysis, analytic properties of proper rank-$r$ generalized arithmetic progressions, and B\'ezout's theorem to bound the number of solutions to an equation over finite fields. The analysis of our attack relies on determining the ``discrepancy'' of the Irwin-Hall distribution. A probability distribution's discrepancy is a new property of distributions that our work introduces, which is of potential independent interest.
Towards this objective, we study the Shamir secret-sharing scheme's leakage-resilience over a prime-field $F$. The parties' secret-shares, which are elements in the finite field $F$, are naturally represented as $\lambda$-bit binary strings representing the elements $\{0,1,\dotsc,p-1\}$. In our leakage model, the adversary can independently probe $m$ bit-locations from each secret share. The inspiration for considering this leakage model stems from the impact that the study of oblivious transfer combiners had on general correlation extraction algorithms, and the significant influence of protecting circuits from probing attacks has on leakage-resilient secure computation.
Consider arbitrary reconstruction threshold $k\geq 2$, physical bit-leakage parameter $m\geq 1$, and the number of parties $n\geq 1$. We prove that Shamir's secret-sharing scheme with random evaluation places is leakage-resilient with high probability when the order of the field $F$ is sufficiently large; ignoring polylogarithmic factors, one needs to ensure that $\log \abs F \geq n/k$. Our result, excluding polylogarithmic factors, states that Shamir's scheme is secure as long as the total amount of leakage $m\cdot n$ is less than the entropy $k\cdot\lambda$ introduced by the Shamir secret-sharing scheme. Note that our result holds even for small constant values of the reconstruction threshold $k$, which is essential to several application scenarios.
To complement this positive result, we present a physical-bit leakage attack for $m=1$ physical bit-leakage from $n=k$ secret shares and any prime-field $F$ satisfying $\abs F=1\mod k$. In particular, there are (roughly) $\abs F^{n-k+1}$ such vulnerable choices for the $n$-tuple of evaluation places. We lower-bound the advantage of this attack for small values of the reconstruction threshold, like $k=2$ and $k=3$, and any $\abs F=1\mod k$. In general, we present a formula calculating our attack's advantage for every $k$ as $\abs F\rightarrow\infty.$
Technically, our positive result relies on Fourier analysis, analytic properties of proper rank-$r$ generalized arithmetic progressions, and B\'ezout's theorem to bound the number of solutions to an equation over finite fields. The analysis of our attack relies on determining the ``discrepancy'' of the Irwin-Hall distribution. A probability distribution's discrepancy is a new property of distributions that our work introduces, which is of potential independent interest.
Hwajeong Seo, Pakize Sanal, Wai-Kong Lee, Reza Azarderakhsh
ePrint Report
In this paper, we firstly presented optimized implementations of Montgomery multiplication on 64-bit ARM processors by taking advantages of Karatsuba algorithm and efficient multiplication instruction sets for ARM64 architectures.
The implementation of Montgomery multiplication improved the performance of public key cryptography (e.g. CSIDH, ECC, and RSA) implementations on ARM64 architectures, directly. Last but not least, the performance of Karatsuba algorithm does not ensure the fastest speed record, while it is determined by the clock cycles per multiplication instruction of target ARM architectures. In particular, recent Apple processors based on ARM64 architecture show lower cycles per instruction of multiplication than that of ARM Cortex-A series. For this reason, the schoolbook method shows much better performance than the sophisticated Karatsuba algorithm on Apple processors. With this observation, we can determine the proper approach for multiplication of cryptography library (e.g. MS-SIDH) on Apple processors and ARM Cortex-A processors.
Sravya Yandamuri, Ittai Abraham, Kartik Nayak, Michael K. Reiter
ePrint Report
Agreement protocols for partially synchronous or asynchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, but typically at the cost of increased communication complexity. In this work, we present results that use small trusted hardware without worsening communication complexity assuming the adversary controls a fraction of the network that is less than one-half. Our results include a version of HotStuff that retains linear communication complexity in each view and a version of the VABA protocol with quadratic communication, both leveraging trusted hardware to tolerate a minority of corruptions. Our results use expander graphs to achieve efficient communication in a manner that may be of independent interest.
Dimitris Karakostas, Nikos Karayannidis, Aggelos Kiayias
ePrint Report
Distributed ledgers implement a storage layer, on top of which a shared state is maintained in a decentralized manner. In UTxO-based ledgers, like Bitcoin, the shared state is the set of all unspent outputs (UTxOs), which serve as inputs to future transactions. The continuously increasing size of this shared state will gradually render its maintenance unaffordable. Our work investigates techniques that minimize the shared state of the distributed ledger, i.e., the in-memory UTxO set. To this end, we follow two directions: a) we propose novel transaction optimization techniques to be followed by wallets, so as to create transactions that reduce the shared state cost and b) propose a novel fee scheme that incentivizes the creation of "state-friendly" transactions. We devise an abstract ledger model, expressed via a series of algebraic operators, and define the transaction optimization problem of minimizing the shared state; we also propose a multi-layered algorithm that approximates the optimal solution to this problem. Finally, we define the necessary conditions such that a ledgers fee scheme incentivizes proper state management and propose a state efficient fee function for Bitcoin.
István András Seres, Máté Horváth, Péter Burcsi
ePrint Report
Sequences of consecutive Legendre and Jacobi symbols as pseudorandom bit generators have been proposed for cryptographic use in 1988. Since then they were mostly forgotten in the applications. However, recently revived interest is shown to pseudorandom functions (PRF) based on the Legendre and power residue symbols, due to their extreme efficiency in the multi-party setting and their conjectured post-quantum security. The lack of provable security results hinders the deployment of PRFs based on quadratic and power residue symbols. On the other hand, the security of the Legendre PRF and other variants do not seem to be related to standard cryptographic assumptions, e.g. discrete logarithm or factoring.
Therefore, in this work, we show that key-recovery attacks against the Legendre PRF are equivalent to solving a specific family of multivariate quadratic (MQ) equation system over a finite prime field. This new perspective sheds some light on the complexity of key-recovery attacks against the Legendre PRF. This allows us to take the first steps in settling the provable security of the Legendre PRF and other variants. We do this by conducting extensive algebraic cryptanalysis on the resulting MQ instance. We show how the currently best-known techniques and attacks fall short in solving these sparse quadratic equation systems. Another benefit of viewing the Legendre PRF as an MQ instance is that it facilitates new applications of the Legendre PRF, such as verifiable random function or oblivious (programmable) pseudorandom function. These new applications can be used in cryptographic protocols, such as state of the art proof-of-stake consensus algorithms or private set intersection protocols.
Therefore, in this work, we show that key-recovery attacks against the Legendre PRF are equivalent to solving a specific family of multivariate quadratic (MQ) equation system over a finite prime field. This new perspective sheds some light on the complexity of key-recovery attacks against the Legendre PRF. This allows us to take the first steps in settling the provable security of the Legendre PRF and other variants. We do this by conducting extensive algebraic cryptanalysis on the resulting MQ instance. We show how the currently best-known techniques and attacks fall short in solving these sparse quadratic equation systems. Another benefit of viewing the Legendre PRF as an MQ instance is that it facilitates new applications of the Legendre PRF, such as verifiable random function or oblivious (programmable) pseudorandom function. These new applications can be used in cryptographic protocols, such as state of the art proof-of-stake consensus algorithms or private set intersection protocols.
Jesus Diaz, Anja Lehmann
ePrint Report
Group signatures allow users to create signatures on behalf of a group while remaining anonymous. Such signatures are a powerful tool to realize privacy-preserving data collections, where e.g., sensors, wearables or vehicles can upload authenticated measurements into a data lake. The anonymity protects the users privacy yet enables basic data processing of the uploaded unlinkable information. For many applications, full anonymity is often neither desired nor useful though, and selected parts of the data must eventually be correlated after being uploaded. Current solutions of group signatures do not provide such functionality in a satisfactory way: they either rely on a trusted party to perform opening or linking of signatures, which clearly conflicts with the core privacy goal of group signatures; or require the user to decide upon the linkability of signatures before they are generated.
In this paper we propose a new variant of group signatures that provides linkability in a flexible and user-centric manner. Users and only they can decide before and after signature creation whether they should remain linkable or be correlated. To prevent attacks where a user omits certain signatures when a sequence of events in a certain section (e.g., time frame), should be linked, we further extend this new primitive to allow for sequential link proofs. Such proofs guarantee that the provided sequence of data is not only originating from the same signer, but also occurred in that exact order and contains all of the users signatures within the time frame. We formally define the desired security and privacy properties, propose a provably secure construction based on DL-related assumptions and report on a prototypical implementation of our scheme.
In this paper we propose a new variant of group signatures that provides linkability in a flexible and user-centric manner. Users and only they can decide before and after signature creation whether they should remain linkable or be correlated. To prevent attacks where a user omits certain signatures when a sequence of events in a certain section (e.g., time frame), should be linked, we further extend this new primitive to allow for sequential link proofs. Such proofs guarantee that the provided sequence of data is not only originating from the same signer, but also occurred in that exact order and contains all of the users signatures within the time frame. We formally define the desired security and privacy properties, propose a provably secure construction based on DL-related assumptions and report on a prototypical implementation of our scheme.
Adithya Bhat, Akhil Bandarupalli, Saurabh Bagchi, Aniket Kate, Michael Reiter
ePrint Report
Existing Byzantine fault-tolerant (BFT) state-machine replication (SMR) protocols in the standard (bounded) synchrony and weak synchrony models rely on equivocation detection to ensure safety. To perform a commit (or output a transaction block), this detection inherently requires $O(n^2)$ communication overhead among $n$ nodes and waiting for $O(\Delta)$ time, where $\Delta$ is the worst-case network delay. The quadratic communication overhead limits scalability. Moreover, as the typical network latency $\delta$ tends to be much smaller than $\Delta$, $51\%$ honest-majority (and hence synchronous or weakly synchronous) solutions become slow as compared to $67\%$ honest-majority asynchronous protocols working at network speed.
The observation that SMR commits do not have to be treated separately motivates this work. We propose UCC (Unique Chain Commit) rule, a novel yet simple rule for hash chains where extending a block by including its hash is treated as a vote for the block and all its direct and indirect parents. When a block obtains $f+1$ such votes, where $f$ is the maximum number of faulty nodes in the system, we commit the block and its parents. We use this UCC rule to design Apollo, an SMR protocol with rotating leaders which has a linear communication complexity. Apollo proposes and commits a block every $\delta$ time units with every block having a latency of $(f+1)\delta$. When compared to existing works which use equivocation detection, we improve the optimistic commit latency when $(f+1)\delta<2\Delta$. We prove the security of our protocol in both standard and weak synchrony models. We also implement and compare Apollo with the state of the art protocol, and demonstrate Apollo having commit latencies independent of and less than the $\Delta$ parameter, and also show significant gains in response rates with increasing $n$. For instance, when $n=3$, Apollo can commit blocks of size $2000$ as fast $3$ ms. For $n=65$, Apollo produces $3$x more committed transactions per second than the state of the art Sync HotStuff protocol.
The observation that SMR commits do not have to be treated separately motivates this work. We propose UCC (Unique Chain Commit) rule, a novel yet simple rule for hash chains where extending a block by including its hash is treated as a vote for the block and all its direct and indirect parents. When a block obtains $f+1$ such votes, where $f$ is the maximum number of faulty nodes in the system, we commit the block and its parents. We use this UCC rule to design Apollo, an SMR protocol with rotating leaders which has a linear communication complexity. Apollo proposes and commits a block every $\delta$ time units with every block having a latency of $(f+1)\delta$. When compared to existing works which use equivocation detection, we improve the optimistic commit latency when $(f+1)\delta<2\Delta$. We prove the security of our protocol in both standard and weak synchrony models. We also implement and compare Apollo with the state of the art protocol, and demonstrate Apollo having commit latencies independent of and less than the $\Delta$ parameter, and also show significant gains in response rates with increasing $n$. For instance, when $n=3$, Apollo can commit blocks of size $2000$ as fast $3$ ms. For $n=65$, Apollo produces $3$x more committed transactions per second than the state of the art Sync HotStuff protocol.
An Wang, Yuan Li, Yaoling Ding, Liehuang Zhu, Yongjuan Wang
ePrint Report
Various Artificial Intelligence (AI) techniques are combined with classic side-channel methods to improve the efficiency of attacks. Among them, Genetic Algorithms based Correlation Power Analysis (GA-CPA) is proposed to launch attacks on hardware cryptosystems to extract the secret key efficiently. However, the convergence rate is unsatisfactory due to two problems: individuals of the initial population generally have low fitnesses, and the mutation operation is hard to generate high-quality components. In this paper, we give an analysis framework to solve them.
Firstly, we employ lists of sorted candidate key bytes obtained with CPA to initialize the population with high quality candidates. Secondly, we guide the mutation operation with lists of candidate keys sorted according to fitnesses, which are obtained by exhausting the values of a certain key byte and calculating the corresponding correlation coefficients with the whole key. Thirdly, key enumeration algorithms are utilized to deal with ranked candidates obtained by the last generation of GA-CPA to improve the success rate further. Simulation experimental results show that our method reduces the number of traces by 33.3\% and 43.9\% compared to CPA with key enumeration and GA-CPA respectively when the success rate is fixed to 90\%. Real experiments performed on SAKURA-G confirm that the number of traces required in our method is much less than the numbers of traces required in CPA and GA-CPA. Besides, we adjust our method to deal with DPA contest v1 dataset, and achieve a better result of 40.76 traces than the winning proposal of 42.42 traces. The computation cost of our proposal is nearly 16.7\% of the winner.
Tapas Pal, Ratna Dutta
ePrint Report
The notion of functional encryption (FE) was proposed as a generalization of plain public-key encryption to enable a much more fine-grained handling of encrypted data, with advanced applications such as cloud computing, multi-party computations, obfuscating circuits or Turin machines. While FE for general circuits or Turin machines gives a natural instantiation of the many cryptographic primitives, existing FE schemes are based on indistinguishability obfuscation or multilinear maps which either rely on new computational hardness assumptions or heuristically claimed to be secure. In this work, we present new techniques directly yielding FE for inner product functionality where secret-keys provide access control via polynomial-size bounded-depth circuits. More specifically, we encrypt messages with respect to attributes and embed
policy circuits into secret-keys so that a restricted class of receivers would be able to learn certain property about the messages. Recently, many inner product FE schemes were proposed. However, none of them uses a general circuit as an access structure. Our main contribution is designing the first construction for an attribute-based FE scheme in key-policy
setting for inner products from well-studied Learning With Errors (LWE) assumption. Our construction takes inspiration from the attribute-based encryption of Boneh et al. from Eurocrypt 2014 and the inner product functional encryption of Agrawal et al. from Crypto 2016. The scheme is proved in a stronger setting where the adversary is allowed to ask secret-keys that can decrypt the challenge ciphertext. Doing so requires a careful setting of parameters for handling the noise in ciphertexts to
enable correct decryption. Another main advantage of our scheme is that the size of ciphertexts and secret-keys depends on the depth of the circuits rather than its size. Additionally, we extend our construction in a much desirable multi-input variant where secret-keys are associated with multiple policies subject to different encryption slots. This enhances the applicability of the scheme with finer access control.
Miguel Ambrona
ePrint Report
Attribute-based encryption (ABE) is a cryptographic primitive which supports fine-grained access control on encrypted data, making it an appealing building block for many applications. Pair encodings (Attrapadung, EUROCRYPT 2014) are simple primitives that can be used for constructing fully secure ABE schemes associated to a predicate relative to the encoding.
We propose a generic transformation that takes any pair encoding scheme (PES) for a predicate $P$ and produces a PES for its negated predicate $\bar{P}$ . This construction finally solves a problem that was open since 2015. Our techniques bring new insight to the expressivity and generality of PES and can be of independent interest. We also provide, to the best of our knowledge, the first pair encoding scheme for negated doubly spatial encryption (obtained with our transformation) and explore several other consequences of our results.
Lukas Aumayr, Pedro Moreno-Sanchez, Aniket Kate, Matteo Maffei
ePrint Report
Payment-channel networks (PCN) are the most prominent approach to tackle the scalability issues of current permissionless blockchains. A PCN reduces the load on-chain by allowing arbitrarily many off-chain multi-hop payments (MHP) between any two users connected through a path of payment channels. Unfortunately, current protocols for MHP are far from satisfactory. One round MHP (e.g., Interledger) are insecure as a malicious intermediary can steal the payment funds. Two-round MHP (e.g., Lightning Network (LN)) follow the 2-phase-commit paradigm as in databases to overcome this issue. However, when tied with economical incentives, 2-phase-commit brings other security threats (i.e., wormhole attacks), staggered collateral (i.e., funds are locked for a time proportional to the payment path length) and dependency on specific scripting language functionality (e.g., hash time lock contracts) that hinders a wider deployment in practice.
We present Blitz, a novel MHP protocol that demonstrates for the first time that we can achieve the best of the two worlds: a single round MHP where no malicious intermediary can steal coins. Moreover, Blitz provides privacy for sender and receiver, it is not prone to the wormhole attack and it requires only constant collateral. Additionally, we construct MHP using only digital signatures and a timelock functionality, both available at the core of virtually every cryptocurrency today. We provide the cryptographic details of Blitz and we formally prove its security. Furthermore, our experimental evaluation on an LN snapshot shows that the LN collateral results in between 4x and 33x more unsuccessful payments than the Blitz collateral (both compared to a baseline), reduce the size of the payment contract by 26% and prevent up to 0.3 BTC (3397 USD in October 2020) in fees being stolen over a three day period as it avoids wormhole attacks by design.
We present Blitz, a novel MHP protocol that demonstrates for the first time that we can achieve the best of the two worlds: a single round MHP where no malicious intermediary can steal coins. Moreover, Blitz provides privacy for sender and receiver, it is not prone to the wormhole attack and it requires only constant collateral. Additionally, we construct MHP using only digital signatures and a timelock functionality, both available at the core of virtually every cryptocurrency today. We provide the cryptographic details of Blitz and we formally prove its security. Furthermore, our experimental evaluation on an LN snapshot shows that the LN collateral results in between 4x and 33x more unsuccessful payments than the Blitz collateral (both compared to a baseline), reduce the size of the payment contract by 26% and prevent up to 0.3 BTC (3397 USD in October 2020) in fees being stolen over a three day period as it avoids wormhole attacks by design.
Siwei Chen, Zejun Xiang, Xiangyong Zeng, Shasha Zhang
ePrint Report
In this paper, we compare several non-tight degree evaluation methods i.e., Boura and Canteaut's formula, Carlet's formula as well as Liu's numeric mapping and division property proposed by Todo, and hope to find the best one from these methods for practical applications. Specifically, for the substitution-permutation-network (SPN) ciphers, we first deeply explore the relationships between division property of an Sbox and its algebraic properties (e.g., the algebraic degree of its inverse). Based on these findings, we can prove theoretically that division property is never worse than Boura and Canteaut's and Carlet's formulas, and we also experimentally verified that the division property can indeed give a better bound than the latter two methods. In addition, for the nonlinear feedback shift registers (NFSR) based ciphers, according to the propagation of division property and the core idea of numeric mapping, we give a strict proof that the estimated degree using division property is never greater than that of numeric mapping. Moreover, our experimental results on Trivium and Kreyvium indicate the division property actually derives a much better bound than the numeric mapping. To the best of our knowledge, this is the first time to give a formal discussion on the relationships between division property and other degree evaluation methods, and we present the first theoretical proof and give the experimental verification to illustrate that division property is the optimal one among these methods in terms of the accuracy of the upper bounds on algebraic degree.
Alptekin Küpçü, Reihaneh Safavi-Naini
ePrint Report
Outsourcing computation allows resource limited clients to access computing on demand. Various types of clusters, grids, and clouds, such as Microsofts Azure and Amazons EC2, form todays outsourced computing infrastructure. A basic requirement of outsourcing is providing guarantee that the computation result is correct. We consider an automated and efficient way of achieving assurance where the computation is replicated and outsourced to two contractors by a smart contract that will decide on the correctness of the computation result, by comparing the two received results. We show that all previous incentivized outsourcing protocols with proven correctness fail when automated by a smart contract, because of copy attack where a contractor simply copies the submitted response of the other contractor. We then design an incentive mechanism that uses two lightweight response-checking protocols, and employ monetary reward, fine, and bounty to incentivize correct computation. We use game theory to model and analyze our mechanism, and prove that it has a single Nash equilibrium, corresponding to the contractors strategy of correctly computing the result. Our work provides a foundation for incentivized computation in the smart contract setting and opens new research directions.
Wai-Kong Lee, Hwajeong Seo, Zhenfei Zhang, Seongoun Hwang
ePrint Report
Tensor core is a specially designed hardware included in new NVIDIA GPU chips, aimed at accelerating deep learning applications. With the introduction of tensor core, the matrix multiplication at low precision can be computed much faster than using conventional integer and floating point units in NVIDIA GPU. In the past, applications of tensor core were mainly restricted to machine learning and mixed precision scientific computing. In this paper, we show that for the first time, tensor core can be used to accelerate state-of-the-art lattice-based cryptosystems. In particular, we employed tensor core to accelerate NTRU, one of the finalists in NIST post-quantum standardization. Towards our aim, several parallel algorithms are proposed to allow the tensor core to handle flexible matrix sizes and ephemeral key pair. Experimental results show that the polynomial convolution using tensor core is 2.79× (ntruhps2048509) and 2.72× (ntruhps2048677) faster than the version implemented with conventional integer units of NVIDIA GPU. The proposed tensor core based polynomial convolution technique was applied to NTRU public key scheme (TensorTRU). It achieved 1.94×/1.95× (encryption) and 1.97×/2.02× (decryption) better performance for the two parameter sets, compared to the conventional integer based implementations in GPU. TensorTRU is also more than 20× faster than the reference implementation in CPU and 2× faster than the AVX2 implementation, for both encryption and decryption. To demonstrate the flexibility of the proposed technique, we have extended the implementation to other lattice-based cryptosystems that have a small modulus (LAC and two variant parameter sets in FrodoKEM). Experimental results show that the tensor core based polynomial convolution is flexible and useful in accelerating lattice-based cryptosystems that cannot utilize number theoretic transform in performing polynomial multiplication.
17 February 2021
CRYPTO
The IACR is soliciting for affiliated events to be held in conjunction with Crypto 2021 on Saturday, August 14 and/or Sunday, August 15.
Each such event is expected to provide a forum discussing a specific topic of the broad cryptographic world (theory, practice, implementation, standardizations, etc.). The format of the event (e.g. workshop, tutorial, etc.) is up to the organizers.
Proposals for events should be submitted by email to the Crypto 2021 workshop chair at crypto2021workshopchair@gmail.com by March 15, 2021 (23:59 UTC).
For more details visit https://crypto.iacr.org/2021/affiliated.php
Each such event is expected to provide a forum discussing a specific topic of the broad cryptographic world (theory, practice, implementation, standardizations, etc.). The format of the event (e.g. workshop, tutorial, etc.) is up to the organizers.
Proposals for events should be submitted by email to the Crypto 2021 workshop chair at crypto2021workshopchair@gmail.com by March 15, 2021 (23:59 UTC).
For more details visit https://crypto.iacr.org/2021/affiliated.php
Nishanth Chandran, Nishka Dasgupta, Divya Gupta, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar, Akash Shah
ePrint Report
Multiparty Private Set Intersection (mPSI), enables $n$ parties, each holding private sets (each of size $m$) to compute the intersection of these private sets, without revealing any other information to each other. While several protocols for this task are known, the only concretely efficient protocol is due to the work of Kolesnikov et al. (KMPRT, CCS 2017), who gave a semi-honest secure protocol with communication complexity $\mathcal{O}(nmt\lambda)$, where $t<n$ is the number of corrupt parties and $\lambda$ is the security parameter. In this work, we make the following contributions:
$-$ First, for the natural adversarial setting of semi-honest honest majority (i.e. $t<n/2$), we asymptotically improve upon the above result and provide a concretely efficient protocol with total communication of $\mathcal{O}(nm\lambda)$.
$-$ Second, concretely, our protocol has $6(t+2)/5$ times lesser communication than KMPRT and is upto $5\times$ and $6.2\times$ faster than KMPRT in the LAN and WAN setting even for 15 parties.
$-$ Finally, we introduce and consider two important variants of mPSI - circuit PSI (that allows the parties to compute a function over the intersection set without revealing the intersection itself) and quorum PSI (that allows $P_1$ to learn all the elements in his/her set that are present in at least $k$ other sets) and provide concretely efficient protocols for these variants.
Wei Yu, Guangwu Xu
ePrint Report
Let $E_a/ \mathbb{F}_{2}: y^2+xy=x^3+ax^2+1$ be a Koblitz curve. The window $\tau$-adic non-adjacent form (window $\tau$NAF) is currently the standard representation system to perform scalar multiplications on $E_a/ \mathbb{F}_{2^m}$ utilizing the Frobenius map $\tau$. This work focuses on the pre-computation part of scalar multiplication. We first introduce $\mu\bar{\tau}$-operations where $\mu=(-1)^{1-a}$ and $\bar{\tau}$ is the complex conjugate of $\tau$. Efficient formulas of $\mu\bar{\tau}$-operations are then derived and used in a novel pre-computation scheme. Our pre-computation scheme requires $6${\bf M}$+6${\bf S}, $18${\bf M}$+17${\bf S}, $44${\bf M}$+32${\bf S}, and $88${\bf M}$+62${\bf S} ($a=0$) and $6${\bf M}$+6${\bf S}, $19${\bf M}$+17${\bf S}, $46${\bf M}$+32${\bf S}, and $90${\bf M}$+62${\bf S} ($a=1$) for window $\tau$NAF with widths from $4$ to $7$ respectively. It is about two times faster, compared to the state-of-the-art technique of pre-computation in the literature. The impact of our new efficient pre-computation is also reflected by the significant improvement of scalar multiplication. Traditionally, window $\tau$NAF with width at most $6$ is used to achieve the best scalar multiplication. Because of the dramatic cost reduction of the proposed pre-computation, we are able to increase the width for window $\tau$NAF to $7$ for a better scalar multiplication. This indicates that the pre-computation part becomes more important in performing scalar multiplication. With our efficient pre-computation and the new window width, our scalar multiplication runs in at least 85.2\% the time of Kohel's work (Eurocrypt'2017) combining the best previous pre-computation. Our results push the scalar multiplication of Koblitz curves, a very well-studied and long-standing research area, to a significant new stage.