Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
[digest] 2023 Week 32
17 views
Skip to first unread message
IACR ePrint Archive
Aug 13, 2023, 3:28:39 PM8/13/23
to
## In this issue
1. [2022/1424] DeFi That Defies: Imported Off-Chain Metrics and ...
2. [2023/1191] Attribute-Based Multi-Input FE (and more) for ...
3. [2023/1192] CycleFold: Folding-scheme-based recursive arguments ...
4. [2023/1193] An Anonymous Authenticated Key Agreement Protocol ...
5. [2023/1194] HI-Kyber: A novel high-performance implementation ...
6. [2023/1195] PicoEMP: A Low-Cost EMFI Platform Compared to BBI ...
7. [2023/1196] A New Paradigm for Verifiable Secret Sharing
8. [2023/1197] Towards a Quantum-resistant Weak Verifiable Delay ...
9. [2023/1198] Towards Achieving Provable Side-Channel Security in ...
10. [2023/1199] RSA Blind Signatures with Public Metadata
11. [2023/1200] Shining Light on the Shadow: Full-round Practical ...
12. [2023/1201] Privacy-preserving edit distance computation using ...
13. [2023/1202] Extension of Shannon's theory of ciphers based on ...
14. [2023/1203] Collaborative Privacy-Preserving Analysis of ...
15. [2023/1204] On Fully-Secure Honest Majority MPC without $n^2$ ...
16. [2023/1205] On the security of REDOG
17. [2023/1206] Decentralized Threshold Signatures for Blockchains ...
18. [2023/1207] DeFi Auditing: Mechanisms, Effectiveness, and User ...
19. [2023/1208] Mutator Sets and their Application to Scalable Privacy
20. [2023/1209] Infinite families of minimal binary codes via ...
21. [2023/1210] Decentralized Finance (DeFi): A Survey
22. [2023/1211] Optimal Flexible Consensus and its Application to ...
23. [2023/1212] CLRW1$^{3}$ is not Secure Beyond the Birthday ...
24. [2023/1213] Fallen Sanctuary: A Higher-Order and Leakage- ...
25. [2023/1214] Verifiable Verification in Cryptographic Protocols
26. [2023/1215] Authentica: A Secure Authentication Mechanism using ...
27. [2023/1216] Unlocking the lookup singularity with Lasso
28. [2023/1217] Jolt: SNARKs for Virtual Machines via Lookups
29. [2023/1218] Arke: Scalable and Byzantine Fault Tolerant ...
30. [2023/1219] A Note on “Secure Quantized Training for Deep Learning”
31. [2023/1220] Quasi-linear Masking to Protect Kyber against both ...
## 2022/1424
* Title: DeFi That Defies: Imported Off-Chain Metrics and Pseudonymous On-Chain Activity
* Authors: David W. Kravitz, Mollie Z. Halverson
* [Permalink](https://eprint.iacr.org/2022/1424)
* [Download](https://eprint.iacr.org/2022/1424.pdf)
### Abstract
Traditional finance quantifies risk by collecting and vetting reputation information for an individual, such as credit scores or payment history. While decentralized finance (DeFi) is an exceptionally well-suited application of permissionless blockchains, it is severely constrained in its ability to reconcile identities and quantify associated transaction risk directly on-chain. Opening the ecosystem to a broad range of use cases requires consistent pseudonymity and quantifiable reputation. This paper defies the status quo: exploring methods of assessing risk on-chain by efficiently integrating off-chain identity- and attribute- verification and on-chain transaction activity. We achieve this while preserving individual privacy within a competitive and fair environment and retaining compatibility with existing platforms such as Ethereum. Even though blockchains are inherently public, our solution gives users control over release of information that pertains to them. Consequently, our contribution focuses on customized methods that balance the degree of disclosure of provably-sourced user information against the likelihood of the user successfully gaining access to a desired resource, such as a loan under suitable terms. Our solution is consistent with the zero-trust model in that it imports explicit trust from recognized sources through relevant metrics that are subject to continuous update.
## 2023/1191
* Title: Attribute-Based Multi-Input FE (and more) for Attribute-Weighted Sums
* Authors: Shweta Agrawal, Junichi Tomida, Anshu Yadav
* [Permalink](https://eprint.iacr.org/2023/1191)
* [Download](https://eprint.iacr.org/2023/1191.pdf)
### Abstract
Recently, Abdalla, Gong and Wee (Crypto 2020) provided the first functional encryption scheme for attribute-weighted sums (AWS), where encryption takes as input $N$ (unbounded) attribute-value pairs $\{\vec{x}_i, \vec{z}_i\}_{I \in [N]}$ where $\vec{x}_i$ is public and $\vec{z}_i$ is private, the secret key is associated with an arithmetic branching programs $f$, and decryption returns the weighted sum ${\sum}_{{i \in [N]}} f(\vec{x}_i)^\top \vec{z}_i$, leaking no additional information about the $\vec{z}_i$'s.
We extend FE for AWS to the significantly more challenging multi-party setting and provide the first construction for {\it attribute-based} multi-input FE (MIFE) supporting AWS. For $i \in [n]$, encryptor $i$ can choose an attribute $\vec{y}_i$ together with AWS input $\{\vec{x}_{i,j}, \vec{z}_{i,j}\}$ where $j \in [N_i]$ and $N_i$ is unbounded, the key generator can choose an access control policy $g_i$ along with its AWS function $h_i$ for each $i \in [n]$, and the decryptor can compute
$$\sum_{i \in [n]}\sum_{j \in [N_{i}]}h_{i}(\vec{x}_{i,j})^{\top}\vec{z}_{i,j} \text{ iff } g_{i}(\vec{y}_{i}) =0 \text{ for all } i \in [n]$$
Previously, the only known attribute based MIFE was for the inner product functionality (Abdalla et al.~Asiacrypt 2020), where additionally, $\vec{y}_i$ had to be fixed during setup and must remain the same for all ciphertexts in a given slot.
Our attribute based MIFE implies the notion of multi-input {\it attribute based encryption} (\miabe) recently studied by Agrawal, Yadav and Yamada (Crypto 2022) and Francati, Friolo, Malavolta and Venturi (Eurocrypt 2023), for a conjunction of predicates represented as arithmetic branching programs (ABP).
Along the way, we also provide the first constructions of multi-client FE (MCFE) and dynamic decentralized FE (DDFE) for the AWS functionality. Previously, the best known MCFE and DDFE schemes were for inner products (Chotard et al.~ePrint 2018, Abdalla, Benhamouda and Gay, Asiacrypt 2019, and Chotard et al.~Crypto 2020).
Our constructions are based on pairings and proven selectively secure under the matrix DDH assumption.
## 2023/1192
* Title: CycleFold: Folding-scheme-based recursive arguments over a cycle of elliptic curves
* Authors: Abhiram Kothapalli, Srinath Setty
* [Permalink](https://eprint.iacr.org/2023/1192)
* [Download](https://eprint.iacr.org/2023/1192.pdf)
### Abstract
This paper introduces CycleFold, a new and conceptually simple approach to instantiate folding-scheme-based recursive arguments over a cycle of elliptic curves, for the purpose of realizing incrementally verifiable computation (IVC). Existing approach to solve this problem originates from BCTV (CRYPTO'14) who describe their approach for a SNARK-based recursive argument, and it was adapted by Nova (CRYPTO'22) to a folding-scheme-based recursive argument. A downside of this approach is that it represents a folding scheme verifier as a circuit on both curves in the cycle. (e.g., with Nova, this requires $\approx$10,000 multiplication gates on both curves in the cycle).
CycleFold’s starting point is the observation that folding-scheme-based recursive arguments can be efficiently instantiated without a cycle of elliptic curves—except for a few scalar multiplications in their verifiers (2 in Nova, 1 in HyperNova, and 3 in ProtoStar). Accordingly, CycleFold uses the second curve in the cycle to merely represent a single scalar multiplication ($\approx$1,000--1,500 multiplication gates). CycleFold then folds invocations of that tiny circuit on the first curve in the cycle. This is nearly an order of magnitude improvement over the prior state-of-the-art in terms of circuit sizes on the second curve. CycleFold is particularly beneficial when instantiating folding-scheme-based recursive arguments over “half pairing” cycles (e.g., BN254/Grumpkin) as it keeps the circuit on the non-pairing-friendly curve minimal. The running instance in a CycleFold-based recursive argument consists of an instance on the first curve and a tiny instance on the second curve. Both instances can be proven using a zkSNARK defined over the scalar field of the first curve.
On the conceptual front, with CycleFold, an IVC construction and nor its security proof has to explicitly reason about the cycle of elliptic curves. Finally, due to its simplicity, CycleFold-based recursive argument can be more easily be adapted to support parallel proving with the so-called "binary tree" IVC.
## 2023/1193
* Title: An Anonymous Authenticated Key Agreement Protocol Secure in Partially Trusted Registration Server Scenario for Multi-Server Architectures
* Authors: Inam ul Haq, Jian Wang, Youwen Zhu, Sheharyar Nasir
* [Permalink](https://eprint.iacr.org/2023/1193)
* [Download](https://eprint.iacr.org/2023/1193.pdf)
### Abstract
The accelerated advances in information communication technologies have made it possible for enterprises to deploy large scale applications in a multi-server architecture (also known as cloud computing environment). In this architecture, a mobile user can remotely obtain desired services over the Internet from multiple servers by initially executing a single registration on a trusted registration server (RS). Due to the hazardous nature of the Internet, to protect user privacy and online communication, a lot of multi-server authenticated-key-agreement (MSAKA) schemes have been furnished. However, all such designs lack in two very vital aspects, i.e., 1) no security under the partially trusted RS and 2) RS cannot control a user to access only a wanted combination of service-providing servers. To address these shortcomings, we present a new MSAKA protocol using self-certified public-key cryptography (SCPKC). We confirm the security of the proposed scheme by utilizing the well-known automated verification tool AVISPA and also provide a formal security proof in the random oracle model. Moreover, the software implementation of the proposed scheme, and a performance and security metrics comparison shows that it portrays a better security performance trade-off, and hence is more appropriate for real-life applications having resource constraint devices.
## 2023/1194
* Title: HI-Kyber: A novel high-performance implementation scheme of Kyber based on GPU
* Authors: Xinyi Ji, Jiankuo Dong, Pinchang Zhang, Deng Tonggui, Hua Jiafeng, Fu Xiao
* [Permalink](https://eprint.iacr.org/2023/1194)
* [Download](https://eprint.iacr.org/2023/1194.pdf)
### Abstract
CRYSTALS-Kyber, as the only public key encryption (PKE) algorithm selected by the National Institute of Standards and Technology (NIST) in the third round, is considered one of the most promising post-quantum cryptography (PQC) schemes. Lattice-based cryptography uses complex discrete alogarithm problems on lattices to build secure encryption and decryption systems to resist attacks from quantum computing. Performance is an important bottleneck affecting the promotion of post quantum cryptography. In this paper, we present a High-performance Implementation of Kyber (named HI-Kyber) on the NVIDIA GPUs, which can increase the key-exchange performance of Kyber to the million-level. Firstly, we propose a lattice-based PQC implementation architecture based on kernel fusion, which can avoid redundant global-memory access operations. Secondly, We optimize and implement the core operations of CRYSTALS-Kyber, including Number Theoretic Transform (NTT), inverse NTT (INTT), pointwise multiplication, etc. Especially for the calculation bottleneck NTT operation, three novel methods are proposed to explore extreme performance: the sliced layer merging (SLM), the sliced depth-first search (SDFS-NTT) and the entire depth-first search (EDFS-NTT), which achieve a speedup of 7.5%, 28.5%, and 41.6% compared to the native implementation. Thirdly, we conduct comprehensive performance experiments with different parallel dimensions based on the above optimization. Finally, our key exchange performance reaches 1,664 kops/s. Specifically, based on the same platform, our HI-Kyber is 3.52$\times$ that of the GPU implementation based on the same instruction set and 1.78$\times$ that of the state-of-the-art one based on AI-accelerated tensor core.
## 2023/1195
* Title: PicoEMP: A Low-Cost EMFI Platform Compared to BBI and Voltage Fault Injection using TDC and External VCC Measurements
* Authors: Colin O'Flynn
* [Permalink](https://eprint.iacr.org/2023/1195)
* [Download](https://eprint.iacr.org/2023/1195.pdf)
### Abstract
Electromagnetic Fault Injection (EMFI) has been demonstrated to be useful for both academic and industrial research. Due to the dangerous voltages involved, most work is done with commercial tools. This paper introduces a safety-focused low-cost and open-source design that can be built for less than \$50 using only off-the-shelf parts.
The paper also introduces an iCE40 based Time-to-Digital Converter (TDC), which is used to visualize the glitch inserted by the EMFI tool. This demonstrates the internal voltage perturbations between voltage, body biasing injection (BBI), and EMFI all result in similar waveforms. In addition, a link between an easy-to-measure external voltage measurement and the internal measurement is made. Attacks are also made on a hardware AES engine, and a soft-core RISC-V processor, all running on the same iCE40 FPGA.
The platform is used to demonstrate several aspects of fault injection, including that the spatial positioning of the EMFI probe can impact the glitch strength, and that the same physical device may require widely different glitch parameters when running different designs.
## 2023/1196
* Title: A New Paradigm for Verifiable Secret Sharing
* Authors: Sourav Das, Zhuolun Xiang, Alin Tomescu, Alexander Spiegelman, Benny Pinkas, Ling Ren
* [Permalink](https://eprint.iacr.org/2023/1196)
* [Download](https://eprint.iacr.org/2023/1196.pdf)
### Abstract
Verifiable Secret Sharing (VSS) is a fundamental building block in cryptography. Despite its importance and extensive studies, existing VSS protocols are often complex and inefficient. Many of them do not support dual threads, are not publicly verifiable, or do not properly terminate in asynchronous networks. In this paper, we present a new and simple paradigm for designing VSS protocols in synchronous and asynchronous networks. Our VSS protocols are optimally fault-tolerant, i.e., they tolerate a 1/2 and a 1/3 fraction of malicious nodes in synchronous and asynchronous networks, respectively. They only require a public key infrastructure and the hardness of discrete logarithms. Our protocols support dual thresholds and their transcripts are publicly verifiable. We implement our VSS protocols and measure their computation and communication costs with up to 1024 nodes. Our evaluation illustrates that our VSS protocols provide asynchronous termination and public verifiability with minimum performance overhead. Compared to the existing VSS protocol with similar guarantees, our protocols are 5-15× and 8-13× better in computation and communication cost, respectively.
## 2023/1197
* Title: Towards a Quantum-resistant Weak Verifiable Delay Function
* Authors: Thomas Decru, Luciano Maino, Antonio Sanso
* [Permalink](https://eprint.iacr.org/2023/1197)
* [Download](https://eprint.iacr.org/2023/1197.pdf)
### Abstract
In this paper, we present a new quantum-resistant weak Verifiable Delay Function based on a purely algebraic construction. Its delay depends on computing a large-degree isogeny between elliptic curves, whereas its verification relies on the computation of isogenies between products of two elliptic curves. One of its major advantages is its expected fast verification time. However, it is important to note that the practical implementation of our theoretical framework poses significant challenges. We examine the strengths and weaknesses of our construction, analyze its security and provide a proof-of-concept implementation.
## 2023/1198
* Title: Towards Achieving Provable Side-Channel Security in Practice
* Authors: Sonia Belaïd, Gaëtan Cassiers, Camille Mutschler, Matthieu Rivain, Thomas Roche, François-Xavier Standaert, Abdul Rahman Taleb
* [Permalink](https://eprint.iacr.org/2023/1198)
* [Download](https://eprint.iacr.org/2023/1198.pdf)
### Abstract
Physical side-channel attacks are powerful attacks that exploit a device's physical emanations to break the security of cryptographic implementations. Many countermeasures have been proposed against these attacks, especially the widely-used and efficient masking countermeasure. Nevertheless, proving the security of masked implementations is challenging. Current techniques rely on empirical approaches to validate the security of such implementations. On the other hand, the theoretical community introduced leakage models to provide formal proofs of the security of masked implementations. Meanwhile, these leakage models rely on physical assumptions that are difficult to satisfy in practice, and the literature lacks a clear framework to implement proven secure constructions on a physical device while preserving the proven security.
In this paper, we present a complete methodology describing the steps to turn an abstract masking scheme proven secure in a theoretical leakage model into a physical implementation satisfying provable security against side-channel attacks in practice. We propose new tools to enforce or relax the physical assumptions the indeal noisy leakage model rely on and provide novel ways of including them in a physical implementation. We also highlight the design goals for an embedded device to reach high levels of proven security, discussing the limitations and open problems of the practical usability of the leakage models. Our goal is to show that it is possible to bridge theory and practice and to motivate further research to fully close the gap and get practical implementations proven secure against side-channel attacks on a physical device without any ideal assumption about the leakage.
## 2023/1199
* Title: RSA Blind Signatures with Public Metadata
* Authors: Ghous Amjad, Kevin Yeo, Moti Yung
* [Permalink](https://eprint.iacr.org/2023/1199)
* [Download](https://eprint.iacr.org/2023/1199.pdf)
### Abstract
Anonymous tokens are digital signature schemes that enable an issuer to provider users with signatures without learning the input message or the resulting signature received by the user. These primitives allow applications to propagate trust while simultaneously protecting the identity of the user. Anonymous tokens have become a core component for improving the privacy of several real-world applications including ad measurements, authorization protocols, spam detection and VPNs.
In certain applications, it is natural to associate signatures with specific public metadata ensuring that signatures only propagate trust with respect to only a certain set of scenarios. To solve this, we study the notion of anonymous tokens with public metadata in this work. We present a variant of RSA blind signatures with public metadata such that issuers may only generate signatures that verify for a certain choice of public metadata. We prove the security of our protocol under one-more RSA assumptions with multiple exponents that we introduce. Furthermore, we provide evidence that the concrete security bounds should be nearly identical to standard RSA blind signatures. The protocols in this paper have been proposed as a technical specification in an IRTF internet draft.
## 2023/1200
* Title: Shining Light on the Shadow: Full-round Practical Distinguisher for Lightweight Block Cipher Shadow
* Authors: Sunyeop Kim, Myoungsu Shin, Seonkyu Kim, Hanbeom Shin, Insung Kim, Donggeun Kwon, Dongjae Lee, Seonggyeom Kim, Deukjo Hong, Jaechul Sung, Seokhie Hong
* [Permalink](https://eprint.iacr.org/2023/1200)
* [Download](https://eprint.iacr.org/2023/1200.pdf)
### Abstract
Shadow is a lightweight block cipher proposed at IEEE IoT journal 2021. Shadow’s main design principle is adopting a variant 4- branch Feistel structure in order to provide a fast diffusion rate. We define such a structure as Shadow structure and prove that it is al- most identical to the Generalized Feistel Network, which invalidates the design principle. Moreover, we give a structural distinguisher that can distinguish Shadow structure from random permutation with only two plaintext/ciphertext pairs. By exploiting the key schedule, the distin- guisher can be extended to key recovery attack with only one plain- text/ciphertext pair. Furthermore, by considering Shadow’s round func- tion, only certain forms of monomials can appear in the ciphertext, re- sulting in an integral distinguisher of four plaintext/ciphertext pairs. Even more, the algebraic degree does not increase more than 12 for Shadow-32 and 20 for Shadow-64 regardless of rounds used. Our results show that Shadow is highly vulnerable to algebraic attacks, and that algebraic attacks should be carefully considered when designing ciphers with AND, rotation, and XOR operations.
## 2023/1201
* Title: Privacy-preserving edit distance computation using secret-sharing two-party computation
* Authors: Hernán Darío Vanegas Madrigal, Daniel Cabarcas Jaramillo, Diego F. Aranha
* [Permalink](https://eprint.iacr.org/2023/1201)
* [Download](https://eprint.iacr.org/2023/1201.pdf)
### Abstract
The edit distance is a metric widely used in genomics to measure the similarity of two DNA chains. Motivated by privacy concerns, we propose a 2PC protocol to compute the edit distance while preserving the privacy of the inputs. Since the edit distance algorithm can be expressed as a mixed-circuit computation, our approach uses protocols based on secret-sharing schemes like Tinier and SPD$\mathbb{Z}_{2^k}$; and also daBits to perform domain conversion and edaBits to perform arithmetic comparisons. We modify the Wagner-Fischer edit distance algorithm, aiming at reducing the number of rounds of the protocol, and achieve a flexible protocol with a trade-off between rounds and multiplications. We implement our proposal in the MP-SPDZ framework, and our experiments show that it reduces the execution time respectively by 81\% and 54\% for passive and active security with respect to a baseline implementation in a LAN. The experiments also show that our protocol reduces traffic by two orders of magnitude compared to a BMR-MASCOT implementation.
## 2023/1202
* Title: Extension of Shannon's theory of ciphers based on Latin rectangles
* Authors: Karel BURDA
* [Permalink](https://eprint.iacr.org/2023/1202)
* [Download](https://eprint.iacr.org/2023/1202.pdf)
### Abstract
The paper extends Shannon's classical theory of ciphers. Here ciphers are modeled by Latin rectangles and their resistance to brute force attack is assessed through the valence of cryptograms. The valence of a cryptogram is defined as the number of all meaningful messages produced by decrypting the cryptogram with all possible keys. In this paper, the mean cryptogram valence of an arbitrary modern cipher with K keys, N outputs and N inputs, of which M inputs are messages, is derived. Furthermore, the lower bound on the valence of the cryptograms of entire ciphers is derived in this paper. The obtained parameters allow to assess the resistance of cryptograms, resp. ciphers against brute force attack. The model is general, illustrative and uses a simpler mathematical apparatus than existing theory. Therefore, it can also be used as an introduction to the theory of resistance of ciphers to brute force attack.
## 2023/1203
* Title: Collaborative Privacy-Preserving Analysis of Oncological Data using Multiparty Homomorphic Encryption
* Authors: Ravit Geva, Alexander Gusev, Yuriy Polyakov, Lior Liram, Oded Rosolio, Andreea Alexandru, Nicholas Genise, Marcelo Blatt, Zohar Duchin, Barliz Waissengrin, Dan Mirelman, Felix Bukstein, Deborah T. Blumenthal, Ido Wolf, Sharon Pelles-Avraham, Tali Schaffer, Lee A. Lavi, Daniele Micciancio, Vinod Vaikuntanathan, Ahmad Al Badawi, Shafi Goldwasser
* [Permalink](https://eprint.iacr.org/2023/1203)
* [Download](https://eprint.iacr.org/2023/1203.pdf)
### Abstract
Real-world healthcare data sharing is instrumental in constructing broader-based and larger clinical data sets that may improve clinical decision-making research and outcomes. Stakeholders are frequently reluctant to share their data without guaranteed patient privacy, proper protection of their data sets, and control over the usage of their data. Fully homomorphic encryption (FHE) is a cryptographic capability that can address these issues by enabling computation on encrypted data without intermediate decryptions, so the analytics results are obtained without revealing the raw data. This work presents a toolset for collaborative privacy-preserving analysis of oncological data using multiparty FHE. Our toolset supports survival analysis, logistic regression training, and several common descriptive statistics. We demonstrate using oncological data sets that the toolset achieves high accuracy and practical performance, which scales well to larger data sets. As part of this work, we propose a novel cryptographic protocol for interactive bootstrapping in multiparty FHE, which is of independent interest. The toolset we develop is general-purpose and can be applied to other collaborative medical and healthcare application domains.
## 2023/1204
* Title: On Fully-Secure Honest Majority MPC without $n^2$ Round Overhead
* Authors: Daniel Escudero, Serge Fehr
* [Permalink](https://eprint.iacr.org/2023/1204)
* [Download](https://eprint.iacr.org/2023/1204.pdf)
### Abstract
Fully secure multiparty computation (or guaranteed output delivery) among $n$ parties can be achieved with perfect security if the number of corruptions $t$ is less than $n/3$, or with statistical security with the help of a broadcast channel if $t<n/2$. In the case of $t<n/3$, it is known that it is possible to achieve linear communication complexity, but at a cost of having a round count of $\Omega(\mathsf{depth}(C) + n)$ in the worst case. The number of rounds can be reduced to $O(\mathsf{depth}(C))$ by either increasing communication, or assuming some correlated randomness (a setting also known as the preprocesing model). For $t<n/2$ it is also known that linear communication complexity is achievable, but at the cost of $\Omega(\mathsf{depth}(C) + n^2)$ rounds, due to the use of a technique called dispute control. However, in contrast to the $t<n/3$ setting, it is not known how to reduce this round count for $t<n/2$ to $O(\mathsf{depth}(C))$, neither allowing for larger communication, or by using correlated randomness.
In this work we make progress in this direction by taking the second route above: we present a fully secure protocol for $t<n/2$ in the preprocessing model, that achieves linear communication complexity, and whose round complexity is only $O(\mathsf{depth}(C))$, without the additive $n^2$ term that appears from the use of dispute control. While on the $t<n/3$ such result requires circuits of width $\Omega(n)$, in our case circuits must be of width $\Omega(n^2)$, leaving it as an interesting future problem to reduce this gap. Our $O(\mathsf{depth}(C))$ round count is achieved by avoiding the use of dispute control entirely, relying on a different tool for guaranteeing output. In the $t<n/3$ setting when correlated randomness is available, this is done by using error correction to reconstruct secret-shared values, but in the $t<n/2$ case the equivalent is robust secret-sharing, which guarantees the reconstruction of a secret in spite of errors. However, we note that a direct use of such tool would lead to \emph{quadratic} communication, stemming from the fact that each party needs to authenticate their share towards each other party. At the crux of our techniques lies a novel method for reconstructing a batch of robustly secret-shared values while involving only a linear amount of communication per secret, which may also be of independent interest.
## 2023/1205
* Title: On the security of REDOG
* Authors: Tanja Lange, Alex Pellegrini, Alberto Ravagnani
* [Permalink](https://eprint.iacr.org/2023/1205)
* [Download](https://eprint.iacr.org/2023/1205.pdf)
### Abstract
We analyze REDOG, a public-key encryption system submitted to the Korean
competition on post-quantum cryptography.
REDOG is based on rank-metric codes. We prove its incorrectness and attack its
implementation providing an efficient message recovery attack. Furthermore, we
show that the security of REDOG is much lower than claimed. We then
proceed to mitigate these issues and provide two approaches to fix the
decryption issue, one of which also leads to better security.
## 2023/1206
* Title: Decentralized Threshold Signatures for Blockchains with Non-Interactive and Transparent Setup
* Authors: Kwangsu Lee
* [Permalink](https://eprint.iacr.org/2023/1206)
* [Download](https://eprint.iacr.org/2023/1206.pdf)
### Abstract
Threshold signatures are digital signatures that support the multi-party signature generation such that a number of parties initially share a signing key and more than a threshold number of parties gather to generate a signature. In this paper, we propose a non-interactive decentralized threshold signature (NIDTS) scheme that supports the non-interactive and transparent key setup based on BLS signatures. Our NIDTS scheme has the following properties. 1) The key setup process is completely non-interactive and does not require message exchange between parties since the transfer of the register keys of parties is enough for a combiner to generate a compact verification key. 2) The register key of a party is compact since the size is independent of the number of group parties. 3) The signing process of parties is non-interactive. 4) The final threshold signature as well as partial signatures are succinct.
We prove the security of our NIDTS scheme under computational assumptions in the random oracle model. Furthermore, we implement our NIDTS scheme in Rust and compare its performance with other scheme to show that the key setup of our scheme is more efficient. For example, in the unweighted setting of 1000 parties, the key setup process of the NIDTS scheme takes 164 seconds, which is 5.9 times faster than the key setup process of the multiverse threshold signature (MTS) scheme.
## 2023/1207
* Title: DeFi Auditing: Mechanisms, Effectiveness, and User Perceptions
* Authors: Ding Feng, Rupert Hitsch, Kaihua Qin, Arthur Gervais, Roger Wattenhofer, Yaxing Yao, Ye Wang
* [Permalink](https://eprint.iacr.org/2023/1207)
* [Download](https://eprint.iacr.org/2023/1207.pdf)
### Abstract
Decentralized Finance (DeFi), a blockchain-based financial ecosystem, suffers from smart contract vulnerabilities that led to a loss exceeding 3.24 billion USD by April 2022. To address this, blockchain firms audit DeFi applications, a process known as DeFi auditing. Our research aims to comprehend the mechanism and efficacy of DeFi auditing. We discovered its ability to detect vulnerabilities in smart contract logic and interactivity with other DeFi entities, but also noted its limitations in communication, transparency, remedial action implementation, and in preventing certain DeFi attacks. Moreover, our interview study delved into user perceptions of DeFi auditing, unmasking gaps in awareness, usage, and trust, and offering insights to address these issues.
## 2023/1208
* Title: Mutator Sets and their Application to Scalable Privacy
* Authors: Alan Szepieniec, Thorkil Værge
* [Permalink](https://eprint.iacr.org/2023/1208)
* [Download](https://eprint.iacr.org/2023/1208.pdf)
### Abstract
A mutator set is a cryptographic data structure for authenticating operations on a changing set of data elements called items. Informally:
- There is a short commitment to the set.
- There are succinct membership proofs for elements of the set.
- It is possible to update the commitment as well as the membership proofs with minimal effort as new items are added to the set or as existing items are removed from it.
- Items cannot be removed before they were added.
- It is difficult to link an item's addition to the set to its removal from the set, except when using information available only to the party that generated it.
This paper formally defines the notion, motivates its existence with an application to scalable privacy in the context of cryptocurrencies, and proposes an instantiation inspired by Merkle mountain ranges and Bloom filters.
## 2023/1209
* Title: Infinite families of minimal binary codes via Krawtchouk polynomials
* Authors: Xiaoni Du, René Rodríguez, Hao Wu
* [Permalink](https://eprint.iacr.org/2023/1209)
* [Download](https://eprint.iacr.org/2023/1209.pdf)
### Abstract
Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, the general Maiorana-McFarland class. We employ a method first proposed by Ding et al. [7] to construct minimal codes violating the Ashikhmin-Barg bound (wide minimal codes) by using Krawtchouk polynomials. The lengths, dimensions, and weight distributions of the obtained codes are determined using the Walsh spectrum distribution of the chosen Boolean functions. Our findings demonstrate that a vast majority of the newly constructed codes are wide minimal codes. Furthermore, our proposed codes exhibit a significantly larger minimum distance, in some cases, compared to some existing similar constructions. Finally, we address this method, based on Krawtchouk polynomials, more generally, and highlight certain generic properties related to it. This study provides insights into the scope of this method.
## 2023/1210
* Title: Decentralized Finance (DeFi): A Survey
* Authors: Erya Jiang, Bo Qin, Qin Wang, Zhipeng Wang, Qianhong Wu, Jian Weng, Xinyu Li, Chenyang Wang, Yuhang Ding, Yanran Zhang
* [Permalink](https://eprint.iacr.org/2023/1210)
* [Download](https://eprint.iacr.org/2023/1210.pdf)
### Abstract
Decentralized Finance (DeFi) is a new paradigm in the creation, distribution, and utilization of financial services via the integration of blockchain technology. Our research conducts a comprehensive introduction and meticulous classification of various DeFi applications. Beyond that, we thoroughly analyze these risks from both technical and economic perspectives, spanning multiple layers. Lastly, we point out research directions in DeFi, encompassing areas of technological advancements, innovative economics, and privacy optimization.
## 2023/1211
* Title: Optimal Flexible Consensus and its Application to Ethereum
* Authors: Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse
* [Permalink](https://eprint.iacr.org/2023/1211)
* [Download](https://eprint.iacr.org/2023/1211.pdf)
### Abstract
Classic BFT consensus protocols guarantee safety and liveness for all clients if fewer than one-third of replicas are faulty. However, in applications such as high-value payments, some clients may want to prioritize safety over liveness. Flexible consensus allows each client to opt for a higher safety resilience, albeit at the expense of reduced liveness resilience. We present the first construction that allows optimal safety--liveness tradeoff for every client simultaneously. This construction is modular and is realized as an add-on applied on top of an existing consensus protocol. The add-on consists of an additional round of voting and permanent locking done by the replicas, to sidestep a sub-optimal quorum-intersection-based constraint present in previous solutions. We adapt our construction to the existing Ethereum protocol to derive optimal flexible confirmation rules that clients can adopt unilaterally without requiring system-wide changes. This is possible because existing Ethereum protocol features can double as the extra voting and locking. We demonstrate an implementation using Ethereum's consensus API.
## 2023/1212
* Title: CLRW1$^{3}$ is not Secure Beyond the Birthday Bound: Breaking TNT with ${O(2^{n/2})}$ queries
* Authors: Mustafa Khairallah
* [Permalink](https://eprint.iacr.org/2023/1212)
* [Download](https://eprint.iacr.org/2023/1212.pdf)
### Abstract
In this paper, we present a new distinguisher for the Tweak-aNd-Tweak (TNT) tweakable block cipher with $O(2^{n/2})$ complexity. The distinguisher is an adaptive chosen ciphertext distinguisher, unlike previous attacks that are only non-adaptive chosen plaintext attacks. However, the attack contradicts the security claims made by the designers. Given TNT can be seen as the three-round CLRW1 tweakable block cipher, our attack matches its more conservative bound. We provide the distinguisher description, a probabilistic analysis of its behaviour, experimental verification and an analysis of why the proof fails to capture the security of TNT. In summary, the distinguisher is based on collision counting and exploits non-uniformity in the statistical behaviour of random permutations. It reduces the goal of finding the collision to solving a difference equation defined over a random permutation. Due to this relation, the number of collisions observed by the distinguisher is twice as expected from an ideal tweakable block cipher.
## 2023/1213
* Title: Fallen Sanctuary: A Higher-Order and Leakage-Resilient Rekeying Scheme
* Authors: Rei Ueno, Naofumi Homma, Akiko Inoue, Kazuhiko Minematsu
* [Permalink](https://eprint.iacr.org/2023/1213)
* [Download](https://eprint.iacr.org/2023/1213.pdf)
### Abstract
This paper presents a provably secure, higher-order, and leakage-resilient
(LR) rekeying scheme named LR Rekeying with Random oracle Repetition (LR4), along with a quantitative security evaluation methodology. Many existing LR cryptographies are based on a concept of leveled implementation, which still essentially require a leak-free sanctuary (i.e., differential power analysis (DPA)-resistant component(s)) for some parts. In addition, although several LR pseudorandom functions (PRFs) based on only bounded DPA-resistant components have been developed, their validity and effectiveness for rekeying usage still need to be determined. In contrast, LR4 is formally proven under a leakage model that captures the practical goal of side-channel attack (SCA) protection (e.g., masking with a practical order) and assumes no unbounded DPA-resistant sanctuary. This proof suggests that LR4 resists exponential invocations (up to the birthday bound of key size) without using any unbounded leak-free component, which is the first of its kind. Moreover, we present a quantitative SCA success rate evaluation methodology for LR4 that combines the bounded leakage models for LR cryptography and a state-of-the-art information-theoretical SCA evaluation method. We validate its soundness and effectiveness as a DPA countermeasure through a numerical evaluation; that is, the number of secure calls of a symmetric primitive increases exponentially by increasing a security parameter under practical conditions.
## 2023/1214
* Title: Verifiable Verification in Cryptographic Protocols
* Authors: Marc Fischlin, Felix Günther
* [Permalink](https://eprint.iacr.org/2023/1214)
* [Download](https://eprint.iacr.org/2023/1214.pdf)
### Abstract
Common verification steps in cryptographic protocols, such as signature or message authentication code checks or the validation of elliptic curve points, are crucial for the overall security of the protocol. Yet implementation errors omitting these steps easily remain unnoticed, as often the protocol will function perfectly anyways. One of the most prominent examples is Apple's goto fail bug where the erroneous certificate verification skipped over several of the required steps, marking invalid certificates as correctly verified. This vulnerability went undetected for at least 17 months.
We propose here a mechanism which supports the detection of such errors on a cryptographic level. Instead of merely returning the binary acceptance decision, we let the verification return more fine-grained information in form of what we call a confirmation code. The reader may think of the confirmation code as disposable information produced as part of the relevant verification steps. In case of an implementation error like the goto fail bug, the confirmation code would then miss essential elements.
The question arises now how to verify the confirmation code itself. We show how to use confirmation codes to tie security to basic functionality at the overall protocol level, making erroneous implementations be detected through the protocol not functioning properly. More concretely, we discuss the usage of confirmation codes in secure connections, established via a key exchange protocol and secured through the derived keys. If some verification steps in a key exchange protocol execution are faulty, then so will be the confirmation codes, and because we can let the confirmation codes enter key derivation, the connection of the two parties will eventually fail. In consequence, an implementation error like goto fail would now be detectable through a simple connection test.
## 2023/1215
* Title: Authentica: A Secure Authentication Mechanism using a Software-defined Unclonable Function
* Authors: Ripon Patgiri, Laiphrakpam Dolendro Singh
* [Permalink](https://eprint.iacr.org/2023/1215)
* [Download](https://eprint.iacr.org/2023/1215.pdf)
### Abstract
Password-based authentication is an extensively used method to authenticate users. It uses cryptography to communicate the authentication process. On the contrary, the physically unclonable function (PUF)-based authentication mechanism is also gaining popularity rapidly due to its usability in IoT devices. It is a lightweight authentication mechanism that does not use cryptography protocol. PUF-based authentication mechanisms cannot authenticate users. To overcome the drawback of PUF, we introduce a software-defined unclonable function (SUF, for short). Contrary to the PUF, the SUF is used to authenticate users, not devices. We use SUF to implement a lightweight password-based authentication mechanism termed Authentica. Authentica bridges the gap between the password-based and the PUF-based authentication mechanism. Authentica does not use cryptography for authentication. However, we establish challenge-response using cryptography during the registration phase, which is a one-time cost. Authentica addresses a) impersonation attacks, b) collision attacks, c) dictionary and rainbow table attacks, d) replay attacks, e) DDoS attacks, f) the domino effect issues, and g) the challenge-response database leakage issues.
## 2023/1216
* Title: Unlocking the lookup singularity with Lasso
* Authors: Srinath Setty, Justin Thaler, Riad Wahby
* [Permalink](https://eprint.iacr.org/2023/1216)
* [Download](https://eprint.iacr.org/2023/1216.pdf)
### Abstract
This paper introduces Lasso, a new family of lookup arguments, which allow an untrusted prover to commit to a vector $a \in \mathbb{F}^m$ and prove that all entries of a reside in some predetermined table $t \in \mathbb{F}^n$. Lasso’s performance characteristics unlock the so-called "lookup singularity". Lasso works with any multilinear polynomial commitment scheme, and provides the following efficiency properties.
For $m$ lookups into a table of size $n$, Lasso’s prover commits to just $m + n$ field elements. Moreover, the committed field elements are small, meaning that, no matter how big the field $\mathbb{F}$ is, they are all in the set $\{0, . . . , m\}$. When using a multiexponentiation-based commitment scheme, this results in the prover’s costs dominated by only $O(m + n)$ group operations (e.g., elliptic curve point additions), plus the cost to prove an evaluation of a multilinear polynomial whose evaluations over the Boolean hypercube are the table entries. This represents a significant improvement in prover costs over prior lookup arguments (e.g., plookup, Halo2’s lookups, lookup arguments based on logarithmic derivatives).
Unlike all prior lookup arguments, if the table $t$ is structured (in a precise sense that we define), then no party needs to commit to $t$, enabling the use of much larger tables than prior works (e.g., of size $2^{128}$ or larger). Moreover, Lasso’s prover only "pays" in runtime for table entries that are accessed by the lookup operations. This applies to tables commonly used to implement range checks, bitwise operations, big-number arithmetic, and even transitions of a full-fledged CPU such as RISC-V. Specifically, for any integer parameter $c > 1$, Lasso’s prover’s dominant cost is committing to $3 \cdot c \cdot m + c \cdot n^{1/c}$ field elements. Furthermore, all these field elements are “small”, meaning they are in the set $\{0, . . . , \max{(m, n^{1/c}, q)} − 1\}$, where $q$ is the maximum value in $a$.
Lasso’s starting point is Spark, a time-optimal polynomial commitment scheme for sparse polynomials in Spartan (CRYPTO 2020). We first provide a stronger security analysis for Spark. Spartan’s security analysis assumed that certain metadata associated with a sparse polynomial is committed by an honest party (this is acceptable for its purpose in Spartan, but not for Lasso). We prove that Spark remains secure even when that metadata is committed by a malicious party. This provides the first "standard" commitment scheme for sparse multilinear polynomials with optimal prover costs. We then generalize Spark to directly support a lookup argument for both structured and unstructured tables, with the efficiency characteristics noted above.
## 2023/1217
* Title: Jolt: SNARKs for Virtual Machines via Lookups
* Authors: Arasu Arun, Srinath Setty, Justin Thaler
* [Permalink](https://eprint.iacr.org/2023/1217)
* [Download](https://eprint.iacr.org/2023/1217.pdf)
### Abstract
Succinct Non-interactive Arguments of Knowledge (SNARKs) allow an untrusted prover to establish that it correctly ran some "witness-checking procedure" on a witness. A zkVM (short for zero-knowledge Virtual Machine) is a SNARK that allows the witness-checking procedure to be specified as a computer program written in the assembly language of a specific instruction set architecture (ISA).
A $\textit{front-end}$ converts computer programs into a lower-level representation such as an arithmetic circuit or generalization thereof. A SNARK for circuit-satisfiability can then be applied to the resulting circuit.
We describe a new front-end technique called Jolt that applies to a variety of ISAs. Jolt arguably realizes a vision called the $\textit{lookup singularity}$, which seeks to produce circuits that only perform lookups into pre-determined lookup tables. The circuits output by Jolt primarily perform lookups into a gigantic lookup table, of size more than $2^{128}$, that depends only on the ISA. The validity of the lookups are proved via a new $\textit{lookup argument}$ called Lasso described in a companion work (Setty, Thaler, and Wahby, e-print 2023). Although size-$2^{128}$ tables are vastly too large to materialize in full, the tables arising in Jolt are structured, avoiding costs that grow linearly with the table size.
We describe performance and auditability benefits of Jolt compared to prior zkVMs, focusing on the popular RISC-V ISA as a concrete example. The dominant cost for the Jolt prover applied to this ISA (on $64$-bit data types) is cryptographically committing to about six $256$-bit field elements per step of the RISC-V CPU. This compares favorably to prior zkVM provers, even those focused on far simpler VMs.
## 2023/1218
* Title: Arke: Scalable and Byzantine Fault Tolerant Privacy-Preserving Contact Discovery
* Authors: Nicolas Mohnblatt, Alberto Sonnino, Kobi Gurkan, Philipp Jovanovic
* [Permalink](https://eprint.iacr.org/2023/1218)
* [Download](https://eprint.iacr.org/2023/1218.pdf)
### Abstract
Contact discovery is a crucial component of social applications, facilitating interactions between registered contacts. This work introduces Arke, a novel approach to contact discovery that addresses the limitations of existing solutions in terms of privacy, scalability, and reliance on trusted third parties. Arke ensures the unlinkability of user interactions, mitigates enumeration attacks, and operates without single points of failure or trust. Notably, Arke is the first contact discovery system whose performance is independent of the total number of users and the first that can operate in a Byzantine setting. It achieves its privacy goals through an unlinkable handshake mechanism built on top of an identity-based non-interactive key exchange. By leveraging a custom distributed architecture, Arke forgoes the expense of consensus to achieve scalability while maintaining consistency in a Byzantine fault tolerant environment. Performance evaluations demonstrate that Arke can support enough throughput to operate at a planetary scale while maintaining sub-second latencies in a large geo-distributed setting.
## 2023/1219
* Title: A Note on “Secure Quantized Training for Deep Learning”
* Authors: Marcel Keller, Ke Sun
* [Permalink](https://eprint.iacr.org/2023/1219)
* [Download](https://eprint.iacr.org/2023/1219.pdf)
### Abstract
Keller and Sun (ICML'22) have found a gap in the accuracy between floating-point deep learning in cleartext and secure quantized deep learning using multi-party computation. We have discovered that this gap is caused by a bug in the implementation of max-pooling. In this note, we present updated figures to support this conclusion. We also add figures for another network on CIFAR-10.
## 2023/1220
* Title: Quasi-linear Masking to Protect Kyber against both SCA and FIA
* Authors: Pierre-Augustin BERTHET, Cédric Tavernier, Jean-Luc Danger, Laurent Sauvage
* [Permalink](https://eprint.iacr.org/2023/1220)
* [Download](https://eprint.iacr.org/2023/1220.pdf)
### Abstract
The recent technological advances in Post-Quantum Cryptography (PQC) rise the questions of robust implementations of new asymmetric cryptographic primitives in today’s technology. This is the case for the lattice-based CRYSTALS-Kyber algorithm which has been selected as the first NIST standard for Public Key Encryption (PKE) and Key Encapsulation Mechanisms (KEM). We have notably to make sure the Kyber implementation is resilient against physical attacks like Side-Channel Analysis (SCA) and Fault Injection Attacks (FIA). To reach this goal, we propose to use the masking countermeasure, more precisely the generic Direct Sum Masking method (DSM). By taking inspiration of a previous paper on AES, we extend the method to finite fields of characteristic prime other than 2 and even-length codes. In particular, we investigated its
application to Keccak, which is the hash-based function used in Kyber. We also provided the first masked implementation of Kyber providing both SCA and FIA resilience while not requiring any conversion between different masking methods.
1. [2022/1424] DeFi That Defies: Imported Off-Chain Metrics and ...
2. [2023/1191] Attribute-Based Multi-Input FE (and more) for ...
3. [2023/1192] CycleFold: Folding-scheme-based recursive arguments ...
4. [2023/1193] An Anonymous Authenticated Key Agreement Protocol ...
5. [2023/1194] HI-Kyber: A novel high-performance implementation ...
6. [2023/1195] PicoEMP: A Low-Cost EMFI Platform Compared to BBI ...
7. [2023/1196] A New Paradigm for Verifiable Secret Sharing
8. [2023/1197] Towards a Quantum-resistant Weak Verifiable Delay ...
9. [2023/1198] Towards Achieving Provable Side-Channel Security in ...
10. [2023/1199] RSA Blind Signatures with Public Metadata
11. [2023/1200] Shining Light on the Shadow: Full-round Practical ...
12. [2023/1201] Privacy-preserving edit distance computation using ...
13. [2023/1202] Extension of Shannon's theory of ciphers based on ...
14. [2023/1203] Collaborative Privacy-Preserving Analysis of ...
15. [2023/1204] On Fully-Secure Honest Majority MPC without $n^2$ ...
16. [2023/1205] On the security of REDOG
17. [2023/1206] Decentralized Threshold Signatures for Blockchains ...
18. [2023/1207] DeFi Auditing: Mechanisms, Effectiveness, and User ...
19. [2023/1208] Mutator Sets and their Application to Scalable Privacy
20. [2023/1209] Infinite families of minimal binary codes via ...
21. [2023/1210] Decentralized Finance (DeFi): A Survey
22. [2023/1211] Optimal Flexible Consensus and its Application to ...
23. [2023/1212] CLRW1$^{3}$ is not Secure Beyond the Birthday ...
24. [2023/1213] Fallen Sanctuary: A Higher-Order and Leakage- ...
25. [2023/1214] Verifiable Verification in Cryptographic Protocols
26. [2023/1215] Authentica: A Secure Authentication Mechanism using ...
27. [2023/1216] Unlocking the lookup singularity with Lasso
28. [2023/1217] Jolt: SNARKs for Virtual Machines via Lookups
29. [2023/1218] Arke: Scalable and Byzantine Fault Tolerant ...
30. [2023/1219] A Note on “Secure Quantized Training for Deep Learning”
31. [2023/1220] Quasi-linear Masking to Protect Kyber against both ...
## 2022/1424
* Title: DeFi That Defies: Imported Off-Chain Metrics and Pseudonymous On-Chain Activity
* Authors: David W. Kravitz, Mollie Z. Halverson
* [Permalink](https://eprint.iacr.org/2022/1424)
* [Download](https://eprint.iacr.org/2022/1424.pdf)
### Abstract
Traditional finance quantifies risk by collecting and vetting reputation information for an individual, such as credit scores or payment history. While decentralized finance (DeFi) is an exceptionally well-suited application of permissionless blockchains, it is severely constrained in its ability to reconcile identities and quantify associated transaction risk directly on-chain. Opening the ecosystem to a broad range of use cases requires consistent pseudonymity and quantifiable reputation. This paper defies the status quo: exploring methods of assessing risk on-chain by efficiently integrating off-chain identity- and attribute- verification and on-chain transaction activity. We achieve this while preserving individual privacy within a competitive and fair environment and retaining compatibility with existing platforms such as Ethereum. Even though blockchains are inherently public, our solution gives users control over release of information that pertains to them. Consequently, our contribution focuses on customized methods that balance the degree of disclosure of provably-sourced user information against the likelihood of the user successfully gaining access to a desired resource, such as a loan under suitable terms. Our solution is consistent with the zero-trust model in that it imports explicit trust from recognized sources through relevant metrics that are subject to continuous update.
## 2023/1191
* Title: Attribute-Based Multi-Input FE (and more) for Attribute-Weighted Sums
* Authors: Shweta Agrawal, Junichi Tomida, Anshu Yadav
* [Permalink](https://eprint.iacr.org/2023/1191)
* [Download](https://eprint.iacr.org/2023/1191.pdf)
### Abstract
Recently, Abdalla, Gong and Wee (Crypto 2020) provided the first functional encryption scheme for attribute-weighted sums (AWS), where encryption takes as input $N$ (unbounded) attribute-value pairs $\{\vec{x}_i, \vec{z}_i\}_{I \in [N]}$ where $\vec{x}_i$ is public and $\vec{z}_i$ is private, the secret key is associated with an arithmetic branching programs $f$, and decryption returns the weighted sum ${\sum}_{{i \in [N]}} f(\vec{x}_i)^\top \vec{z}_i$, leaking no additional information about the $\vec{z}_i$'s.
We extend FE for AWS to the significantly more challenging multi-party setting and provide the first construction for {\it attribute-based} multi-input FE (MIFE) supporting AWS. For $i \in [n]$, encryptor $i$ can choose an attribute $\vec{y}_i$ together with AWS input $\{\vec{x}_{i,j}, \vec{z}_{i,j}\}$ where $j \in [N_i]$ and $N_i$ is unbounded, the key generator can choose an access control policy $g_i$ along with its AWS function $h_i$ for each $i \in [n]$, and the decryptor can compute
$$\sum_{i \in [n]}\sum_{j \in [N_{i}]}h_{i}(\vec{x}_{i,j})^{\top}\vec{z}_{i,j} \text{ iff } g_{i}(\vec{y}_{i}) =0 \text{ for all } i \in [n]$$
Previously, the only known attribute based MIFE was for the inner product functionality (Abdalla et al.~Asiacrypt 2020), where additionally, $\vec{y}_i$ had to be fixed during setup and must remain the same for all ciphertexts in a given slot.
Our attribute based MIFE implies the notion of multi-input {\it attribute based encryption} (\miabe) recently studied by Agrawal, Yadav and Yamada (Crypto 2022) and Francati, Friolo, Malavolta and Venturi (Eurocrypt 2023), for a conjunction of predicates represented as arithmetic branching programs (ABP).
Along the way, we also provide the first constructions of multi-client FE (MCFE) and dynamic decentralized FE (DDFE) for the AWS functionality. Previously, the best known MCFE and DDFE schemes were for inner products (Chotard et al.~ePrint 2018, Abdalla, Benhamouda and Gay, Asiacrypt 2019, and Chotard et al.~Crypto 2020).
Our constructions are based on pairings and proven selectively secure under the matrix DDH assumption.
## 2023/1192
* Title: CycleFold: Folding-scheme-based recursive arguments over a cycle of elliptic curves
* Authors: Abhiram Kothapalli, Srinath Setty
* [Permalink](https://eprint.iacr.org/2023/1192)
* [Download](https://eprint.iacr.org/2023/1192.pdf)
### Abstract
This paper introduces CycleFold, a new and conceptually simple approach to instantiate folding-scheme-based recursive arguments over a cycle of elliptic curves, for the purpose of realizing incrementally verifiable computation (IVC). Existing approach to solve this problem originates from BCTV (CRYPTO'14) who describe their approach for a SNARK-based recursive argument, and it was adapted by Nova (CRYPTO'22) to a folding-scheme-based recursive argument. A downside of this approach is that it represents a folding scheme verifier as a circuit on both curves in the cycle. (e.g., with Nova, this requires $\approx$10,000 multiplication gates on both curves in the cycle).
CycleFold’s starting point is the observation that folding-scheme-based recursive arguments can be efficiently instantiated without a cycle of elliptic curves—except for a few scalar multiplications in their verifiers (2 in Nova, 1 in HyperNova, and 3 in ProtoStar). Accordingly, CycleFold uses the second curve in the cycle to merely represent a single scalar multiplication ($\approx$1,000--1,500 multiplication gates). CycleFold then folds invocations of that tiny circuit on the first curve in the cycle. This is nearly an order of magnitude improvement over the prior state-of-the-art in terms of circuit sizes on the second curve. CycleFold is particularly beneficial when instantiating folding-scheme-based recursive arguments over “half pairing” cycles (e.g., BN254/Grumpkin) as it keeps the circuit on the non-pairing-friendly curve minimal. The running instance in a CycleFold-based recursive argument consists of an instance on the first curve and a tiny instance on the second curve. Both instances can be proven using a zkSNARK defined over the scalar field of the first curve.
On the conceptual front, with CycleFold, an IVC construction and nor its security proof has to explicitly reason about the cycle of elliptic curves. Finally, due to its simplicity, CycleFold-based recursive argument can be more easily be adapted to support parallel proving with the so-called "binary tree" IVC.
## 2023/1193
* Title: An Anonymous Authenticated Key Agreement Protocol Secure in Partially Trusted Registration Server Scenario for Multi-Server Architectures
* Authors: Inam ul Haq, Jian Wang, Youwen Zhu, Sheharyar Nasir
* [Permalink](https://eprint.iacr.org/2023/1193)
* [Download](https://eprint.iacr.org/2023/1193.pdf)
### Abstract
The accelerated advances in information communication technologies have made it possible for enterprises to deploy large scale applications in a multi-server architecture (also known as cloud computing environment). In this architecture, a mobile user can remotely obtain desired services over the Internet from multiple servers by initially executing a single registration on a trusted registration server (RS). Due to the hazardous nature of the Internet, to protect user privacy and online communication, a lot of multi-server authenticated-key-agreement (MSAKA) schemes have been furnished. However, all such designs lack in two very vital aspects, i.e., 1) no security under the partially trusted RS and 2) RS cannot control a user to access only a wanted combination of service-providing servers. To address these shortcomings, we present a new MSAKA protocol using self-certified public-key cryptography (SCPKC). We confirm the security of the proposed scheme by utilizing the well-known automated verification tool AVISPA and also provide a formal security proof in the random oracle model. Moreover, the software implementation of the proposed scheme, and a performance and security metrics comparison shows that it portrays a better security performance trade-off, and hence is more appropriate for real-life applications having resource constraint devices.
## 2023/1194
* Title: HI-Kyber: A novel high-performance implementation scheme of Kyber based on GPU
* Authors: Xinyi Ji, Jiankuo Dong, Pinchang Zhang, Deng Tonggui, Hua Jiafeng, Fu Xiao
* [Permalink](https://eprint.iacr.org/2023/1194)
* [Download](https://eprint.iacr.org/2023/1194.pdf)
### Abstract
CRYSTALS-Kyber, as the only public key encryption (PKE) algorithm selected by the National Institute of Standards and Technology (NIST) in the third round, is considered one of the most promising post-quantum cryptography (PQC) schemes. Lattice-based cryptography uses complex discrete alogarithm problems on lattices to build secure encryption and decryption systems to resist attacks from quantum computing. Performance is an important bottleneck affecting the promotion of post quantum cryptography. In this paper, we present a High-performance Implementation of Kyber (named HI-Kyber) on the NVIDIA GPUs, which can increase the key-exchange performance of Kyber to the million-level. Firstly, we propose a lattice-based PQC implementation architecture based on kernel fusion, which can avoid redundant global-memory access operations. Secondly, We optimize and implement the core operations of CRYSTALS-Kyber, including Number Theoretic Transform (NTT), inverse NTT (INTT), pointwise multiplication, etc. Especially for the calculation bottleneck NTT operation, three novel methods are proposed to explore extreme performance: the sliced layer merging (SLM), the sliced depth-first search (SDFS-NTT) and the entire depth-first search (EDFS-NTT), which achieve a speedup of 7.5%, 28.5%, and 41.6% compared to the native implementation. Thirdly, we conduct comprehensive performance experiments with different parallel dimensions based on the above optimization. Finally, our key exchange performance reaches 1,664 kops/s. Specifically, based on the same platform, our HI-Kyber is 3.52$\times$ that of the GPU implementation based on the same instruction set and 1.78$\times$ that of the state-of-the-art one based on AI-accelerated tensor core.
## 2023/1195
* Title: PicoEMP: A Low-Cost EMFI Platform Compared to BBI and Voltage Fault Injection using TDC and External VCC Measurements
* Authors: Colin O'Flynn
* [Permalink](https://eprint.iacr.org/2023/1195)
* [Download](https://eprint.iacr.org/2023/1195.pdf)
### Abstract
Electromagnetic Fault Injection (EMFI) has been demonstrated to be useful for both academic and industrial research. Due to the dangerous voltages involved, most work is done with commercial tools. This paper introduces a safety-focused low-cost and open-source design that can be built for less than \$50 using only off-the-shelf parts.
The paper also introduces an iCE40 based Time-to-Digital Converter (TDC), which is used to visualize the glitch inserted by the EMFI tool. This demonstrates the internal voltage perturbations between voltage, body biasing injection (BBI), and EMFI all result in similar waveforms. In addition, a link between an easy-to-measure external voltage measurement and the internal measurement is made. Attacks are also made on a hardware AES engine, and a soft-core RISC-V processor, all running on the same iCE40 FPGA.
The platform is used to demonstrate several aspects of fault injection, including that the spatial positioning of the EMFI probe can impact the glitch strength, and that the same physical device may require widely different glitch parameters when running different designs.
## 2023/1196
* Title: A New Paradigm for Verifiable Secret Sharing
* Authors: Sourav Das, Zhuolun Xiang, Alin Tomescu, Alexander Spiegelman, Benny Pinkas, Ling Ren
* [Permalink](https://eprint.iacr.org/2023/1196)
* [Download](https://eprint.iacr.org/2023/1196.pdf)
### Abstract
Verifiable Secret Sharing (VSS) is a fundamental building block in cryptography. Despite its importance and extensive studies, existing VSS protocols are often complex and inefficient. Many of them do not support dual threads, are not publicly verifiable, or do not properly terminate in asynchronous networks. In this paper, we present a new and simple paradigm for designing VSS protocols in synchronous and asynchronous networks. Our VSS protocols are optimally fault-tolerant, i.e., they tolerate a 1/2 and a 1/3 fraction of malicious nodes in synchronous and asynchronous networks, respectively. They only require a public key infrastructure and the hardness of discrete logarithms. Our protocols support dual thresholds and their transcripts are publicly verifiable. We implement our VSS protocols and measure their computation and communication costs with up to 1024 nodes. Our evaluation illustrates that our VSS protocols provide asynchronous termination and public verifiability with minimum performance overhead. Compared to the existing VSS protocol with similar guarantees, our protocols are 5-15× and 8-13× better in computation and communication cost, respectively.
## 2023/1197
* Title: Towards a Quantum-resistant Weak Verifiable Delay Function
* Authors: Thomas Decru, Luciano Maino, Antonio Sanso
* [Permalink](https://eprint.iacr.org/2023/1197)
* [Download](https://eprint.iacr.org/2023/1197.pdf)
### Abstract
In this paper, we present a new quantum-resistant weak Verifiable Delay Function based on a purely algebraic construction. Its delay depends on computing a large-degree isogeny between elliptic curves, whereas its verification relies on the computation of isogenies between products of two elliptic curves. One of its major advantages is its expected fast verification time. However, it is important to note that the practical implementation of our theoretical framework poses significant challenges. We examine the strengths and weaknesses of our construction, analyze its security and provide a proof-of-concept implementation.
## 2023/1198
* Title: Towards Achieving Provable Side-Channel Security in Practice
* Authors: Sonia Belaïd, Gaëtan Cassiers, Camille Mutschler, Matthieu Rivain, Thomas Roche, François-Xavier Standaert, Abdul Rahman Taleb
* [Permalink](https://eprint.iacr.org/2023/1198)
* [Download](https://eprint.iacr.org/2023/1198.pdf)
### Abstract
Physical side-channel attacks are powerful attacks that exploit a device's physical emanations to break the security of cryptographic implementations. Many countermeasures have been proposed against these attacks, especially the widely-used and efficient masking countermeasure. Nevertheless, proving the security of masked implementations is challenging. Current techniques rely on empirical approaches to validate the security of such implementations. On the other hand, the theoretical community introduced leakage models to provide formal proofs of the security of masked implementations. Meanwhile, these leakage models rely on physical assumptions that are difficult to satisfy in practice, and the literature lacks a clear framework to implement proven secure constructions on a physical device while preserving the proven security.
In this paper, we present a complete methodology describing the steps to turn an abstract masking scheme proven secure in a theoretical leakage model into a physical implementation satisfying provable security against side-channel attacks in practice. We propose new tools to enforce or relax the physical assumptions the indeal noisy leakage model rely on and provide novel ways of including them in a physical implementation. We also highlight the design goals for an embedded device to reach high levels of proven security, discussing the limitations and open problems of the practical usability of the leakage models. Our goal is to show that it is possible to bridge theory and practice and to motivate further research to fully close the gap and get practical implementations proven secure against side-channel attacks on a physical device without any ideal assumption about the leakage.
## 2023/1199
* Title: RSA Blind Signatures with Public Metadata
* Authors: Ghous Amjad, Kevin Yeo, Moti Yung
* [Permalink](https://eprint.iacr.org/2023/1199)
* [Download](https://eprint.iacr.org/2023/1199.pdf)
### Abstract
Anonymous tokens are digital signature schemes that enable an issuer to provider users with signatures without learning the input message or the resulting signature received by the user. These primitives allow applications to propagate trust while simultaneously protecting the identity of the user. Anonymous tokens have become a core component for improving the privacy of several real-world applications including ad measurements, authorization protocols, spam detection and VPNs.
In certain applications, it is natural to associate signatures with specific public metadata ensuring that signatures only propagate trust with respect to only a certain set of scenarios. To solve this, we study the notion of anonymous tokens with public metadata in this work. We present a variant of RSA blind signatures with public metadata such that issuers may only generate signatures that verify for a certain choice of public metadata. We prove the security of our protocol under one-more RSA assumptions with multiple exponents that we introduce. Furthermore, we provide evidence that the concrete security bounds should be nearly identical to standard RSA blind signatures. The protocols in this paper have been proposed as a technical specification in an IRTF internet draft.
## 2023/1200
* Title: Shining Light on the Shadow: Full-round Practical Distinguisher for Lightweight Block Cipher Shadow
* Authors: Sunyeop Kim, Myoungsu Shin, Seonkyu Kim, Hanbeom Shin, Insung Kim, Donggeun Kwon, Dongjae Lee, Seonggyeom Kim, Deukjo Hong, Jaechul Sung, Seokhie Hong
* [Permalink](https://eprint.iacr.org/2023/1200)
* [Download](https://eprint.iacr.org/2023/1200.pdf)
### Abstract
Shadow is a lightweight block cipher proposed at IEEE IoT journal 2021. Shadow’s main design principle is adopting a variant 4- branch Feistel structure in order to provide a fast diffusion rate. We define such a structure as Shadow structure and prove that it is al- most identical to the Generalized Feistel Network, which invalidates the design principle. Moreover, we give a structural distinguisher that can distinguish Shadow structure from random permutation with only two plaintext/ciphertext pairs. By exploiting the key schedule, the distin- guisher can be extended to key recovery attack with only one plain- text/ciphertext pair. Furthermore, by considering Shadow’s round func- tion, only certain forms of monomials can appear in the ciphertext, re- sulting in an integral distinguisher of four plaintext/ciphertext pairs. Even more, the algebraic degree does not increase more than 12 for Shadow-32 and 20 for Shadow-64 regardless of rounds used. Our results show that Shadow is highly vulnerable to algebraic attacks, and that algebraic attacks should be carefully considered when designing ciphers with AND, rotation, and XOR operations.
## 2023/1201
* Title: Privacy-preserving edit distance computation using secret-sharing two-party computation
* Authors: Hernán Darío Vanegas Madrigal, Daniel Cabarcas Jaramillo, Diego F. Aranha
* [Permalink](https://eprint.iacr.org/2023/1201)
* [Download](https://eprint.iacr.org/2023/1201.pdf)
### Abstract
The edit distance is a metric widely used in genomics to measure the similarity of two DNA chains. Motivated by privacy concerns, we propose a 2PC protocol to compute the edit distance while preserving the privacy of the inputs. Since the edit distance algorithm can be expressed as a mixed-circuit computation, our approach uses protocols based on secret-sharing schemes like Tinier and SPD$\mathbb{Z}_{2^k}$; and also daBits to perform domain conversion and edaBits to perform arithmetic comparisons. We modify the Wagner-Fischer edit distance algorithm, aiming at reducing the number of rounds of the protocol, and achieve a flexible protocol with a trade-off between rounds and multiplications. We implement our proposal in the MP-SPDZ framework, and our experiments show that it reduces the execution time respectively by 81\% and 54\% for passive and active security with respect to a baseline implementation in a LAN. The experiments also show that our protocol reduces traffic by two orders of magnitude compared to a BMR-MASCOT implementation.
## 2023/1202
* Title: Extension of Shannon's theory of ciphers based on Latin rectangles
* Authors: Karel BURDA
* [Permalink](https://eprint.iacr.org/2023/1202)
* [Download](https://eprint.iacr.org/2023/1202.pdf)
### Abstract
The paper extends Shannon's classical theory of ciphers. Here ciphers are modeled by Latin rectangles and their resistance to brute force attack is assessed through the valence of cryptograms. The valence of a cryptogram is defined as the number of all meaningful messages produced by decrypting the cryptogram with all possible keys. In this paper, the mean cryptogram valence of an arbitrary modern cipher with K keys, N outputs and N inputs, of which M inputs are messages, is derived. Furthermore, the lower bound on the valence of the cryptograms of entire ciphers is derived in this paper. The obtained parameters allow to assess the resistance of cryptograms, resp. ciphers against brute force attack. The model is general, illustrative and uses a simpler mathematical apparatus than existing theory. Therefore, it can also be used as an introduction to the theory of resistance of ciphers to brute force attack.
## 2023/1203
* Title: Collaborative Privacy-Preserving Analysis of Oncological Data using Multiparty Homomorphic Encryption
* Authors: Ravit Geva, Alexander Gusev, Yuriy Polyakov, Lior Liram, Oded Rosolio, Andreea Alexandru, Nicholas Genise, Marcelo Blatt, Zohar Duchin, Barliz Waissengrin, Dan Mirelman, Felix Bukstein, Deborah T. Blumenthal, Ido Wolf, Sharon Pelles-Avraham, Tali Schaffer, Lee A. Lavi, Daniele Micciancio, Vinod Vaikuntanathan, Ahmad Al Badawi, Shafi Goldwasser
* [Permalink](https://eprint.iacr.org/2023/1203)
* [Download](https://eprint.iacr.org/2023/1203.pdf)
### Abstract
Real-world healthcare data sharing is instrumental in constructing broader-based and larger clinical data sets that may improve clinical decision-making research and outcomes. Stakeholders are frequently reluctant to share their data without guaranteed patient privacy, proper protection of their data sets, and control over the usage of their data. Fully homomorphic encryption (FHE) is a cryptographic capability that can address these issues by enabling computation on encrypted data without intermediate decryptions, so the analytics results are obtained without revealing the raw data. This work presents a toolset for collaborative privacy-preserving analysis of oncological data using multiparty FHE. Our toolset supports survival analysis, logistic regression training, and several common descriptive statistics. We demonstrate using oncological data sets that the toolset achieves high accuracy and practical performance, which scales well to larger data sets. As part of this work, we propose a novel cryptographic protocol for interactive bootstrapping in multiparty FHE, which is of independent interest. The toolset we develop is general-purpose and can be applied to other collaborative medical and healthcare application domains.
## 2023/1204
* Title: On Fully-Secure Honest Majority MPC without $n^2$ Round Overhead
* Authors: Daniel Escudero, Serge Fehr
* [Permalink](https://eprint.iacr.org/2023/1204)
* [Download](https://eprint.iacr.org/2023/1204.pdf)
### Abstract
Fully secure multiparty computation (or guaranteed output delivery) among $n$ parties can be achieved with perfect security if the number of corruptions $t$ is less than $n/3$, or with statistical security with the help of a broadcast channel if $t<n/2$. In the case of $t<n/3$, it is known that it is possible to achieve linear communication complexity, but at a cost of having a round count of $\Omega(\mathsf{depth}(C) + n)$ in the worst case. The number of rounds can be reduced to $O(\mathsf{depth}(C))$ by either increasing communication, or assuming some correlated randomness (a setting also known as the preprocesing model). For $t<n/2$ it is also known that linear communication complexity is achievable, but at the cost of $\Omega(\mathsf{depth}(C) + n^2)$ rounds, due to the use of a technique called dispute control. However, in contrast to the $t<n/3$ setting, it is not known how to reduce this round count for $t<n/2$ to $O(\mathsf{depth}(C))$, neither allowing for larger communication, or by using correlated randomness.
In this work we make progress in this direction by taking the second route above: we present a fully secure protocol for $t<n/2$ in the preprocessing model, that achieves linear communication complexity, and whose round complexity is only $O(\mathsf{depth}(C))$, without the additive $n^2$ term that appears from the use of dispute control. While on the $t<n/3$ such result requires circuits of width $\Omega(n)$, in our case circuits must be of width $\Omega(n^2)$, leaving it as an interesting future problem to reduce this gap. Our $O(\mathsf{depth}(C))$ round count is achieved by avoiding the use of dispute control entirely, relying on a different tool for guaranteeing output. In the $t<n/3$ setting when correlated randomness is available, this is done by using error correction to reconstruct secret-shared values, but in the $t<n/2$ case the equivalent is robust secret-sharing, which guarantees the reconstruction of a secret in spite of errors. However, we note that a direct use of such tool would lead to \emph{quadratic} communication, stemming from the fact that each party needs to authenticate their share towards each other party. At the crux of our techniques lies a novel method for reconstructing a batch of robustly secret-shared values while involving only a linear amount of communication per secret, which may also be of independent interest.
## 2023/1205
* Title: On the security of REDOG
* Authors: Tanja Lange, Alex Pellegrini, Alberto Ravagnani
* [Permalink](https://eprint.iacr.org/2023/1205)
* [Download](https://eprint.iacr.org/2023/1205.pdf)
### Abstract
We analyze REDOG, a public-key encryption system submitted to the Korean
competition on post-quantum cryptography.
REDOG is based on rank-metric codes. We prove its incorrectness and attack its
implementation providing an efficient message recovery attack. Furthermore, we
show that the security of REDOG is much lower than claimed. We then
proceed to mitigate these issues and provide two approaches to fix the
decryption issue, one of which also leads to better security.
## 2023/1206
* Title: Decentralized Threshold Signatures for Blockchains with Non-Interactive and Transparent Setup
* Authors: Kwangsu Lee
* [Permalink](https://eprint.iacr.org/2023/1206)
* [Download](https://eprint.iacr.org/2023/1206.pdf)
### Abstract
Threshold signatures are digital signatures that support the multi-party signature generation such that a number of parties initially share a signing key and more than a threshold number of parties gather to generate a signature. In this paper, we propose a non-interactive decentralized threshold signature (NIDTS) scheme that supports the non-interactive and transparent key setup based on BLS signatures. Our NIDTS scheme has the following properties. 1) The key setup process is completely non-interactive and does not require message exchange between parties since the transfer of the register keys of parties is enough for a combiner to generate a compact verification key. 2) The register key of a party is compact since the size is independent of the number of group parties. 3) The signing process of parties is non-interactive. 4) The final threshold signature as well as partial signatures are succinct.
We prove the security of our NIDTS scheme under computational assumptions in the random oracle model. Furthermore, we implement our NIDTS scheme in Rust and compare its performance with other scheme to show that the key setup of our scheme is more efficient. For example, in the unweighted setting of 1000 parties, the key setup process of the NIDTS scheme takes 164 seconds, which is 5.9 times faster than the key setup process of the multiverse threshold signature (MTS) scheme.
## 2023/1207
* Title: DeFi Auditing: Mechanisms, Effectiveness, and User Perceptions
* Authors: Ding Feng, Rupert Hitsch, Kaihua Qin, Arthur Gervais, Roger Wattenhofer, Yaxing Yao, Ye Wang
* [Permalink](https://eprint.iacr.org/2023/1207)
* [Download](https://eprint.iacr.org/2023/1207.pdf)
### Abstract
Decentralized Finance (DeFi), a blockchain-based financial ecosystem, suffers from smart contract vulnerabilities that led to a loss exceeding 3.24 billion USD by April 2022. To address this, blockchain firms audit DeFi applications, a process known as DeFi auditing. Our research aims to comprehend the mechanism and efficacy of DeFi auditing. We discovered its ability to detect vulnerabilities in smart contract logic and interactivity with other DeFi entities, but also noted its limitations in communication, transparency, remedial action implementation, and in preventing certain DeFi attacks. Moreover, our interview study delved into user perceptions of DeFi auditing, unmasking gaps in awareness, usage, and trust, and offering insights to address these issues.
## 2023/1208
* Title: Mutator Sets and their Application to Scalable Privacy
* Authors: Alan Szepieniec, Thorkil Værge
* [Permalink](https://eprint.iacr.org/2023/1208)
* [Download](https://eprint.iacr.org/2023/1208.pdf)
### Abstract
A mutator set is a cryptographic data structure for authenticating operations on a changing set of data elements called items. Informally:
- There is a short commitment to the set.
- There are succinct membership proofs for elements of the set.
- It is possible to update the commitment as well as the membership proofs with minimal effort as new items are added to the set or as existing items are removed from it.
- Items cannot be removed before they were added.
- It is difficult to link an item's addition to the set to its removal from the set, except when using information available only to the party that generated it.
This paper formally defines the notion, motivates its existence with an application to scalable privacy in the context of cryptocurrencies, and proposes an instantiation inspired by Merkle mountain ranges and Bloom filters.
## 2023/1209
* Title: Infinite families of minimal binary codes via Krawtchouk polynomials
* Authors: Xiaoni Du, René Rodríguez, Hao Wu
* [Permalink](https://eprint.iacr.org/2023/1209)
* [Download](https://eprint.iacr.org/2023/1209.pdf)
### Abstract
Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, the general Maiorana-McFarland class. We employ a method first proposed by Ding et al. [7] to construct minimal codes violating the Ashikhmin-Barg bound (wide minimal codes) by using Krawtchouk polynomials. The lengths, dimensions, and weight distributions of the obtained codes are determined using the Walsh spectrum distribution of the chosen Boolean functions. Our findings demonstrate that a vast majority of the newly constructed codes are wide minimal codes. Furthermore, our proposed codes exhibit a significantly larger minimum distance, in some cases, compared to some existing similar constructions. Finally, we address this method, based on Krawtchouk polynomials, more generally, and highlight certain generic properties related to it. This study provides insights into the scope of this method.
## 2023/1210
* Title: Decentralized Finance (DeFi): A Survey
* Authors: Erya Jiang, Bo Qin, Qin Wang, Zhipeng Wang, Qianhong Wu, Jian Weng, Xinyu Li, Chenyang Wang, Yuhang Ding, Yanran Zhang
* [Permalink](https://eprint.iacr.org/2023/1210)
* [Download](https://eprint.iacr.org/2023/1210.pdf)
### Abstract
Decentralized Finance (DeFi) is a new paradigm in the creation, distribution, and utilization of financial services via the integration of blockchain technology. Our research conducts a comprehensive introduction and meticulous classification of various DeFi applications. Beyond that, we thoroughly analyze these risks from both technical and economic perspectives, spanning multiple layers. Lastly, we point out research directions in DeFi, encompassing areas of technological advancements, innovative economics, and privacy optimization.
## 2023/1211
* Title: Optimal Flexible Consensus and its Application to Ethereum
* Authors: Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse
* [Permalink](https://eprint.iacr.org/2023/1211)
* [Download](https://eprint.iacr.org/2023/1211.pdf)
### Abstract
Classic BFT consensus protocols guarantee safety and liveness for all clients if fewer than one-third of replicas are faulty. However, in applications such as high-value payments, some clients may want to prioritize safety over liveness. Flexible consensus allows each client to opt for a higher safety resilience, albeit at the expense of reduced liveness resilience. We present the first construction that allows optimal safety--liveness tradeoff for every client simultaneously. This construction is modular and is realized as an add-on applied on top of an existing consensus protocol. The add-on consists of an additional round of voting and permanent locking done by the replicas, to sidestep a sub-optimal quorum-intersection-based constraint present in previous solutions. We adapt our construction to the existing Ethereum protocol to derive optimal flexible confirmation rules that clients can adopt unilaterally without requiring system-wide changes. This is possible because existing Ethereum protocol features can double as the extra voting and locking. We demonstrate an implementation using Ethereum's consensus API.
## 2023/1212
* Title: CLRW1$^{3}$ is not Secure Beyond the Birthday Bound: Breaking TNT with ${O(2^{n/2})}$ queries
* Authors: Mustafa Khairallah
* [Permalink](https://eprint.iacr.org/2023/1212)
* [Download](https://eprint.iacr.org/2023/1212.pdf)
### Abstract
In this paper, we present a new distinguisher for the Tweak-aNd-Tweak (TNT) tweakable block cipher with $O(2^{n/2})$ complexity. The distinguisher is an adaptive chosen ciphertext distinguisher, unlike previous attacks that are only non-adaptive chosen plaintext attacks. However, the attack contradicts the security claims made by the designers. Given TNT can be seen as the three-round CLRW1 tweakable block cipher, our attack matches its more conservative bound. We provide the distinguisher description, a probabilistic analysis of its behaviour, experimental verification and an analysis of why the proof fails to capture the security of TNT. In summary, the distinguisher is based on collision counting and exploits non-uniformity in the statistical behaviour of random permutations. It reduces the goal of finding the collision to solving a difference equation defined over a random permutation. Due to this relation, the number of collisions observed by the distinguisher is twice as expected from an ideal tweakable block cipher.
## 2023/1213
* Title: Fallen Sanctuary: A Higher-Order and Leakage-Resilient Rekeying Scheme
* Authors: Rei Ueno, Naofumi Homma, Akiko Inoue, Kazuhiko Minematsu
* [Permalink](https://eprint.iacr.org/2023/1213)
* [Download](https://eprint.iacr.org/2023/1213.pdf)
### Abstract
This paper presents a provably secure, higher-order, and leakage-resilient
(LR) rekeying scheme named LR Rekeying with Random oracle Repetition (LR4), along with a quantitative security evaluation methodology. Many existing LR cryptographies are based on a concept of leveled implementation, which still essentially require a leak-free sanctuary (i.e., differential power analysis (DPA)-resistant component(s)) for some parts. In addition, although several LR pseudorandom functions (PRFs) based on only bounded DPA-resistant components have been developed, their validity and effectiveness for rekeying usage still need to be determined. In contrast, LR4 is formally proven under a leakage model that captures the practical goal of side-channel attack (SCA) protection (e.g., masking with a practical order) and assumes no unbounded DPA-resistant sanctuary. This proof suggests that LR4 resists exponential invocations (up to the birthday bound of key size) without using any unbounded leak-free component, which is the first of its kind. Moreover, we present a quantitative SCA success rate evaluation methodology for LR4 that combines the bounded leakage models for LR cryptography and a state-of-the-art information-theoretical SCA evaluation method. We validate its soundness and effectiveness as a DPA countermeasure through a numerical evaluation; that is, the number of secure calls of a symmetric primitive increases exponentially by increasing a security parameter under practical conditions.
## 2023/1214
* Title: Verifiable Verification in Cryptographic Protocols
* Authors: Marc Fischlin, Felix Günther
* [Permalink](https://eprint.iacr.org/2023/1214)
* [Download](https://eprint.iacr.org/2023/1214.pdf)
### Abstract
Common verification steps in cryptographic protocols, such as signature or message authentication code checks or the validation of elliptic curve points, are crucial for the overall security of the protocol. Yet implementation errors omitting these steps easily remain unnoticed, as often the protocol will function perfectly anyways. One of the most prominent examples is Apple's goto fail bug where the erroneous certificate verification skipped over several of the required steps, marking invalid certificates as correctly verified. This vulnerability went undetected for at least 17 months.
We propose here a mechanism which supports the detection of such errors on a cryptographic level. Instead of merely returning the binary acceptance decision, we let the verification return more fine-grained information in form of what we call a confirmation code. The reader may think of the confirmation code as disposable information produced as part of the relevant verification steps. In case of an implementation error like the goto fail bug, the confirmation code would then miss essential elements.
The question arises now how to verify the confirmation code itself. We show how to use confirmation codes to tie security to basic functionality at the overall protocol level, making erroneous implementations be detected through the protocol not functioning properly. More concretely, we discuss the usage of confirmation codes in secure connections, established via a key exchange protocol and secured through the derived keys. If some verification steps in a key exchange protocol execution are faulty, then so will be the confirmation codes, and because we can let the confirmation codes enter key derivation, the connection of the two parties will eventually fail. In consequence, an implementation error like goto fail would now be detectable through a simple connection test.
## 2023/1215
* Title: Authentica: A Secure Authentication Mechanism using a Software-defined Unclonable Function
* Authors: Ripon Patgiri, Laiphrakpam Dolendro Singh
* [Permalink](https://eprint.iacr.org/2023/1215)
* [Download](https://eprint.iacr.org/2023/1215.pdf)
### Abstract
Password-based authentication is an extensively used method to authenticate users. It uses cryptography to communicate the authentication process. On the contrary, the physically unclonable function (PUF)-based authentication mechanism is also gaining popularity rapidly due to its usability in IoT devices. It is a lightweight authentication mechanism that does not use cryptography protocol. PUF-based authentication mechanisms cannot authenticate users. To overcome the drawback of PUF, we introduce a software-defined unclonable function (SUF, for short). Contrary to the PUF, the SUF is used to authenticate users, not devices. We use SUF to implement a lightweight password-based authentication mechanism termed Authentica. Authentica bridges the gap between the password-based and the PUF-based authentication mechanism. Authentica does not use cryptography for authentication. However, we establish challenge-response using cryptography during the registration phase, which is a one-time cost. Authentica addresses a) impersonation attacks, b) collision attacks, c) dictionary and rainbow table attacks, d) replay attacks, e) DDoS attacks, f) the domino effect issues, and g) the challenge-response database leakage issues.
## 2023/1216
* Title: Unlocking the lookup singularity with Lasso
* Authors: Srinath Setty, Justin Thaler, Riad Wahby
* [Permalink](https://eprint.iacr.org/2023/1216)
* [Download](https://eprint.iacr.org/2023/1216.pdf)
### Abstract
This paper introduces Lasso, a new family of lookup arguments, which allow an untrusted prover to commit to a vector $a \in \mathbb{F}^m$ and prove that all entries of a reside in some predetermined table $t \in \mathbb{F}^n$. Lasso’s performance characteristics unlock the so-called "lookup singularity". Lasso works with any multilinear polynomial commitment scheme, and provides the following efficiency properties.
For $m$ lookups into a table of size $n$, Lasso’s prover commits to just $m + n$ field elements. Moreover, the committed field elements are small, meaning that, no matter how big the field $\mathbb{F}$ is, they are all in the set $\{0, . . . , m\}$. When using a multiexponentiation-based commitment scheme, this results in the prover’s costs dominated by only $O(m + n)$ group operations (e.g., elliptic curve point additions), plus the cost to prove an evaluation of a multilinear polynomial whose evaluations over the Boolean hypercube are the table entries. This represents a significant improvement in prover costs over prior lookup arguments (e.g., plookup, Halo2’s lookups, lookup arguments based on logarithmic derivatives).
Unlike all prior lookup arguments, if the table $t$ is structured (in a precise sense that we define), then no party needs to commit to $t$, enabling the use of much larger tables than prior works (e.g., of size $2^{128}$ or larger). Moreover, Lasso’s prover only "pays" in runtime for table entries that are accessed by the lookup operations. This applies to tables commonly used to implement range checks, bitwise operations, big-number arithmetic, and even transitions of a full-fledged CPU such as RISC-V. Specifically, for any integer parameter $c > 1$, Lasso’s prover’s dominant cost is committing to $3 \cdot c \cdot m + c \cdot n^{1/c}$ field elements. Furthermore, all these field elements are “small”, meaning they are in the set $\{0, . . . , \max{(m, n^{1/c}, q)} − 1\}$, where $q$ is the maximum value in $a$.
Lasso’s starting point is Spark, a time-optimal polynomial commitment scheme for sparse polynomials in Spartan (CRYPTO 2020). We first provide a stronger security analysis for Spark. Spartan’s security analysis assumed that certain metadata associated with a sparse polynomial is committed by an honest party (this is acceptable for its purpose in Spartan, but not for Lasso). We prove that Spark remains secure even when that metadata is committed by a malicious party. This provides the first "standard" commitment scheme for sparse multilinear polynomials with optimal prover costs. We then generalize Spark to directly support a lookup argument for both structured and unstructured tables, with the efficiency characteristics noted above.
## 2023/1217
* Title: Jolt: SNARKs for Virtual Machines via Lookups
* Authors: Arasu Arun, Srinath Setty, Justin Thaler
* [Permalink](https://eprint.iacr.org/2023/1217)
* [Download](https://eprint.iacr.org/2023/1217.pdf)
### Abstract
Succinct Non-interactive Arguments of Knowledge (SNARKs) allow an untrusted prover to establish that it correctly ran some "witness-checking procedure" on a witness. A zkVM (short for zero-knowledge Virtual Machine) is a SNARK that allows the witness-checking procedure to be specified as a computer program written in the assembly language of a specific instruction set architecture (ISA).
A $\textit{front-end}$ converts computer programs into a lower-level representation such as an arithmetic circuit or generalization thereof. A SNARK for circuit-satisfiability can then be applied to the resulting circuit.
We describe a new front-end technique called Jolt that applies to a variety of ISAs. Jolt arguably realizes a vision called the $\textit{lookup singularity}$, which seeks to produce circuits that only perform lookups into pre-determined lookup tables. The circuits output by Jolt primarily perform lookups into a gigantic lookup table, of size more than $2^{128}$, that depends only on the ISA. The validity of the lookups are proved via a new $\textit{lookup argument}$ called Lasso described in a companion work (Setty, Thaler, and Wahby, e-print 2023). Although size-$2^{128}$ tables are vastly too large to materialize in full, the tables arising in Jolt are structured, avoiding costs that grow linearly with the table size.
We describe performance and auditability benefits of Jolt compared to prior zkVMs, focusing on the popular RISC-V ISA as a concrete example. The dominant cost for the Jolt prover applied to this ISA (on $64$-bit data types) is cryptographically committing to about six $256$-bit field elements per step of the RISC-V CPU. This compares favorably to prior zkVM provers, even those focused on far simpler VMs.
## 2023/1218
* Title: Arke: Scalable and Byzantine Fault Tolerant Privacy-Preserving Contact Discovery
* Authors: Nicolas Mohnblatt, Alberto Sonnino, Kobi Gurkan, Philipp Jovanovic
* [Permalink](https://eprint.iacr.org/2023/1218)
* [Download](https://eprint.iacr.org/2023/1218.pdf)
### Abstract
Contact discovery is a crucial component of social applications, facilitating interactions between registered contacts. This work introduces Arke, a novel approach to contact discovery that addresses the limitations of existing solutions in terms of privacy, scalability, and reliance on trusted third parties. Arke ensures the unlinkability of user interactions, mitigates enumeration attacks, and operates without single points of failure or trust. Notably, Arke is the first contact discovery system whose performance is independent of the total number of users and the first that can operate in a Byzantine setting. It achieves its privacy goals through an unlinkable handshake mechanism built on top of an identity-based non-interactive key exchange. By leveraging a custom distributed architecture, Arke forgoes the expense of consensus to achieve scalability while maintaining consistency in a Byzantine fault tolerant environment. Performance evaluations demonstrate that Arke can support enough throughput to operate at a planetary scale while maintaining sub-second latencies in a large geo-distributed setting.
## 2023/1219
* Title: A Note on “Secure Quantized Training for Deep Learning”
* Authors: Marcel Keller, Ke Sun
* [Permalink](https://eprint.iacr.org/2023/1219)
* [Download](https://eprint.iacr.org/2023/1219.pdf)
### Abstract
Keller and Sun (ICML'22) have found a gap in the accuracy between floating-point deep learning in cleartext and secure quantized deep learning using multi-party computation. We have discovered that this gap is caused by a bug in the implementation of max-pooling. In this note, we present updated figures to support this conclusion. We also add figures for another network on CIFAR-10.
## 2023/1220
* Title: Quasi-linear Masking to Protect Kyber against both SCA and FIA
* Authors: Pierre-Augustin BERTHET, Cédric Tavernier, Jean-Luc Danger, Laurent Sauvage
* [Permalink](https://eprint.iacr.org/2023/1220)
* [Download](https://eprint.iacr.org/2023/1220.pdf)
### Abstract
The recent technological advances in Post-Quantum Cryptography (PQC) rise the questions of robust implementations of new asymmetric cryptographic primitives in today’s technology. This is the case for the lattice-based CRYSTALS-Kyber algorithm which has been selected as the first NIST standard for Public Key Encryption (PKE) and Key Encapsulation Mechanisms (KEM). We have notably to make sure the Kyber implementation is resilient against physical attacks like Side-Channel Analysis (SCA) and Fault Injection Attacks (FIA). To reach this goal, we propose to use the masking countermeasure, more precisely the generic Direct Sum Masking method (DSM). By taking inspiration of a previous paper on AES, we extend the method to finite fields of characteristic prime other than 2 and even-length codes. In particular, we investigated its
application to Keccak, which is the hash-based function used in Kyber. We also provided the first masked implementation of Kyber providing both SCA and FIA resilience while not requiring any conversion between different masking methods.
Stefan Claas
Aug 14, 2023, 11:18:23 AM8/14/23
to
IACR ePrint Archive wrote:
> ## In this issue
>
> [...]
While looking around, I found this Golang (non-GPU implementation,
of Crystals-Kyber on GitHub, as CLI app written in Golang.
Problem is I can't test sign or encrypt messages, because I get an
error not using the right --algo :-(
Has anyone tried out the software and can help me, or is it a bug I
need to file?
<https://github.com/mariiatuzovska/crystals-kyber>
Regards
Stefan
> ## In this issue
>
> [...]
> 5. [2023/1194] HI-Kyber: A novel high-performance implementation ...
> [...]
of Crystals-Kyber on GitHub, as CLI app written in Golang.
Problem is I can't test sign or encrypt messages, because I get an
error not using the right --algo :-(
Has anyone tried out the software and can help me, or is it a bug I
need to file?
<https://github.com/mariiatuzovska/crystals-kyber>
Regards
Stefan
0 new messages