info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
[digest] 2022 Week 50
17 views
Skip to first unread message
IACR ePrint Archive
Dec 18, 2022, 3:20:45 PM12/18/22
to
## In this issue
1. [2022/1713] Breaking a Fifth-Order Masked Implementation of ...
2. [2022/1714] Meet-in-the-Middle Preimage Attacks on Sponge-based ...
3. [2022/1715] An Algebraic Attack Against McEliece-like ...
4. [2022/1716] Area-time Efficient Implementation of NIST ...
5. [2022/1717] Scaling Blockchain-Based Tokens with Joint ...
6. [2022/1718] Identity-based Matchmaking Encryption with Stronger ...
7. [2022/1719] Two-Round Concurrent 2PC from Sub-Exponential LWE
8. [2022/1720] Red Team vs. Blue Team: A Real-World Hardware ...
9. [2022/1721] Glimpse: On-Demand, Cross-Chain Communication for ...
10. [2022/1722] On Side-Channel and CVO Attacks against TFHE and FHEW
11. [2022/1723] Asymptotically Optimal Message Dissemination with ...
12. [2022/1724] Formal Analysis of SPDM: Security Protocol and Data ...
13. [2022/1725] A note on SPHINCS+ parameter sets
14. [2022/1726] Optimization for SPHINCS+ using Intel Secure Hash ...
15. [2022/1727] Find Thy Neighbourhood: Privacy-Preserving Local ...
16. [2022/1728] Efficient Zero Knowledge Arguments for Bilinear ...
## 2022/1713
* Title: Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste
* Authors: Elena Dubrova, Kalle Ngo, Joel Gärtner
* [Permalink](https://eprint.iacr.org/2022/1713)
* [Download](https://eprint.iacr.org/2022/1713.pdf)
### Abstract
CRYSTALS-Kyber has been selected by the NIST as a public-key encryption and key encapsulation mechanism to be standardized. It is also included in the NSA's suite of cryptographic algorithms recommended for national security systems. This makes it important to evaluate the resistance of CRYSTALS-Kyber's implementations to side-channel attacks. The unprotected and first-order masked software implementations have been already analysed. In this paper, we present deep learning-based message recovery attacks on the $\omega$-order masked implementations of CRYSTALS-Kyber in ARM Cortex-M4 CPU for $\omega \leq 5$. The main contribution is a new neural network training method called recursive learning. In the attack on an $\omega$-order masked implementation, we start training from an artificially constructed neural network $M^{\omega}$ whose weights are partly copied from a model $M^{\omega-1}$ trained on the $(\omega-1)$-order masked implementation, and then extended to one more share. Such a method allows us to train neural networks that can recover a message bit with the probability above 99% from high-order masked implementations.
## 2022/1714
* Title: Meet-in-the-Middle Preimage Attacks on Sponge-based Hashing
* Authors: Lingyue Qin, Jialiang Hua, Xiaoyang Dong, Hailun Yan, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2022/1714)
* [Download](https://eprint.iacr.org/2022/1714.pdf)
### Abstract
The Meet-in-the-Middle (MitM) attack has been widely applied to preimage attacks on Merkle-Damg{\aa}rd (MD) hashing. In this paper, we introduce a generic framework of the MitM attack on sponge-based hashing. We find certain bit conditions can significantly reduce the diffusion of the unknown bits and lead to longer MitM characteristics. To find good or optimal configurations of MitM attacks, e.g., the bit conditions, the neutral sets, and the matching points, we introduce the
bit-level MILP-based automatic tools on Keccak, Ascon and Xoodyak. To reduce the scale of bit-level models and make them solvable in reasonable time, a series of properties of the targeted hashing are considered in the modelling, such as the linear structure and CP-kernel for Keccak, the Boolean expression of Sbox for Ascon. Finally, we give an improved 4-round preimage attack on Keccak-512/SHA3, and break a nearly 10 years’ cryptanalysis record. We also give the first preimage attacks on 3-/4-round Ascon-XOF and 3-round Xoodyak-XOF.
## 2022/1715
* Title: An Algebraic Attack Against McEliece-like Cryptosystems Based on BCH Codes
* Authors: Freja Elbro, Christian Majenz
* [Permalink](https://eprint.iacr.org/2022/1715)
* [Download](https://eprint.iacr.org/2022/1715.pdf)
### Abstract
We present an algebraic attack on a McEliece-like scheme based on BCH codes (BCH-McEliece), where the Goppa code is replaced by a suitably permuted BCH code. Our attack continues the line of work devising attacks against McEliece-like schemes with Goppa-like codes, with the goal of getting a better understanding of why Goppa codes are so intractable. Our starting point is the work of Faugère, Perret and Portzamparc (Asiacrypt 2014). We take their algebraic model and adapt and improve their attack algorithm so that it can handle BCH-McEliece. We implement the attack and exhibit a parameter range where our attack is practical while generic attacks suggest cryptographic security.
## 2022/1716
* Title: Area-time Efficient Implementation of NIST Lightweight Hash Functions Targeting IoT Applications
* Authors: Safiullah Khan, Wai-Kong Lee, Angshuman Karmakar, Jose Maria Bermudo Mera, Abdul Majeed, Seong Oun Hwang
* [Permalink](https://eprint.iacr.org/2022/1716)
* [Download](https://eprint.iacr.org/2022/1716.pdf)
### Abstract
To mitigate cybersecurity breaches, secure communication is crucial for the Internet of Things (IoT) environment. Data integrity is one of the most significant characteristics of security, which can be achieved by employing cryptographic hash functions. In view of the demand from IoT applications, the National Institute of Standards and Technology (NIST) initiated a standardization process for lightweight hash functions. This work presents field-programmable gate array (FPGA) implementations and carefully worked out optimizations of four Round-3 finalists in the NIST standardization process. A novel compact PHOTON-Beetle implementation is proposed wherein the underlying matrix multiplication is executed in serialized fashion to achieve a small hardware footprint. SPARKLE implementations are carried out by implementing the ARX-box in serialized, parallelized, and hybrid approaches. For Ascon and XOODYAK, the proposed implementations compute certain permutation rounds in one clock cycle in order to explore the trade-off between computation time and hardware area. As a result, this work achieves the smallest hardware footprint for PHOTON-Beetle consuming an area 3.4× smaller than state-of-the-art implementations. Ascon and XOODYAK are implemented in a flexible manner that achieves throughput-to-area (TP/A) ratios 1.8× and 3.9× higher, respectively, compared to implementations found in the literature. In addition, we propose the first FPGA implementations for the SPARKLE hash function. These efficient implementations provide guidelines for choosing a suitable architecture for applications in demand that can be employed in the IoT environment to achieve data integrity for various applications.
## 2022/1717
* Title: Scaling Blockchain-Based Tokens with Joint Cryptographic Accumulators
* Authors: Trevor Miller
* [Permalink](https://eprint.iacr.org/2022/1717)
* [Download](https://eprint.iacr.org/2022/1717.pdf)
### Abstract
As digital tokens on blockchains such as non-fungible tokens (NFTs)
increase in popularity and scale, the existing interfaces (ERC-721,
ERC-20, and many more) are being exposed for being expensive and
not scalable. As a result, tokens are being forced to be implemented
on alternative blockchains where it is cheaper but less secure. To
offer a solution without making security tradeoffs, we propose
using joint cryptographic accumulators (e.g. joint Merkle trees).
We propose a method of creating such joint accumulators in a
decentralized fashion which is secured by the same set of validating
nodes as existing blockchains. Such accumulators allow the tokens
for certain applications to be implemented using up to 99.99% less of
the blockchain’s resources by outsourcing most of the storage and
computational requirements to the users creating the tokens. This
is done without sacrificing permanence and verifiability of these
tokens. This system achieves optimizations mainly by allowing
certain storage of a blockchain to be used in a cross-application
manner, instead of a per-application manner. Additionally, we show
how it can be beneficial in other areas like privacy-preserving
timestamps or shortening file hashes
## 2022/1718
* Title: Identity-based Matchmaking Encryption with Stronger Security and Instantiation on Lattices
* Authors: Yuejun Wang, Baocang Wang, Qiqi Lai, Yu Zhan
* [Permalink](https://eprint.iacr.org/2022/1718)
* [Download](https://eprint.iacr.org/2022/1718.pdf)
### Abstract
An Identity-based matchmaking encryption (IB-ME) scheme proposed at CRYPTO 2019 supports anonymous but authenticated communications in a way that communication parties can both specify the senders or receivers on the fly. IB-ME is easy to be used in several network applications requiring privacy-preserving for its efficient implementation and special syntax. In the literature, IB-ME schemes are built from the variants of Diffie-Hellman assumption and all fail to retain security for quantum attackers. Despite the rigorous security proofs in previous security models, the existing schemes are still possibly vulnerable to some potential neglected attacks. Aiming at the above problems, we provide stronger security definitions considering new attacks to fit real-world scenarios and then propose a generic construction of IB-ME satisfying the new model. Inspired by the prior IB-ME construction of Chen et al., the proposed scheme is constructed by combining 2-level anonymous hierarchical IBE (HIBE) and identity-based signature (IBS) schemes. In order to upgrade lattice-based IB-ME with better efficiency, we additionally improve a lattice IBS, as an independent technical contribution, to shorten its signature and thus reduce the final IB-ME ciphertext size. By combining the improved IBS and any 2-level adaptively-secure lattice-based HIBE with anonymity, we finally obtain the first IB-ME from lattices.
## 2022/1719
* Title: Two-Round Concurrent 2PC from Sub-Exponential LWE
* Authors: Behzad Abdolmaleki, Saikrishna Badrinarayanan, Rex Fernando, Giulio Malavolta, Ahmadreza Rahimi, Amit Sahai
* [Permalink](https://eprint.iacr.org/2022/1719)
* [Download](https://eprint.iacr.org/2022/1719.pdf)
### Abstract
Secure computation is a cornerstone of modern cryptography and a rich body of research is devoted to understanding its round complexity. In this work, we consider two-party computation (2PC) protocols (where both parties receive output) that remain secure in the realistic setting where many instances of the protocol are executed in parallel (concurrent security). We obtain a two-round concurrent-secure 2PC protocol based on a single, standard, post-quantum assumption: The subexponential hardness of the learning-with-errors (LWE) problem. Our protocol is in the plain model, i.e., it has no trusted setup, and it is secure in the super-polynomial simulation framework of Pass (EUROCRYPT 2003). Since two rounds are minimal for (concurrent) 2PC, this work resolves the round complexity of concurrent 2PC from standard assumptions.
As immediate applications, our work establishes feasibility results for interesting cryptographic primitives such as The first two-round password authentication key exchange (PAKE) protocol in the plain model and the first two-round concurrent secure computation protocol for quantum circuits (2PQC).
## 2022/1720
* Title: Red Team vs. Blue Team: A Real-World Hardware Trojan Detection Case Study Across Four Modern CMOS Technology Generations
* Authors: Endres Puschner, Thorben Moos, Steffen Becker, Christian Kison, Amir Moradi, Christof Paar
* [Permalink](https://eprint.iacr.org/2022/1720)
* [Download](https://eprint.iacr.org/2022/1720.pdf)
### Abstract
Verifying the absence of maliciously inserted Trojans in ICs is a crucial task – especially for security-enabled products. Depending on the concrete threat model, different techniques can be applied for this purpose. Assuming that the original IC layout is benign and free of backdoors, the primary security threats are usually identified as the outsourced manufacturing and transportation. To ensure the absence of Trojans in commissioned chips, one straightforward solution is to compare the received semiconductor devices to the design files that were initially submitted to the foundry. Clearly, conducting such a comparison requires advanced laboratory equipment and qualified experts. Nevertheless, the fundamental techniques to detect Trojans which require evident changes to the silicon layout are nowadays well-understood. Despite this, there is a glaring lack of public case studies describing the process in its entirety while making the underlying datasets publicly available. In this work, we aim to improve upon this state of the art by presenting a public and open hardware Trojan detection case study based on four different digital ICs using a Red Team vs. Blue Team approach. Hereby, the Red Team creates small changes acting as surrogates for inserted Trojans in the layouts of 90 nm, 65 nm, 40 nm, and 28 nm ICs. The quest of the Blue Team is to detect all differences between digital layout and manufactured device by means of a GDSII–vs–SEM-image comparison. Can the Blue Team perform this task efficiently? Our results spark optimism for the Trojan seekers and answer common questions about the efficiency of such techniques for relevant IC sizes. Further, they allow to draw conclusions about the impact of technology scaling on the detection performance.
## 2022/1721
* Title: Glimpse: On-Demand, Cross-Chain Communication for Efficient DeFi Applications on Bitcoin-based Blockchains
* Authors: Giulia Scaffino, Lukas Aumayr, Zeta Avarikioti, Matteo Maffei
* [Permalink](https://eprint.iacr.org/2022/1721)
* [Download](https://eprint.iacr.org/2022/1721.pdf)
### Abstract
Cross-chain communication is instrumental in unleashing the full potential of blockchain technologies, as it allows users and developers to exploit the unique design features and the profit opportunities of different existing blockchains. Solutions based on trusted third parties (TTPs) suffer from security and scalability drawbacks; hence, increasing attention has recently been given to decentralized solutions. Lock contracts (e.g., HTLCs and adaptor signatures) and chain relays emerged as the two most prominent attempts to achieve cross-chain communication without TTPs. Lock contracts enable efficient synchronization of single transactions over different chains but are limited in expressiveness as they only support the development of a restricted class of applications (e.g., atomic swaps). On the other hand, chain relays enable the development of arbitrary cross-chain applications but are extremely expensive to operate in practice because they need to synchronize every on-chain transaction, besides assuming a quasi Turing-complete scripting language, which makes them incompatible with Bitcoin-based and scriptless blockchains.
We introduce Glimpse, a novel on-demand cross-chain synchronization primitive, which is both efficient in terms of on-chain costs and computational overhead, and expressive in terms of applications it supports. The key idea of Glimpse is to synchronize transactions on-demand, i.e., only those relevant to realize the cross-chain application of interest. We present a concrete instantiation which is compatible with blockchains featuring a limited scripting language (e.g., Bitcoin-based chains like Liquid), and, yet, can be used as a building block for the design of DeFi applications such as lending, pegs, wrapping/unwrapping of tokens, Proof-of-Burn, and verification of multiple oracle attestations. We formally define and prove Glimpse security in the Universal Composability (UC) framework and conduct an economical security analysis to identify the secure parameter space in the rational setting. Finally, we evaluate the cost of Glimpse for Bitcoin-like chains, showing that verifying a simple transaction has at most 700 bytes of on-chain overhead, resulting in a one-time fee of 3$, only twice as much as a basic Bitcoin transaction.
## 2022/1722
* Title: On Side-Channel and CVO Attacks against TFHE and FHEW
* Authors: Michael Walter
* [Permalink](https://eprint.iacr.org/2022/1722)
* [Download](https://eprint.iacr.org/2022/1722.pdf)
### Abstract
The recent work of Chaturvedi et al. (ePrint 2022/685) claims to observe leakage about secret information in a ciphertext of TFHE through a timing side-channel on the (untrusted) server. In (Chaturvedi et al., ePrint 2022/1563) this is combined with an active attack against TFHE and FHEW. The claims in (Chaturvedi et al., ePrint 2022/685) about the non-trivial leakage from a ciphertext would have far-reaching implications, since the server does not have any secret inputs. In particular, this would mean a weakening of LWE in general,
since an adversary could always simulate a server on which there is side channel leakage.
In this short note, we show that the claims made in the two aforementioned works with regards to the leakage through the timing side channel are false. We demonstrate that the active attack, a standard attack against IND-CPA secure LWE-based encryption, can be mounted just as efficiently without the "side channel information".
## 2022/1723
* Title: Asymptotically Optimal Message Dissemination with Applications to Blockchains
* Authors: Chen-Da Liu-Zhang, Christian Matt, Søren Eller Thomsen
* [Permalink](https://eprint.iacr.org/2022/1723)
* [Download](https://eprint.iacr.org/2022/1723.pdf)
### Abstract
Messages in large-scale networks such as blockchain systems are typically disseminated using flooding protocols, in which parties send the message to a random set of peers until it reaches all parties. Optimizing the communication complexity of such protocols and, in particular, the per-party communication complexity is of primary interest since nodes in a network are often subject to bandwidth constraints. Previous flooding protocols incur a communication complexity of $\Omega(l\cdot n \cdot (\log(n) + \kappa))$ bits to disseminate an $l$-bit message among $n$ parties with security parameter $\kappa$. In this work, we present the first flooding protocols with optimal total communication complexity of $O(l\cdot n)$ bits and per-party communication of $O(l)$ bits. We further show how our protocols can be instantiated provably securely in proof-of-stake blockchains.
To demonstrate that one of our new protocols is not only asymptotically optimal but also practical, we perform several probabilistic simulations to estimate the concrete complexity for given parameters. Our simulations show that our protocol significantly improves the per-party communication complexity over the state-of-the-art for practical parameters. Hence, for given bandwidth constraints, our results allow to, e.g., increase the block size, improving the overall throughput of the blockchain.
## 2022/1724
* Title: Formal Analysis of SPDM: Security Protocol and Data Model version 1.2
* Authors: Cas Cremers, Alexander Dax, Aurora Naska
* [Permalink](https://eprint.iacr.org/2022/1724)
* [Download](https://eprint.iacr.org/2022/1724.pdf)
### Abstract
DMTF is a standards organization by major industry players in IT infrastructure including AMD, Alibaba, Broadcom, Cisco, Dell, Google, Huawei, IBM, Intel, Lenovo, and NVIDIA, which aims to enable interoperability, e.g., including cloud, virtualization, network, servers and storage. It is currently standardizing a security protocol called SPDM, which aims to secure communication over the wire and to enable device attestation, notably also explicitly catering for communicating hardware components.
The SPDM protocol inherits requirements and design ideas from IETF's TLS 1.3. However, its state machines and transcript handling are substantially different and more complex. While architecture, specification, and open-source libraries of the current versions of SPDM are publicly available, these include no significant security analysis of any kind.
In this work we develop the first formal model of the SPDM protocol, notably of the current version 1.2.1, and formally analyze its main security properties.
## 2022/1725
* Title: A note on SPHINCS+ parameter sets
* Authors: Stefan Kölbl
* [Permalink](https://eprint.iacr.org/2022/1725)
* [Download](https://eprint.iacr.org/2022/1725.pdf)
### Abstract
In this note, we discuss using parameter sets for SPHINCS+ which support a smaller number of signatures than the $2^{64}$ target. This includes a larger search through the SPHINCS+ parameter space, comparing it with the current parameter sets and providing data on how the security degrades if one exceeds the limits.
## 2022/1726
* Title: Optimization for SPHINCS+ using Intel Secure Hash Algorithm Extensions
* Authors: Thomas Hanson, Qian Wang, Santosh Ghosh, Fernando Virdia, Anne Reinders, Manoj R. Sastry
* [Permalink](https://eprint.iacr.org/2022/1726)
* [Download](https://eprint.iacr.org/2022/1726.pdf)
### Abstract
SPHINCS+ was selected as a candidate digital signature scheme for standardization by the NIST Post-Quantum Cryptography Standardization Process. It offers security capabilities relying only on the security of cryptographic hash functions. However, it is less efficient than the lattice-based schemes. In this paper, we present an optimized software library for the SPHINCS+ signature scheme, which combines the Intel® Secure Hash Algorithm Extensions (SHA-NI) and AVX2 vector instructions. We obtain significant speed-up of SPHINCS+-128f-simple on both non-optimized (70%) and AVX2 reference implementations (8% -23%) offering 128-bit security.
## 2022/1727
* Title: Find Thy Neighbourhood: Privacy-Preserving Local Clustering
* Authors: Pranav Shriram A, Nishat Koti, Varsha Bhat Kukkala, Arpita Patra, Bhavish Raj Gopal
* [Permalink](https://eprint.iacr.org/2022/1727)
* [Download](https://eprint.iacr.org/2022/1727.pdf)
### Abstract
Identifying a cluster around a seed node in a graph, termed local clustering, finds use in several applications, including fraud detection, targeted advertising, community detection, etc. However, performing local clustering is challenging when the graph is distributed among multiple data owners, which is further aggravated by the privacy concerns that arise in disclosing their view of the graph. This necessitates designing solutions for privacy-preserving local clustering and is addressed for the first time in the literature. We propose using the technique of secure multiparty computation (MPC) to achieve the same. Our local clustering algorithm is based on the heat kernel PageRank (HKPR) metric, which produces the best-known cluster quality. En route to our final solution, we have two important steps: (i) designing data-oblivious equivalent of the state-of-the-art algorithms for computing local clustering and HKPR values, and (ii) compiling the data-oblivious algorithms into its secure realisation via an MPC framework that supports operations over fixed-point arithmetic representation such as multiplication and division. Keeping efficiency in mind for large graphs, we choose the best-known honest-majority 3-party framework of SWIFT (Koti et al., USENIX'21) and enhance it with some of the necessary yet missing primitives, before using it for our purpose. We benchmark the performance of our secure protocols, and the reported run time showcases the practicality of the same. Further, we perform extensive experiments to evaluate the accuracy loss of our protocols. Compared to their cleartext counterparts, we observe that the results are comparable and thus showcase the practicality of the designed protocols.
## 2022/1728
* Title: Efficient Zero Knowledge Arguments for Bilinear Matrix Relations over Finite Fields and Knowledge-Soundness Enhancement via Operations over Extended Field
* Authors: Yuan Tian
* [Permalink](https://eprint.iacr.org/2022/1728)
* [Download](https://eprint.iacr.org/2022/1728.pdf)
### Abstract
In data-intensive private computing applications various relations appear as or can be reduced to various matrix relations. In this paper we investigate two problems related to constructing the zero-knowledge argument (ZKA) protocols for matrix relations.
In the first part, we establish the ZKA for some bilinear matrix relations over Fp. The relations in consideration include (1) general forms of bilinear relations with two witness matrices and some most important special cases. (2) some special forms of bilinear relations with three or four witness matrices. (3) eigenvalue relation. In private computing tasks various important relations are instances or special cases of these relations, e.g., matrix multiplicative relation, inverse relation, similarity relation, some structure decomposition relation and some isomorphic relations for lattices and graphs, etc. Instead of applying the general linearization approach to dealing with these non-linear relations, our approach is matrix-specific. The matrix equation is treated as a tensor identity and probabilistic-equivalent reduction techniques (amortization) are widely applied to reduce non-linear matrix relations to vector nonlinear relations. With the author’s knowledge, currently there are no other systematic works on ZKA for nonlinear matrix relations. Our approach significantly outperforms the general linearization approach in all important performances, e.g., for n-by-t matrix witnesses the required size of c.r.s (only used as the public-key for commitment) can be compressed by 2t times; when n>>t or t>>n the number of rounds, group and field elements in messages are all decreased by ~1/2; when n~t (e.g., square witnesses) they are all decreased by ~1/3.
In the second part, we enhance knowledge-soundness of ZKA for the linear matrix relation over the ground field Fp. By treating the matrix in F_p^(n×td) as a nt-dimensional vector over the d-th extended field over Fp and applying appropriate reductions, we decrease the knowledge-error of the original ZKA over Fp from O(1/p) down to O(1/p^d). This is comparable to the general parallel repetition approach which improves knowledge-error to the same degree, but our approach (matrix-specific) at the same time significantly improves other performances, e.g., smaller-sized c.r.s., fewer rounds and shorter messages.
1. [2022/1713] Breaking a Fifth-Order Masked Implementation of ...
2. [2022/1714] Meet-in-the-Middle Preimage Attacks on Sponge-based ...
3. [2022/1715] An Algebraic Attack Against McEliece-like ...
4. [2022/1716] Area-time Efficient Implementation of NIST ...
5. [2022/1717] Scaling Blockchain-Based Tokens with Joint ...
6. [2022/1718] Identity-based Matchmaking Encryption with Stronger ...
7. [2022/1719] Two-Round Concurrent 2PC from Sub-Exponential LWE
8. [2022/1720] Red Team vs. Blue Team: A Real-World Hardware ...
9. [2022/1721] Glimpse: On-Demand, Cross-Chain Communication for ...
10. [2022/1722] On Side-Channel and CVO Attacks against TFHE and FHEW
11. [2022/1723] Asymptotically Optimal Message Dissemination with ...
12. [2022/1724] Formal Analysis of SPDM: Security Protocol and Data ...
13. [2022/1725] A note on SPHINCS+ parameter sets
14. [2022/1726] Optimization for SPHINCS+ using Intel Secure Hash ...
15. [2022/1727] Find Thy Neighbourhood: Privacy-Preserving Local ...
16. [2022/1728] Efficient Zero Knowledge Arguments for Bilinear ...
## 2022/1713
* Title: Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste
* Authors: Elena Dubrova, Kalle Ngo, Joel Gärtner
* [Permalink](https://eprint.iacr.org/2022/1713)
* [Download](https://eprint.iacr.org/2022/1713.pdf)
### Abstract
CRYSTALS-Kyber has been selected by the NIST as a public-key encryption and key encapsulation mechanism to be standardized. It is also included in the NSA's suite of cryptographic algorithms recommended for national security systems. This makes it important to evaluate the resistance of CRYSTALS-Kyber's implementations to side-channel attacks. The unprotected and first-order masked software implementations have been already analysed. In this paper, we present deep learning-based message recovery attacks on the $\omega$-order masked implementations of CRYSTALS-Kyber in ARM Cortex-M4 CPU for $\omega \leq 5$. The main contribution is a new neural network training method called recursive learning. In the attack on an $\omega$-order masked implementation, we start training from an artificially constructed neural network $M^{\omega}$ whose weights are partly copied from a model $M^{\omega-1}$ trained on the $(\omega-1)$-order masked implementation, and then extended to one more share. Such a method allows us to train neural networks that can recover a message bit with the probability above 99% from high-order masked implementations.
## 2022/1714
* Title: Meet-in-the-Middle Preimage Attacks on Sponge-based Hashing
* Authors: Lingyue Qin, Jialiang Hua, Xiaoyang Dong, Hailun Yan, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2022/1714)
* [Download](https://eprint.iacr.org/2022/1714.pdf)
### Abstract
The Meet-in-the-Middle (MitM) attack has been widely applied to preimage attacks on Merkle-Damg{\aa}rd (MD) hashing. In this paper, we introduce a generic framework of the MitM attack on sponge-based hashing. We find certain bit conditions can significantly reduce the diffusion of the unknown bits and lead to longer MitM characteristics. To find good or optimal configurations of MitM attacks, e.g., the bit conditions, the neutral sets, and the matching points, we introduce the
bit-level MILP-based automatic tools on Keccak, Ascon and Xoodyak. To reduce the scale of bit-level models and make them solvable in reasonable time, a series of properties of the targeted hashing are considered in the modelling, such as the linear structure and CP-kernel for Keccak, the Boolean expression of Sbox for Ascon. Finally, we give an improved 4-round preimage attack on Keccak-512/SHA3, and break a nearly 10 years’ cryptanalysis record. We also give the first preimage attacks on 3-/4-round Ascon-XOF and 3-round Xoodyak-XOF.
## 2022/1715
* Title: An Algebraic Attack Against McEliece-like Cryptosystems Based on BCH Codes
* Authors: Freja Elbro, Christian Majenz
* [Permalink](https://eprint.iacr.org/2022/1715)
* [Download](https://eprint.iacr.org/2022/1715.pdf)
### Abstract
We present an algebraic attack on a McEliece-like scheme based on BCH codes (BCH-McEliece), where the Goppa code is replaced by a suitably permuted BCH code. Our attack continues the line of work devising attacks against McEliece-like schemes with Goppa-like codes, with the goal of getting a better understanding of why Goppa codes are so intractable. Our starting point is the work of Faugère, Perret and Portzamparc (Asiacrypt 2014). We take their algebraic model and adapt and improve their attack algorithm so that it can handle BCH-McEliece. We implement the attack and exhibit a parameter range where our attack is practical while generic attacks suggest cryptographic security.
## 2022/1716
* Title: Area-time Efficient Implementation of NIST Lightweight Hash Functions Targeting IoT Applications
* Authors: Safiullah Khan, Wai-Kong Lee, Angshuman Karmakar, Jose Maria Bermudo Mera, Abdul Majeed, Seong Oun Hwang
* [Permalink](https://eprint.iacr.org/2022/1716)
* [Download](https://eprint.iacr.org/2022/1716.pdf)
### Abstract
To mitigate cybersecurity breaches, secure communication is crucial for the Internet of Things (IoT) environment. Data integrity is one of the most significant characteristics of security, which can be achieved by employing cryptographic hash functions. In view of the demand from IoT applications, the National Institute of Standards and Technology (NIST) initiated a standardization process for lightweight hash functions. This work presents field-programmable gate array (FPGA) implementations and carefully worked out optimizations of four Round-3 finalists in the NIST standardization process. A novel compact PHOTON-Beetle implementation is proposed wherein the underlying matrix multiplication is executed in serialized fashion to achieve a small hardware footprint. SPARKLE implementations are carried out by implementing the ARX-box in serialized, parallelized, and hybrid approaches. For Ascon and XOODYAK, the proposed implementations compute certain permutation rounds in one clock cycle in order to explore the trade-off between computation time and hardware area. As a result, this work achieves the smallest hardware footprint for PHOTON-Beetle consuming an area 3.4× smaller than state-of-the-art implementations. Ascon and XOODYAK are implemented in a flexible manner that achieves throughput-to-area (TP/A) ratios 1.8× and 3.9× higher, respectively, compared to implementations found in the literature. In addition, we propose the first FPGA implementations for the SPARKLE hash function. These efficient implementations provide guidelines for choosing a suitable architecture for applications in demand that can be employed in the IoT environment to achieve data integrity for various applications.
## 2022/1717
* Title: Scaling Blockchain-Based Tokens with Joint Cryptographic Accumulators
* Authors: Trevor Miller
* [Permalink](https://eprint.iacr.org/2022/1717)
* [Download](https://eprint.iacr.org/2022/1717.pdf)
### Abstract
As digital tokens on blockchains such as non-fungible tokens (NFTs)
increase in popularity and scale, the existing interfaces (ERC-721,
ERC-20, and many more) are being exposed for being expensive and
not scalable. As a result, tokens are being forced to be implemented
on alternative blockchains where it is cheaper but less secure. To
offer a solution without making security tradeoffs, we propose
using joint cryptographic accumulators (e.g. joint Merkle trees).
We propose a method of creating such joint accumulators in a
decentralized fashion which is secured by the same set of validating
nodes as existing blockchains. Such accumulators allow the tokens
for certain applications to be implemented using up to 99.99% less of
the blockchain’s resources by outsourcing most of the storage and
computational requirements to the users creating the tokens. This
is done without sacrificing permanence and verifiability of these
tokens. This system achieves optimizations mainly by allowing
certain storage of a blockchain to be used in a cross-application
manner, instead of a per-application manner. Additionally, we show
how it can be beneficial in other areas like privacy-preserving
timestamps or shortening file hashes
## 2022/1718
* Title: Identity-based Matchmaking Encryption with Stronger Security and Instantiation on Lattices
* Authors: Yuejun Wang, Baocang Wang, Qiqi Lai, Yu Zhan
* [Permalink](https://eprint.iacr.org/2022/1718)
* [Download](https://eprint.iacr.org/2022/1718.pdf)
### Abstract
An Identity-based matchmaking encryption (IB-ME) scheme proposed at CRYPTO 2019 supports anonymous but authenticated communications in a way that communication parties can both specify the senders or receivers on the fly. IB-ME is easy to be used in several network applications requiring privacy-preserving for its efficient implementation and special syntax. In the literature, IB-ME schemes are built from the variants of Diffie-Hellman assumption and all fail to retain security for quantum attackers. Despite the rigorous security proofs in previous security models, the existing schemes are still possibly vulnerable to some potential neglected attacks. Aiming at the above problems, we provide stronger security definitions considering new attacks to fit real-world scenarios and then propose a generic construction of IB-ME satisfying the new model. Inspired by the prior IB-ME construction of Chen et al., the proposed scheme is constructed by combining 2-level anonymous hierarchical IBE (HIBE) and identity-based signature (IBS) schemes. In order to upgrade lattice-based IB-ME with better efficiency, we additionally improve a lattice IBS, as an independent technical contribution, to shorten its signature and thus reduce the final IB-ME ciphertext size. By combining the improved IBS and any 2-level adaptively-secure lattice-based HIBE with anonymity, we finally obtain the first IB-ME from lattices.
## 2022/1719
* Title: Two-Round Concurrent 2PC from Sub-Exponential LWE
* Authors: Behzad Abdolmaleki, Saikrishna Badrinarayanan, Rex Fernando, Giulio Malavolta, Ahmadreza Rahimi, Amit Sahai
* [Permalink](https://eprint.iacr.org/2022/1719)
* [Download](https://eprint.iacr.org/2022/1719.pdf)
### Abstract
Secure computation is a cornerstone of modern cryptography and a rich body of research is devoted to understanding its round complexity. In this work, we consider two-party computation (2PC) protocols (where both parties receive output) that remain secure in the realistic setting where many instances of the protocol are executed in parallel (concurrent security). We obtain a two-round concurrent-secure 2PC protocol based on a single, standard, post-quantum assumption: The subexponential hardness of the learning-with-errors (LWE) problem. Our protocol is in the plain model, i.e., it has no trusted setup, and it is secure in the super-polynomial simulation framework of Pass (EUROCRYPT 2003). Since two rounds are minimal for (concurrent) 2PC, this work resolves the round complexity of concurrent 2PC from standard assumptions.
As immediate applications, our work establishes feasibility results for interesting cryptographic primitives such as The first two-round password authentication key exchange (PAKE) protocol in the plain model and the first two-round concurrent secure computation protocol for quantum circuits (2PQC).
## 2022/1720
* Title: Red Team vs. Blue Team: A Real-World Hardware Trojan Detection Case Study Across Four Modern CMOS Technology Generations
* Authors: Endres Puschner, Thorben Moos, Steffen Becker, Christian Kison, Amir Moradi, Christof Paar
* [Permalink](https://eprint.iacr.org/2022/1720)
* [Download](https://eprint.iacr.org/2022/1720.pdf)
### Abstract
Verifying the absence of maliciously inserted Trojans in ICs is a crucial task – especially for security-enabled products. Depending on the concrete threat model, different techniques can be applied for this purpose. Assuming that the original IC layout is benign and free of backdoors, the primary security threats are usually identified as the outsourced manufacturing and transportation. To ensure the absence of Trojans in commissioned chips, one straightforward solution is to compare the received semiconductor devices to the design files that were initially submitted to the foundry. Clearly, conducting such a comparison requires advanced laboratory equipment and qualified experts. Nevertheless, the fundamental techniques to detect Trojans which require evident changes to the silicon layout are nowadays well-understood. Despite this, there is a glaring lack of public case studies describing the process in its entirety while making the underlying datasets publicly available. In this work, we aim to improve upon this state of the art by presenting a public and open hardware Trojan detection case study based on four different digital ICs using a Red Team vs. Blue Team approach. Hereby, the Red Team creates small changes acting as surrogates for inserted Trojans in the layouts of 90 nm, 65 nm, 40 nm, and 28 nm ICs. The quest of the Blue Team is to detect all differences between digital layout and manufactured device by means of a GDSII–vs–SEM-image comparison. Can the Blue Team perform this task efficiently? Our results spark optimism for the Trojan seekers and answer common questions about the efficiency of such techniques for relevant IC sizes. Further, they allow to draw conclusions about the impact of technology scaling on the detection performance.
## 2022/1721
* Title: Glimpse: On-Demand, Cross-Chain Communication for Efficient DeFi Applications on Bitcoin-based Blockchains
* Authors: Giulia Scaffino, Lukas Aumayr, Zeta Avarikioti, Matteo Maffei
* [Permalink](https://eprint.iacr.org/2022/1721)
* [Download](https://eprint.iacr.org/2022/1721.pdf)
### Abstract
Cross-chain communication is instrumental in unleashing the full potential of blockchain technologies, as it allows users and developers to exploit the unique design features and the profit opportunities of different existing blockchains. Solutions based on trusted third parties (TTPs) suffer from security and scalability drawbacks; hence, increasing attention has recently been given to decentralized solutions. Lock contracts (e.g., HTLCs and adaptor signatures) and chain relays emerged as the two most prominent attempts to achieve cross-chain communication without TTPs. Lock contracts enable efficient synchronization of single transactions over different chains but are limited in expressiveness as they only support the development of a restricted class of applications (e.g., atomic swaps). On the other hand, chain relays enable the development of arbitrary cross-chain applications but are extremely expensive to operate in practice because they need to synchronize every on-chain transaction, besides assuming a quasi Turing-complete scripting language, which makes them incompatible with Bitcoin-based and scriptless blockchains.
We introduce Glimpse, a novel on-demand cross-chain synchronization primitive, which is both efficient in terms of on-chain costs and computational overhead, and expressive in terms of applications it supports. The key idea of Glimpse is to synchronize transactions on-demand, i.e., only those relevant to realize the cross-chain application of interest. We present a concrete instantiation which is compatible with blockchains featuring a limited scripting language (e.g., Bitcoin-based chains like Liquid), and, yet, can be used as a building block for the design of DeFi applications such as lending, pegs, wrapping/unwrapping of tokens, Proof-of-Burn, and verification of multiple oracle attestations. We formally define and prove Glimpse security in the Universal Composability (UC) framework and conduct an economical security analysis to identify the secure parameter space in the rational setting. Finally, we evaluate the cost of Glimpse for Bitcoin-like chains, showing that verifying a simple transaction has at most 700 bytes of on-chain overhead, resulting in a one-time fee of 3$, only twice as much as a basic Bitcoin transaction.
## 2022/1722
* Title: On Side-Channel and CVO Attacks against TFHE and FHEW
* Authors: Michael Walter
* [Permalink](https://eprint.iacr.org/2022/1722)
* [Download](https://eprint.iacr.org/2022/1722.pdf)
### Abstract
The recent work of Chaturvedi et al. (ePrint 2022/685) claims to observe leakage about secret information in a ciphertext of TFHE through a timing side-channel on the (untrusted) server. In (Chaturvedi et al., ePrint 2022/1563) this is combined with an active attack against TFHE and FHEW. The claims in (Chaturvedi et al., ePrint 2022/685) about the non-trivial leakage from a ciphertext would have far-reaching implications, since the server does not have any secret inputs. In particular, this would mean a weakening of LWE in general,
since an adversary could always simulate a server on which there is side channel leakage.
In this short note, we show that the claims made in the two aforementioned works with regards to the leakage through the timing side channel are false. We demonstrate that the active attack, a standard attack against IND-CPA secure LWE-based encryption, can be mounted just as efficiently without the "side channel information".
## 2022/1723
* Title: Asymptotically Optimal Message Dissemination with Applications to Blockchains
* Authors: Chen-Da Liu-Zhang, Christian Matt, Søren Eller Thomsen
* [Permalink](https://eprint.iacr.org/2022/1723)
* [Download](https://eprint.iacr.org/2022/1723.pdf)
### Abstract
Messages in large-scale networks such as blockchain systems are typically disseminated using flooding protocols, in which parties send the message to a random set of peers until it reaches all parties. Optimizing the communication complexity of such protocols and, in particular, the per-party communication complexity is of primary interest since nodes in a network are often subject to bandwidth constraints. Previous flooding protocols incur a communication complexity of $\Omega(l\cdot n \cdot (\log(n) + \kappa))$ bits to disseminate an $l$-bit message among $n$ parties with security parameter $\kappa$. In this work, we present the first flooding protocols with optimal total communication complexity of $O(l\cdot n)$ bits and per-party communication of $O(l)$ bits. We further show how our protocols can be instantiated provably securely in proof-of-stake blockchains.
To demonstrate that one of our new protocols is not only asymptotically optimal but also practical, we perform several probabilistic simulations to estimate the concrete complexity for given parameters. Our simulations show that our protocol significantly improves the per-party communication complexity over the state-of-the-art for practical parameters. Hence, for given bandwidth constraints, our results allow to, e.g., increase the block size, improving the overall throughput of the blockchain.
## 2022/1724
* Title: Formal Analysis of SPDM: Security Protocol and Data Model version 1.2
* Authors: Cas Cremers, Alexander Dax, Aurora Naska
* [Permalink](https://eprint.iacr.org/2022/1724)
* [Download](https://eprint.iacr.org/2022/1724.pdf)
### Abstract
DMTF is a standards organization by major industry players in IT infrastructure including AMD, Alibaba, Broadcom, Cisco, Dell, Google, Huawei, IBM, Intel, Lenovo, and NVIDIA, which aims to enable interoperability, e.g., including cloud, virtualization, network, servers and storage. It is currently standardizing a security protocol called SPDM, which aims to secure communication over the wire and to enable device attestation, notably also explicitly catering for communicating hardware components.
The SPDM protocol inherits requirements and design ideas from IETF's TLS 1.3. However, its state machines and transcript handling are substantially different and more complex. While architecture, specification, and open-source libraries of the current versions of SPDM are publicly available, these include no significant security analysis of any kind.
In this work we develop the first formal model of the SPDM protocol, notably of the current version 1.2.1, and formally analyze its main security properties.
## 2022/1725
* Title: A note on SPHINCS+ parameter sets
* Authors: Stefan Kölbl
* [Permalink](https://eprint.iacr.org/2022/1725)
* [Download](https://eprint.iacr.org/2022/1725.pdf)
### Abstract
In this note, we discuss using parameter sets for SPHINCS+ which support a smaller number of signatures than the $2^{64}$ target. This includes a larger search through the SPHINCS+ parameter space, comparing it with the current parameter sets and providing data on how the security degrades if one exceeds the limits.
## 2022/1726
* Title: Optimization for SPHINCS+ using Intel Secure Hash Algorithm Extensions
* Authors: Thomas Hanson, Qian Wang, Santosh Ghosh, Fernando Virdia, Anne Reinders, Manoj R. Sastry
* [Permalink](https://eprint.iacr.org/2022/1726)
* [Download](https://eprint.iacr.org/2022/1726.pdf)
### Abstract
SPHINCS+ was selected as a candidate digital signature scheme for standardization by the NIST Post-Quantum Cryptography Standardization Process. It offers security capabilities relying only on the security of cryptographic hash functions. However, it is less efficient than the lattice-based schemes. In this paper, we present an optimized software library for the SPHINCS+ signature scheme, which combines the Intel® Secure Hash Algorithm Extensions (SHA-NI) and AVX2 vector instructions. We obtain significant speed-up of SPHINCS+-128f-simple on both non-optimized (70%) and AVX2 reference implementations (8% -23%) offering 128-bit security.
## 2022/1727
* Title: Find Thy Neighbourhood: Privacy-Preserving Local Clustering
* Authors: Pranav Shriram A, Nishat Koti, Varsha Bhat Kukkala, Arpita Patra, Bhavish Raj Gopal
* [Permalink](https://eprint.iacr.org/2022/1727)
* [Download](https://eprint.iacr.org/2022/1727.pdf)
### Abstract
Identifying a cluster around a seed node in a graph, termed local clustering, finds use in several applications, including fraud detection, targeted advertising, community detection, etc. However, performing local clustering is challenging when the graph is distributed among multiple data owners, which is further aggravated by the privacy concerns that arise in disclosing their view of the graph. This necessitates designing solutions for privacy-preserving local clustering and is addressed for the first time in the literature. We propose using the technique of secure multiparty computation (MPC) to achieve the same. Our local clustering algorithm is based on the heat kernel PageRank (HKPR) metric, which produces the best-known cluster quality. En route to our final solution, we have two important steps: (i) designing data-oblivious equivalent of the state-of-the-art algorithms for computing local clustering and HKPR values, and (ii) compiling the data-oblivious algorithms into its secure realisation via an MPC framework that supports operations over fixed-point arithmetic representation such as multiplication and division. Keeping efficiency in mind for large graphs, we choose the best-known honest-majority 3-party framework of SWIFT (Koti et al., USENIX'21) and enhance it with some of the necessary yet missing primitives, before using it for our purpose. We benchmark the performance of our secure protocols, and the reported run time showcases the practicality of the same. Further, we perform extensive experiments to evaluate the accuracy loss of our protocols. Compared to their cleartext counterparts, we observe that the results are comparable and thus showcase the practicality of the designed protocols.
## 2022/1728
* Title: Efficient Zero Knowledge Arguments for Bilinear Matrix Relations over Finite Fields and Knowledge-Soundness Enhancement via Operations over Extended Field
* Authors: Yuan Tian
* [Permalink](https://eprint.iacr.org/2022/1728)
* [Download](https://eprint.iacr.org/2022/1728.pdf)
### Abstract
In data-intensive private computing applications various relations appear as or can be reduced to various matrix relations. In this paper we investigate two problems related to constructing the zero-knowledge argument (ZKA) protocols for matrix relations.
In the first part, we establish the ZKA for some bilinear matrix relations over Fp. The relations in consideration include (1) general forms of bilinear relations with two witness matrices and some most important special cases. (2) some special forms of bilinear relations with three or four witness matrices. (3) eigenvalue relation. In private computing tasks various important relations are instances or special cases of these relations, e.g., matrix multiplicative relation, inverse relation, similarity relation, some structure decomposition relation and some isomorphic relations for lattices and graphs, etc. Instead of applying the general linearization approach to dealing with these non-linear relations, our approach is matrix-specific. The matrix equation is treated as a tensor identity and probabilistic-equivalent reduction techniques (amortization) are widely applied to reduce non-linear matrix relations to vector nonlinear relations. With the author’s knowledge, currently there are no other systematic works on ZKA for nonlinear matrix relations. Our approach significantly outperforms the general linearization approach in all important performances, e.g., for n-by-t matrix witnesses the required size of c.r.s (only used as the public-key for commitment) can be compressed by 2t times; when n>>t or t>>n the number of rounds, group and field elements in messages are all decreased by ~1/2; when n~t (e.g., square witnesses) they are all decreased by ~1/3.
In the second part, we enhance knowledge-soundness of ZKA for the linear matrix relation over the ground field Fp. By treating the matrix in F_p^(n×td) as a nt-dimensional vector over the d-th extended field over Fp and applying appropriate reductions, we decrease the knowledge-error of the original ZKA over Fp from O(1/p) down to O(1/p^d). This is comparable to the general parallel repetition approach which improves knowledge-error to the same degree, but our approach (matrix-specific) at the same time significantly improves other performances, e.g., smaller-sized c.r.s., fewer rounds and shorter messages.
0 new messages