[continued from previous message]

Since its invention in 1978 by Rivest, Shamir and Adleman, the public key cryptosystem RSA has become a widely popular and a widely useful scheme in cryptography. Its security is related to the difficulty of factoring large integers which are the product
of two large prime numbers. For various reasons, several variants of RSA have been proposed, and some have different arithmetics such as elliptic and singular cubic curves. In 2018, Murru and Saettone proposed another variant of RSA based on the cubic
Pell curve with a modulus of the form $N=pq$. In this paper, we present a new public key cryptosystem based on the arithmetic of the cubic Pell curve with a modulus of the form $N=p^rq^s$. Its security is based on the hardness of factoring composite
integers, and on Rabin's trapdoor one way function. In the new scheme, the arithmetic operations are performed on a cubic Pell curve which is known only to the sender and the recipient of a plaintext.



## 2024/386

* Title: High-Throughput Secure Multiparty Computation with an Honest Majority in Various Network Settings
* Authors: Christopher Harth-Kitzerow, Georg Carle
* [Permalink](https://eprint.iacr.org/2024/386)
* [Download](https://eprint.iacr.org/2024/386.pdf)

### Abstract

In this work, we present novel protocols over rings for semi-honest secure three-party computation (3-PC) and malicious four-party computation (4-PC) with one corruption. Compared to state-of-the-art protocols in the same setting, our protocols require
fewer low-latency and high-bandwidth links between the parties to achieve high throughput. Our protocols also reduce the computational complexity by requiring up to 50 percent fewer basic instructions per gate. Further, our protocols achieve the
currently best-known communication complexity (3, resp. 5 elements per multiplication gate) with an optional preprocessing phase to reduce the communication complexity of the online phase to 2 (resp. 3) elements per multiplication gate.
In homogeneous network settings, i.e. all links between the parties share similar network bandwidth and latency, our protocols achieve up to two times higher throughput than state-of-the-art protocols.
In heterogeneous network settings, i.e. all links between the parties share different network bandwidth and latency, our protocols achieve even larger performance improvements.
We implemented our protocols and multiple other state-of-the-art protocols (Replicated 3-PC, Astra, Fantastic Four, Tetrad) in a novel open-source C++ framework optimized for achieving high throughput.
Five out of six implemented 3-PC and 4-PC protocols achieve more than one billion 32-bit multiplication or more than 32 billion AND gates per second using our implementation in a 25 Gbit/s LAN environment.
This is the highest throughput achieved in 3-PC and 4-PC so far and between two and three orders of magnitude higher than the throughput MP-SPDZ achieves in the same settings.



## 2024/387

* Title: Parallel Zero-knowledge Virtual Machine
* Authors: Wenqing Hu, Tianyi Liu, Ye Zhang, Yuncong Zhang, Zhenfei Zhang
* [Permalink](https://eprint.iacr.org/2024/387)
* [Download](https://eprint.iacr.org/2024/387.pdf)

### Abstract

Zero-knowledge virtual machine (zkVM) is a novel applica-
tion of succinct and non-interactive zero-knowledge proof protocols that
allows for verifiable computation over arbitrary codes. In this paper, we present a new paradigm to build such a zkVM via data parallel circuits.
Our parallelization happens at the opcode and the basic block level.
Such a design allows us to eliminate almost all of the circuit overhead
for opcodes, including the control flow and the data flow which can be substantial in a zero-knowledge circuit. The size of our circuit is dynamic
and optimal in the sense that it only costs the sum of all individual op-
codes that are executed in the program, (i.e., you only pay as much as
you use); while in all previous designs, the circuit is of a constant size, de- termined by the product of a) the upper limit of the number of opcodes,
and b) the size of a super opcode circuit that is capable of handling every type of opcode.
Further, we present an asymmetric GKR prover that is tailored to the
data parallelism in our zkVM design, accompanied by various optimized constraint gadgets. The use of GKR prover also leads to significant re- ductions in the number of witnesses that are to be committed: GKR
allows us to commit only the input and output of the circuits, whereas
in previous Plonkish-based solutions, the prover needs to commit to all
the witnesses



## 2024/388

* Title: Leakage-Resilient Attribute-Based Encryption with Attribute-Hiding
* Authors: Yijian Zhang, Yunhao Ling, Jie Chen, Luping Wang
* [Permalink](https://eprint.iacr.org/2024/388)
* [Download](https://eprint.iacr.org/2024/388.pdf)

### Abstract

In this work, we present two generic frameworks for leakage-resilient attribute-based encryption (ABE), which is an improved version of ABE that can be proven secure even when part of the secret key is leaked. Our frameworks rely on the standard
assumption ($k$-Lin) over prime-order groups. The first framework is designed for leakage-resilient ABE with attribute-hiding in the bounded leakage model. Prior to this work, no one had yet derived a generic leakage-resilient ABE framework with
attribute-hiding. The second framework provides a generic method to construct leakage-resilient ABE in the continual leakage model. It is compatible with Zhang et al.'s work [DCC 2018] but more generic. Concretely, Zhang et al.'s framework cannot act on
some specific ABE schemes while ours manages to do that. Technically, our frameworks are built on the predicate encoding of Chen et al.'s [EUROCRYPT 2015] combined with a method of adding redundancy. At last, several instantiations are derived from our
frameworks, which cover the cases of zero inner-product predicate and non-zero inner-product predicate.



## 2024/389

* Title: On the Feasibility of Sliced Garbling
* Authors: Tomer Ashur, Carmit Hazay, Rahul Satish
* [Permalink](https://eprint.iacr.org/2024/389)
* [Download](https://eprint.iacr.org/2024/389.pdf)

### Abstract

Garbling schemes are one of the most fundamental objects in cryptography and have been studied extensively due to their broad applicability. The state-of-the-art is a construction in which XOR gates are free and AND gates require $3\kappa/2+\mathcal{O}(1)
$ bits per gate, due to Rosulek and Roy (CRYPTO'21). An important technique in their garbling is slicing, which partitions the labels into two equal-length slices. In this paper, we explore the feasibility of the slicing technique for garbling schemes
beyond the results introduced by Rosulek and Roy, demonstrating both its potential and its limitations.

In particular, we extend this technique to demonstrate the garbling of certain higher fan-in gadgets, and then use this to show that it is possible to garble 2-input AND gates at a cost of $4\kappa/3 +\mathcal{O}(1)$ bits. We then give a separation
result showing that sliced garbling cannot be used to garble higher fan-in gadgets of degree $\geq 3$ when restricted to making queries that are linear functions of the input labels to the random oracle. We further demonstrate the usefulness of our
techniques in the context of oblivious garbling, a newly introduced concept for capturing circuit hiding from the garbler. The complexity of our construction is superior to that of universal circuits, and grows linearly with circuit size.



## 2024/390

* Title: STIR: Reed–Solomon Proximity Testing with Fewer Queries
* Authors: Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2024/390)
* [Download](https://eprint.iacr.org/2024/390.pdf)

### Abstract

We present STIR (Shift To Improve Rate), an interactive oracle proof of proximity (IOPP) for Reed-Solomon codes that achieves the best known query complexity of any concretely efficient IOPP for this problem. For $\lambda$ bits of security, STIR has
query complexity $O(\log d + \lambda \cdot \log \log d )$, while FRI, a popular protocol, has query complexity $O(\lambda \cdot \log d )$ (including variants of FRI based on conjectured security assumptions). STIR relies on a new technique for
recursively improving the rate of the tested Reed-Solomon code.

We provide an implementation of STIR compiled to a SNARK. Compared to a highly-optimized implementation of FRI, STIR achieves an improvement in argument size that ranges from $1.25\times$ to $2.46\times$ depending on the chosen parameters, with similar
prover and verifier running times. For example, in order to achieve 128 bits of security for degree $2^{26}$ and rate $1/4$, STIR has argument size $114$ KiB, compared to $211$ KiB for FRI.



## 2024/391

* Title: On Information-Theoretic Secure Multiparty Computation with Local Repairability
* Authors: Daniel Escudero, Ivan Tjuawinata, Chaoping Xing
* [Permalink](https://eprint.iacr.org/2024/391)
* [Download](https://eprint.iacr.org/2024/391.pdf)

### Abstract

In this work we consider the task of designing information-theoretic MPC protocols for which the state of a given party can be recovered from a small amount of parties, a property we refer to as local repairability.
This is useful when considering MPC over dynamic settings where parties leave and join a computation, a scenario that has gained notable attention in recent literature.
Thanks to the results of (Cramer et al. EUROCRYPT'00), designing such protocols boils down to constructing a linear secret-sharing scheme (LSSS) with good locality, that is, each share is determined by only a small amount of other shares, that also
satisfies the so-called multiplicativity property.
Previous constructions that achieve locality (e.g. using locally recoverable codes---LRCs) do not enjoy multiplicativity, and LSSS that are multiplicative (e.g. Shamir's secret-sharing) do not satisfy locality.
Our construction bridges this literature gap by showing the existence of an LSSS that achieves both properties simultaneously.

Our results are obtained by making use of well known connection between error correcting codes and LSSS, in order to adapt the LRC construction by (Tamo & Barg, IEEE Transactions on Information Theory 2014) to turn it into a LSSS.
With enough care, such coding-theoretic construction yields our desired locality property, but it falls short at satisfying multiplicativity.
In order to address this, we perform an extensive analysis of the privacy properties of our scheme in order to identify parameter regimes where our construction satisfies multiplicativity.

Finally, since our LSSS satisfies locality, every share is determined by a small amount of shares.
However, in an MPC context it is not enough to let the (small set of) parties to send their shares to the repaired party, since this may leak more information than the regenerated share.
To obtain our final result regarding MPC with local repairability, we construct a lightweight MPC protocol that performs such repairing process without any leakage.
We provide both a passively secure construction (for the plain multiplicative regime) and an actively secure one (for strong multiplicativity).



## 2024/392

* Title: Heuristic Ideal Obfuscation Scheme based on LWE Problem, its Variants and Quantum Oracle
* Authors: Zhuang Shan, Leyou Zhang, Qing Wu
* [Permalink](https://eprint.iacr.org/2024/392)
* [Download](https://eprint.iacr.org/2024/392.pdf)

### Abstract

This paper presents a heuristic ideal obfuscation scheme based on the learning problem, which di ers from that of Jain, Lin, and Luo [JLLW23]. The paper adopts a method similar to Brakerski, Dottling, Garg, and Malavolta [BDGM22, BDGM20] for constructing
iO. It first introduces a variant of the LWR problem and proves its pseudorandomness. Based on the variant of the LWR problem, it constructs LHE, then combines it with sFHE constructed from the LWE problem to further construct the ideal obfuscation
scheme. In comparison to the approach by Jain et al., this paper is relatively more specific. Additionally, the paper incorporates the quantum random oracle construction by Jelle Don, et al.[DFMS22] to provide a more concrete quantum random oracle used
in the proposed obfuscation scheme.



## 2024/393

* Title: Revisiting the May--Meurer--Thomae Algorithm --- Solving McEliece-1409 in One Day
* Authors: Shintaro Narisada, Shusaku Uemura, Hiroki Okada, Hiroki Furue, Yusuke Aikawa, Kazuhide Fukushima
* [Permalink](https://eprint.iacr.org/2024/393)
* [Download](https://eprint.iacr.org/2024/393.pdf)

### Abstract

As post-quantum cryptography transitions toward practical deployment, the significance of extensive cryptanalysis is on the rise. Three out of the four NIST-PQC round 4 candidates are forms of code-based cryptography. Analyses of asymptotic complexity in
information set decoding (ISD) algorithms have been a central focus in the field of code-based cryptography. Recently, Esser, May and Zweydinger (Eurocrypt '22) demonstrate the practicality of the May--Meurer--Thomae (MMT) algorithm by decoding McEliece-
1284. Esser and Zweydinger (Eurocrypt '23) propose the time-memory trade-off variant of Becker--Joux--May--Meurer (BJMM) decoding, which solves QC-3138. These works have paved the way for the cryptanalysis of ISD in real-world scenarios.

In this work, we further advance the progress of the abovementioned studies by performing a concrete analysis of MMT decoding. We improve the list construction in MMT so that the number of both candidates and representations in the enumeration phase is
increased without the need for additional time and memory. Our new algorithm is theoretically 5.1 times faster than the BJMM algorithm for Classic McEliece I instance. We achieve the minimum time complexity across all categories of Classic McEliece among
all ISD algorithms. Moreover, compared with the BJMM algorithm, our MMT algorithm reduces the bit security by 1 to 3 bits for all code based NIST-PQC round 4 candidates. Practical security estimates confirm that all the candidates have sufficiently
strong bit security, except for Classic McEliece III, with a 1-bit deficiency.

In addition, we implement our new MMT algorithm in a GPU environment and provide the new record of the McEliece-1409 instance, along with implementation details and experimental analyses. Our study verifies the practical reliability of the code-based
candidates against current ISD algorithms.



## 2024/394

* Title: A Deniably Authenticated Searchable Public Key Encryption Scheme in Mobile Electronic Mail System
* Authors: Shuhan Zeng, Yongjian Liao, Chuanhao Zhou, Jinlin He, Hongwei Wang
* [Permalink](https://eprint.iacr.org/2024/394)
* [Download](https://eprint.iacr.org/2024/394.pdf)

### Abstract

Confidentiality and authentication are two main security goals in secure electronic mail (e-mail). Furthermore, deniability is also a significant security property for some e-mail applications to protect the privacy of the sender. Although searchable
encryption solves the keyword searching problem in a secure e-mail system, it also breaks the deniability of the system. Because the adversary can obtain the information of the data sender and data user from the trapdoor as well as ciphertext used for
keyword searching. At the same time, efficiency is another problem in mobile computing. To overcome the issues, we put forward deniably authenticated searchable public key encryption (DA-SPKE) which can apply to the deniable e-mail system. We first
define the DA-SPKE model and propose the DA-SPKE scheme. Then we prove its security in the random oracle model and evaluate its efficiency. Finally, we use it in a deniably secure e-mail system to protect both data senders’ and data users' privacy.



## 2024/395

* Title: Notus: Dynamic Proofs of Liabilities from Zero-knowledge RSA Accumulators
* Authors: Jiajun Xin, Arman Haghighi, Xiangan Tian, Dimitrios Papadopoulos
* [Permalink](https://eprint.iacr.org/2024/395)
* [Download](https://eprint.iacr.org/2024/395.pdf)

### Abstract

Proofs of Liabilities (PoL) allow an untrusted prover to commit to its liabilities towards a set of users and then prove independent users' amounts or the total sum of liabilities, upon queries by users or third-party auditors. This application setting
is highly dynamic. User liabilities may increase/decrease arbitrarily and the prover needs to update proofs in epoch increments (e.g., once a day for a crypto-asset exchange platform). However, prior works mostly focus on the static case and trivial
extensions to the dynamic setting open the system to windows of opportunity for the prover to under-report its liabilities and rectify its books in time for the next check, unless all users check their liabilities at all epochs. In this work, we develop
Notus, the first dynamic PoL system for general liability updates that avoids this issue. Moreover, it achieves $O(1)$ query proof size, verification time, and auditor overhead-per-epoch.
The core building blocks underlying Notus are a novel zero-knowledge (and SNARK-friendly) RSA accumulator and a corresponding zero-knowledge MultiSwap protocol, which may be of independent interest. We then propose optimizations to reduce the prover's
update overhead and make Notus scale to large numbers of users ($10^6$ in our experiments). Our results are very encouraging, e.g., it takes less than $2$ms to verify a user's liability and the proof size is $256$ Bytes. On the prover side, deploying
Notus on a cloud-based testbed with eight 32-core machines and exploiting parallelism, it takes ${\sim}3$ minutes to perform the complete epoch update, after which all proofs have already been computed.



## 2024/396

* Title: On the impact of ionizing and non-ionizing irradiation damage on security microcontrollers in CMOS technology
* Authors: Theresa Krüger
* [Permalink](https://eprint.iacr.org/2024/396)
* [Download](https://eprint.iacr.org/2024/396.pdf)

### Abstract

The possible effects of irradiation on security controllers implemented in CMOS technology are studied. First, the decrease of the effectiveness of a light sensor/detector as countermeasure against laser fault injection is analysed. Second, the use of
irradiation as fault injection method is proposed.



## 2024/397

* Title: Exponent-VRFs and Their Applications
* Authors: Dan Boneh, Iftach Haitner, Yehuda Lindell
* [Permalink](https://eprint.iacr.org/2024/397)
* [Download](https://eprint.iacr.org/2024/397.pdf)

### Abstract

Verifiable random functions (VRFs) are pseudorandom functions with the addition that the function owner can prove that a generated output is correct, with respect to a committed key. In this paper we introduce the notion of an exponent-VRF, or eVRF,
which is a VRF that does not provide its output $y$ explicitly, but instead provides $Y = y \cdot G$, where $G$ is a generator of some finite cyclic group (or $Y = g^y$ in multiplicative notation). We construct eVRFs from DDH and from the Paillier
encryption scheme (both in the random-oracle model). We then show that an eVRF can be used to solve several long-standing open problems in threshold cryptography. In particular, we construct (1) a one-round fully simulatable distributed key-generation
protocols (after a single two-round initialization phase), (2) a two-round fully simulatable signing protocols for multiparty Schnorr with a deterministic variant, (3) a two-party ECDSA protocol that has a deterministic variant, (4) a threshold Schnorr
signing where the parties can later prove that they signed without being able to frame another group, (5) an MPC-friendly and verifiable HD-derivation. Efficient simulatable protocols of this round complexity were not known prior to this work. All of our
protocols are concretely efficient.



## 2024/398

* Title: The Last Challenge Attack: Exploiting a Vulnerable Implementation of the Fiat-Shamir Transform in a KZG-based SNARK
* Authors: Oana Ciobotaru, Maxim Peter, Vesselin Velichkov
* [Permalink](https://eprint.iacr.org/2024/398)
* [Download](https://eprint.iacr.org/2024/398.pdf)

### Abstract

The Fiat-Shamir transform [1] is a well-known and widely employed technique for converting sound public-coin interactive protocols into sound non-interactive protocols. Even though the transformation itself is relatively clear and simple, some
implementations choose to deviate from the specifications, for example for performance reasons. In this short note, we present a vulnerability arising from such a deviation in a KZG-based PLONK verifier implementation. This deviation stemmed from the
incorrect computation of the last challenge of the PLONK protocol [2], where the KZG batching proof challenge was computed before, and, hence, independently from the KZG evaluation proofs. More generally, such a vulnerability may affect any KZG [3]
implementation where one uses batched KZG proof evaluations for at least two distinct evaluation points. We call an attack enabled by such a deviation a Last Challenge Attack. For concreteness, we show that when a PLONK verifier implementation presents
such a deviation, a malicious PLONK prover can mount a Last Challenge Attack to construct verifiable proofs of false statements. The described vulnerability was initially discovered as part of an audit, and has been responsibly disclosed to the
developers and fixed. A proof of concept of the vulnerability, in which a proof is forged for an arbitrary public input, is made available.

In addition to the above, in this work we also provide a security proof of the knowledge-soundness of the batched KZG scheme with evaluations for at least two distinct values.



## 2024/399

* Title: A Direct PRF Construction from Kolmogorov Complexity
* Authors: Yanyi Liu, Rafael Pass
* [Permalink](https://eprint.iacr.org/2024/399)
* [Download](https://eprint.iacr.org/2024/399.pdf)

### Abstract

While classic result in the 1980s establish that one-way functions (OWFs) imply the existence of pseudorandom generators (PRGs) which in turn imply pseudorandom functions (PRFs), the constructions (most notably the one from OWFs to PRGs) is complicated
and inefficient.

Consequently, researchers have developed alternative \emph{direct} constructions of PRFs from various different concrete hardness assumptions. In this work, we continue this thread of work and demonstrate the first direct constructions of PRFs from
average-case hardness of the time-bounded Kolmogorov complexity problem $\mktp[s]$, where given a threshold, $s(\cdot)$, and a polynomial time-bound, $t(\cdot)$, $\mktp[s]$ denotes the language consisting of strings $x$ with $t$-bounded Kolmogorov
complexity, $K^t(x)$, bounded by $s(|x|)$.

In more detail, we demonstrate a direct PRF construction with quasi-polynomial security from mild average-case of hardness of $\mktp[2^{O(\sqrt{\log n})}]$ w.r.t the uniform distribution. We note that by earlier results, this
assumption is known to be equivalent to the existence of quasi-polynomially secure OWFs; as such, our results yield the first direct (quasi-polynomially secure) PRF constructions from a natural hardness assumptions that also is known to be implied by (
quasi-polynomially secure) PRFs.

Perhaps surprisingly, we show how to make use of the Nisan-Wigderson PRG construction to get a cryptographic, as opposed to a complexity-theoretic, PRG.



## 2024/400

* Title: SILBE: an Updatable Public Key Encryption Scheme from Lollipop Attacks * Authors: Max Duparc, Tako Boris Fouotsa, Serge Vaudenay
* [Permalink](https://eprint.iacr.org/2024/400)
* [Download](https://eprint.iacr.org/2024/400.pdf)

### Abstract

We present a new post-quantum Public Key Encryption scheme (PKE) named Supersingular Isogeny Lollipop Based Encryption or SILBE. SILBE is obtained by leveraging the generalized lollipop attack of Castryck and Vercauteren on the M-SIDH Key exchange by
Fouotsa, Moriya and Petit. Doing so, we can in fact make of SILBE a post-quantum secure Updatable Public Key Encryption scheme (UPKE). SILBE is the first isogeny-based UPKE which is not based on group actions. In its core, SILBE extensively uses both
the Deuring Correspondence and Kani's Lemma, two central concepts in Isogeny-Based Cryptography.



## 2024/401

* Title: Plover: Masking-Friendly Hash-and-Sign Lattice Signatures
* Authors: Muhammed F. Esgin, Thomas Espitau, Guilhem Niot, Thomas Prest, Amin Sakzad, Ron Steinfeld
* [Permalink](https://eprint.iacr.org/2024/401)
* [Download](https://eprint.iacr.org/2024/401.pdf)

### Abstract

We introduce a toolkit for transforming lattice-based hash-and-sign signature schemes into masking-friendly signatures secure in the t-probing model. Until now, efficiently masking lattice-based hash-and-sign schemes has been an open problem, with
unsuccessful attempts such as Mitaka. A first breakthrough was made in 2023 with the NIST PQC submission Raccoon, although it was not formally proven.

Our main conceptual contribution is to realize that the same principles underlying Raccoon are very generic, and to find a systematic way to apply them within the hash-and-sign paradigm. Our main technical contribution is to formalize, prove, instantiate
and implement a hash-and-sign scheme based on these techniques. Our toolkit includes noise flooding to mitigate statistical leaks, and an extended Strong Non-Interfering probing security (SNIu) property to handle masked gadgets with unshared inputs.

We showcase the efficiency of our techniques in a signature scheme, Plover, based on (hint) Ring-LWE. It is the first lattice-based masked hash-and-sign scheme with quasi-linear complexity O(d log d) in the number of shares d. Our performances are
competitive with the state-of-the-art masking-friendly signature, the Fiat-Shamir scheme Raccoon.



## 2024/402

* Title: Efficient Unbalanced Quorum PSI from Homomorphic Encryption
* Authors: Xinpeng Yang, Liang Cai, Yinghao Wang, Yinghao Wang, Lu Sun, Jingwei Hu
* [Permalink](https://eprint.iacr.org/2024/402)
* [Download](https://eprint.iacr.org/2024/402.pdf)

### Abstract

Multiparty private set intersection (mPSI) protocol is capable of finding the intersection of multiple sets securely without revealing any other information. However, its limitation lies in processing only those elements present in every participant's
set, which proves inadequate in scenarios where certain elements are common to several, but not all, sets.
In this paper, we introduce an innovative variant of the mPSI protocol named unbalanced quorum PSI to fill in the gaps of the mPSI protocol. Unlike the previous quorum-PSI proposals which detect elements present in at least $k$ out of $n$ equal sets,
our protocol is particularly tailored for unbalanced cases where the size of the receiver's set is much smaller than the size of the senders' sets. Our work achieves logarithmic communication complexity in the semi-honest setting, significantly
surpassing previous work in efficiency.
The benchmarks show that it takes 22.7 seconds in WAN and 14.7 seconds in LAN for online computation, and only 87.8 MB of total communication to intersect 5535 elements across 15 sets, each containing $2^{24}$ elements. Compared to prior work, this
is roughly an 87$\times$ reduction in communication and a 31$\times$ reduction in online time. Our protocols can be easily extended to the larger set with $2^{28}$ elements which is nearly impractical for prior work.



## 2024/403

* Title: DARE to agree: Byzantine Agreement with Optimal Resilience and Adaptive Communication
* Authors: Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira
* [Permalink](https://eprint.iacr.org/2024/403)
* [Download](https://eprint.iacr.org/2024/403.pdf)

### Abstract

Byzantine Agreement (BA) enables $n$ processes to reach consensus on a common valid $L_o$-bit value, even in the presence of up to $t<n$ faulty processes that can deviate arbitrarily from their prescribed protocol. Despite its significance, the optimal
communication complexity for key variations of BA has not been determined within the honest majority regime ($n=2t+1$), for both the worst-case scenario and the adaptive scenario, which accounts for the actual number $f \leq t$ of failures.
We introduce ADA-DARE (Adaptively Disperse, Agree, Retrieve), a novel universal approach to solve BA efficiently. Let $\kappa$ represent the size of the cryptographic objects required to solve BA when $t>n/3$. Different instantiations of ADA-DARE achieve
near-optimal adaptive bit complexity of $O(nL_o + n(f + 1) \kappa)$ for both strong multi-valued validated BA (SMVBA) and interactive consistency (IC). By definition, for IC, $L_o = nL_{in}$, with $L_{in}$ representing the size of an input value.
These results achieve optimal $O(n(L_o+f))$ word complexity and significantly improve the previous best results by up to a linear factor, depending on $L_o$ and $f$.



## 2024/404

* Title: Breaking the DECT Standard Cipher with Lower Time Cost
* Authors: Lin Ding, Zhengting Li, Ziyu Guan, Xinhai Wang, Zheng Wu
* [Permalink](https://eprint.iacr.org/2024/404)
* [Download](https://eprint.iacr.org/2024/404.pdf)

### Abstract

The DECT Standard Cipher (DSC) is a proprietary stream cipher used for encryption in the Digital Enhanced Cordless Telecommunications (DECT), which is a standard for short range cordless communication and widely deployed worldwide both in residential and
enterprise environments. New weaknesses of the DSC stream cipher which are not discovered in previous works are explored and analyzed in this paper. Based on these weaknesses, new practical key recovery attacks and distinguishing attack on DSC with lower
time cost are proposed. The first cryptanalytic result show that DSC can be broken in about 13.12 seconds in the known IV setting, when an offline phase that takes about 58.33 minutes is completed. After then, a distinguishing attack on DSC in the
related key chosen IV setting is given, which has a time complexity of only 2 encryptions and a success probability of almost 1. Finally, based on the slide property, a key recovery attack on DSC with practical complexities is proposed. The experimental
result shows that DSC can be broken on a common PC within about 44.97 seconds in the multiple related key setting. The attacks on DSC proposed in this paper clearly show that a well-designed initialization is absolutely necessary to design a secure
stream cipher.



## 2024/405

* Title: Traceable Secret Sharing: Strong Security and Efficient Constructions * Authors: Dan Boneh, Aditi Partap, Lior Rotem
* [Permalink](https://eprint.iacr.org/2024/405)
* [Download](https://eprint.iacr.org/2024/405.pdf)

### Abstract

Suppose Alice uses a $t$-out-of-$n$ secret sharing to store her secret key on $n$ servers. Her secret key is protected as long as $t$ of them do not collude. However, what if a less-than-$t$ subset of the servers decides to offer the shares they have for
sale? In this case, Alice should be able to hold them accountable, or else nothing prevents them from selling her shares. With this motivation in mind, Goyal, Song, and Srinivasan (CRYPTO 21) introduced the concept of {\em traceable secret sharing}. In
such schemes, it is possible to provably trace the leaked secret shares back to the servers who leaked them. Goyal et al.~presented the first construction of a traceable secret sharing scheme. However, secret shares in their construction are quadratic in
the secret size, and their tracing algorithm is quite involved as it relies on Goldreich-Levin decoding.


[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)