• [digest] 2024 Week 12 (1/2)

    From IACR ePrint Archive@21:1/5 to All on Mon Mar 25 02:21:52 2024
    ## In this issue

    1. [2023/883] Prouff & Rivain’s Formal Security Proof of Masking, ...
    2. [2024/456] Tight ZK CPU: Batched ZK Branching with Cost ...
    3. [2024/457] Studying Lattice-Based Zero-Knowlege Proofs: A ...
    4. [2024/458] Classical and Quantum Generic Attacks on 6-round ...
    5. [2024/459] Isogeny problems with level structure
    6. [2024/460] Encrypted Image Classification with Low Memory ...
    7. [2024/461] Atlas-X Equity Financing: Unlocking New Methods to ...
    8. [2024/462] Perfect Zero-Knowledge PCPs for #P
    9. [2024/463] Security Guidelines for Implementing Homomorphic ...
    10. [2024/464] ON THE IMPLEMENTATION OF A LATTICE-BASED DAA FOR ...
    11. [2024/465] Shorter VOLEitH Signature from Multivariate Quadratic
    12. [2024/466] Arctic: Lightweight and Stateless Threshold Schnorr ...
    13. [2024/467] Partially Non-Interactive Two-Round Lattice-Based ...
    14. [2024/468] Zero-Dimensional Gröbner Bases for Rescue-XLIX
    15. [2024/469] Malicious Security for Sparse Private Histograms
    16. [2024/470] Fast Secure Computations on Shared Polynomials and ...
    17. [2024/471] Knot-based Key Exchange protocol
    18. [2024/472] Sailfish: Towards Improving Latency of DAG-based BFT
    19. [2024/473] Extremely Simple Fail-Stop ECDSA Signatures
    20. [2024/474] Accumulation without Homomorphism
    21. [2024/475] CheckOut: User-Controlled Anonymization for ...
    22. [2024/476] OPSA: Efficient and Verifiable One-Pass Secure ...
    23. [2024/477] Large Language Models for Blockchain Security: A ...
    24. [2024/478] The Security of SHA2 under the Differential Fault ...
    25. [2024/479] Making Hash-based MVBA Great Again
    26. [2024/480] Folding-based zkLLM
    27. [2024/481] Watermarkable and Zero-Knowledge Verifiable Delay ...

    ## 2023/883

    * Title: Prouff & Rivain’s Formal Security Proof of Masking, Revisited: Tight Bounds in the Noisy Leakage Model
    * Authors: Loïc Masure, François-Xavier Standaert
    * [Permalink](https://eprint.iacr.org/2023/883)
    * [Download](https://eprint.iacr.org/2023/883.pdf)

    ### Abstract

    Masking is a counter-measure that can be incorporated to
    software and hardware implementations of block ciphers to provably se-
    cure them against side-channel attacks. The security of masking can be
    proven in different types of threat models. In this paper, we are interested in directly proving the security in the most realistic threat model, the so-called noisy leakage adversary, that captures well how real-world side- channel adversaries operate. Direct proofs in this leakage model have
    been established by Prouff & Rivain at Eurocrypt 2013, Dziembowski
    et al. at Eurocrypt 2015, and Prest et al. at Crypto 2019. Both proofs
    are complementary to each other, in the sense that the weaknesses of one
    proof are fixed in at least one of the others, and conversely. These weak- nesses concerned in particular the strong requirements on the noise level
    and the security parameter to get meaningful security bounds, and some requirements on the type of adversary covered by the proof — i.e., cho-
    sen or random plaintexts. This suggested that the drawbacks of each
    security bound could actually be proof artifacts. In this paper, we solve
    these issues, by revisiting Prouff & Rivain’s approach.



    ## 2024/456

    * Title: Tight ZK CPU: Batched ZK Branching with Cost Proportional to Evaluated Instruction
    * Authors: Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov, Muthuramakrishnan Venkitasubramaniam
    * [Permalink](https://eprint.iacr.org/2024/456)
    * [Download](https://eprint.iacr.org/2024/456.pdf)

    ### Abstract

    We explore Zero-Knowledge proofs (ZKP) of statements expressed as programs written in high-level languages, e.g., C or assembly. At the core of executing such programs in ZK is the repeated evaluation of a CPU step, achieved by branching over the CPU’s
    instruction set. This approach is general and covers traversal-execution of a program’s control flow graph (CFG): here CPU instructions are straight-line program fragments (of various sizes) associated with the CFG nodes. This highlights the usefulness
    of ZK CPUs with a large number of instructions of varying sizes.

    We formalize and design an efficient tight ZK CPU, where the cost (both computation and communication, for each party) of each step depends only on the instruction taken. This qualitatively improves over state-of-the-art, where cost scales with the size
    of the largest CPU instruction (largest CFG node).

    Our technique is formalized in the standard commit-and-prove paradigm, so our results are compatible with a variety of (interactive and non-interactive) general-purpose ZK.

    We implemented an interactive tight arithmetic (over $\mathbb{F}_{2^{61}-1}$) ZK CPU based on Vector Oblivious Linear Evaluation (VOLE) and compared it to the state-of-the-art non-tight VOLE-based ZK CPU Batchman (Yang et al. CCS’23). In our
    experiments, under the same hardware configuration, we achieve comparable performance when instructions are of the same size and a $5$-$18×$ improvement when instructions are of varied size. Our VOLE-based ZK CPU can execute $100$K (resp. $450$K)
    multiplication gates per second in a WAN-like (resp. LAN-like) setting. It requires ≤ $102$ Bytes per multiplication gate. Our basic building block, ZK Unbalanced Read-Only Memory (ZK UROM), may be of an independent interest.



    ## 2024/457

    * Title: Studying Lattice-Based Zero-Knowlege Proofs: A Tutorial and an Implementation of Lantern
    * Authors: Lena Heimberger, Florian Lugstein, Christian Rechberger
    * [Permalink](https://eprint.iacr.org/2024/457)
    * [Download](https://eprint.iacr.org/2024/457.pdf)

    ### Abstract

    Lattice-based cryptography has emerged as a promising new candidate to build cryptographic primitives. It offers resilience against quantum attacks, enables fully homomorphic encryption, and relies on robust theoretical foundations. Zero-knowledge proofs
    (ZKPs) are an essential primitive for various privacy-preserving applications. For example, anonymous credentials, group signatures, and verifiable oblivious pseudorandom functions all require ZKPs. Currently, the majority of ZKP systems are based on
    elliptic curves, which are susceptible to attacks from quantum computers. This project presents the first implementation of Lantern, a state-of-the-art lattice-based ZKP system that can create compact proofs, which are a few dozen kilobytes large, for
    basic statements. We thoroughly explain the theory behind the scheme and give a full implementation in a Jupyter Notebook using SageMath to make Lantern more accessible to researchers. Our interactive implementation allows users to fully understand the
    scheme and its building blocks, providing a valuable resource to understand both ZKPs and lattice cryptography. Albeit not optimized for performance, this implementation allows us to construct a Module-LWE secret proof in 35s on a consumer laptop.
    Through our contributions, we aim to advance the understanding and practical utilization of lattice-based ZKP systems, particularly emphasizing accessibility for the broader research community.



    ## 2024/458

    * Title: Classical and Quantum Generic Attacks on 6-round Feistel Schemes
    * Authors: Maya Chartouny, Benoit Cogliati, Jacques Patarin
    * [Permalink](https://eprint.iacr.org/2024/458)
    * [Download](https://eprint.iacr.org/2024/458.pdf)

    ### Abstract

    In this paper, we describe new quantum generic attacks on 6 rounds balanced Feistel networks with internal functions or internal permutations. In order to obtain our new quantum attacks, we revisit a result of Childs and Eisenberg that extends Ambainis'
    collision finding algorithm to the subset finding problem. In more details, we continue their work by carefully analyzing the time complexity of their algorithm. We also use four points structures attacks instead of two points structures attacks that
    leads to a complexity of $\mathcal{O}(2^{8n/5})$ instead of $\mathcal{O}(2^{2n})$. Moreover, we have also found a classical (i.e. non quantum) improved attack on $6$ rounds with internal permutations. The complexity here will be in $\mathcal{O}(2^{2n})$
    instead of $\mathcal{O}(2^{3n})$ previously known.



    ## 2024/459

    * Title: Isogeny problems with level structure
    * Authors: Luca De Feo, Tako Boris Fouotsa, Lorenz Panny
    * [Permalink](https://eprint.iacr.org/2024/459)
    * [Download](https://eprint.iacr.org/2024/459.pdf)

    ### Abstract

    Given two elliptic curves and the degree of an isogeny between them, finding the isogeny is believed to be a difficult problem---upon which rests the security of nearly any isogeny-based scheme. If, however, to the data above we add information about the
    behavior of the isogeny on a large enough subgroup, the problem can become easy, as recent cryptanalyses on SIDH have shown.
    Between the restriction of the isogeny to a full $N$-torsion subgroup and no ''torsion information'' at all lies a spectrum of interesting intermediate problems, raising the question of how easy or hard each of them is. Here we explore modular isogeny
    problems where the torsion information is masked by the action of a group of $2\times 2$ matrices. We give reductions between these problems, classify them by their difficulty, and link them to security assumptions found in the literature.



    ## 2024/460

    * Title: Encrypted Image Classification with Low Memory Footprint using Fully Homomorphic Encryption
    * Authors: Lorenzo Rovida, Alberto Leporati
    * [Permalink](https://eprint.iacr.org/2024/460)
    * [Download](https://eprint.iacr.org/2024/460.pdf)

    ### Abstract

    Classifying images has become a straightforward and accessible task, thanks to the advent of Deep Neural Networks. Nevertheless, not much attention is given to the privacy concerns associated with sensitive data contained in images. In this study, we
    propose a solution to this issue by exploring an intersection between Machine Learning and cryptography.
    In particular, Fully Homomorphic Encryption (FHE) emerges as a promising solution, as it enables computations to be performed on encrypted data. We, therefore, propose a Residual Network implementation based on FHE which allows the classification of
    encrypted images, ensuring that only the user can see the result.
    We suggest a circuit which reduces the memory requirements by more than 85% compared to the most recent works, while maintaining a high level of accuracy and a short computational time. We implement the circuit using the well-known CKKS scheme, which
    enables approximate encrypted computations.
    We evaluate the results from three perspectives: memory requirements, computational time and calculations precision. We demonstrate that it is possible to evaluate an encrypted ResNet20 in less than five minutes on a laptop using approximately 15GB of
    memory, achieving an accuracy of 91.67% on the CIFAR-10 dataset, which is almost equivalent to the accuracy of the plain model (92.60%).



    ## 2024/461

    * Title: Atlas-X Equity Financing: Unlocking New Methods to Securely Obfuscate Axe Inventory Data Based on Differential Privacy
    * Authors: Antigoni Polychroniadou, Gabriele Cipriani, Richard Hua, Tucker Balch
    * [Permalink](https://eprint.iacr.org/2024/461)
    * [Download](https://eprint.iacr.org/2024/461.pdf)

    ### Abstract

    Banks publish daily a list of available securities/assets (axe list) to selected clients to help them effectively locate Long (buy) or Short (sell) trades at reduced financing rates. This reduces costs for the bank, as the list aggregates the bank's
    internal firm inventory per asset for all clients of long as well as short trades. However, this is somewhat problematic: (1) the bank's inventory is revealed; (2) trades of clients who contribute to the aggregated list, particularly those deemed large,
    are revealed to other clients. Clients conducting sizable trades with the bank and possessing a portion of the aggregated asset exceeding $50\%$ are considered to be concentrated clients. This could potentially reveal a trading concentrated client's
    activity to their competitors, thus providing an unfair advantage over the market.


    Atlas-X Axe Obfuscation, powered by new differential private methods, enables a bank to obfuscate its published axe list on a daily basis while under continual observation, thus maintaining an acceptable inventory Profit and Loss (P\&L) cost pertaining
    to the noisy obfuscated axe list while reducing the clients' trading activity leakage. Our main differential private innovation is a differential private aggregator for streams (time series data) of both positive and negative integers under continual
    observation.

    For the last two years, Atlas-X system has been live in production across three major regions—USA, Europe, and Asia—at J.P. Morgan, a major financial institution, facilitating significant profitability. To our knowledge, it is the first differential
    privacy solution to be deployed in the financial sector. We also report benchmarks of our algorithm based on (anonymous) real and synthetic data to showcase the quality of our obfuscation and its success in production.



    ## 2024/462

    * Title: Perfect Zero-Knowledge PCPs for #P
    * Authors: Tom Gur, Jack O'Connor, Nicholas Spooner
    * [Permalink](https://eprint.iacr.org/2024/462)
    * [Download](https://eprint.iacr.org/2024/462.pdf)

    ### Abstract

    We construct perfect zero-knowledge probabilistically checkable proofs (PZK-PCPs) for every language in #P. This is the first construction of a PZK-PCP for any language outside BPP. Furthermore, unlike previous constructions of (statistical) zero-
    knowledge PCPs, our construction simultaneously achieves non-adaptivity and zero knowledge against arbitrary (adaptive) polynomial-time malicious verifiers.

    Our construction consists of a novel masked sumcheck PCP, which uses the combinatorial nullstellensatz to obtain antisymmetric structure within the hypercube and randomness outside of it. To prove zero knowledge, we introduce the notion of locally
    simulatable encodings: randomised encodings in which every local view of the encoding can be efficiently sampled given a local view of the message. We show that the code arising from the sumcheck protocol (the Reed--Muller code augmented with subcube
    sums) admits a locally simulatable encoding. This reduces the algebraic problem of simulating our masked sumcheck to a combinatorial property of antisymmetric functions.



    ## 2024/463

    * Title: Security Guidelines for Implementing Homomorphic Encryption
    * Authors: Jean-Philippe Bossuat, Rosario Cammarota, Jung Hee Cheon, Ilaria Chillotti, Benjamin R. Curtis, Wei Dai, Huijing Gong, Erin Hales, Duhyeong Kim, Bryan Kumara, Changmin Lee, Xianhui Lu, Carsten Maple, Alberto Pedrouzo-Ulloa, Rachel Player, Luis
    Antonio Ruiz Lopez, Yongsoo Song, Donggeon Yhee, Bahattin Yildiz
    * [Permalink](https://eprint.iacr.org/2024/463)
    * [Download](https://eprint.iacr.org/2024/463.pdf)

    ### Abstract

    Fully Homomorphic Encryption (FHE) is a cryptographic primitive that allows performing arbitrary operations on encrypted data. Since the conception of the idea in [RAD78], it was considered a holy grail of cryptography. After the first construction in
    2009 [Gen09], it has evolved to become a practical primitive with strong security guarantees. Most modern constructions are based on well-known lattice problems such as Learning with Errors (LWE). Besides its academic appeal, in recent years FHE has also
    attracted significant attention from industry, thanks to its applicability to a considerable number of real-world use-cases. An upcoming standardization effort by ISO/IEC aims to support the wider adoption of these techniques. However, one of the main
    challenges that standards bodies, developers, and end users usually encounter is establishing parameters. This is particularly hard in the case of FHE because the parameters are not only related to the security level of the system, but also to the type
    of operations that the system is able to handle. In this paper, we provide examples of parameter sets for LWE targeting particular security levels that can be used in the context of FHE constructions. We also give examples of complete FHE parameter sets,
    including the parameters relevant for correctness and performance, alongside those relevant for security. As an additional contribution, we survey the parameter selection support offered in open-source FHE libraries.



    ## 2024/464

    * Title: ON THE IMPLEMENTATION OF A LATTICE-BASED DAA FOR VANET SYSTEM
    * Authors: Doryan Lesaignoux, Mikael Carmona
    * [Permalink](https://eprint.iacr.org/2024/464)
    * [Download](https://eprint.iacr.org/2024/464.pdf)

    ### Abstract

    Direct Anonymous Attestation (DAA) is a cryptographic protocol that enables users with a Trusted Platform Module (TPM) to authenticate without revealing their identity. Thus, DAA emerged as a good privacy-enhancing solution. Current standards have
    security based on factorization and discrete logarithm problem making them vulnerable to quantum computer attacks. Recently, a number of lattice-based DAA has been propose in the literature to start transition to quantum-resistant cryptography. In
    addition to these, DAA has been adapted to Vehicle Ad-hoc NETwork system (VANETs) to offer secure vehicule-to-vehicule/infrastructure communication (V2V and V2I). In this paper, we provide an implementation of the most advanced post-quantum DAA for
    VANETs. We explore the cryptographic foundations, construction methodologies, and the performance of this scheme, offering insights into their suitability for various real-world use cases.



    ## 2024/465

    * Title: Shorter VOLEitH Signature from Multivariate Quadratic
    * Authors: Dung Bui
    * [Permalink](https://eprint.iacr.org/2024/465)
    * [Download](https://eprint.iacr.org/2024/465.pdf)

    ### Abstract

    VOLE-in-the-head paradigm recently introduced by Baum et al. (Crypto 2023) allows transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our
    transformation applies to a large class of ZK protocols based on vector oblivious linear evaluation (VOLE) and leads to resulting ZK protocols that have linear proof size and are simpler, smaller, and faster than related approaches based on MPC-in-the-
    head.
    We propose a new candidate post-quantum signature scheme from the Multivariate Quadratic(MQ) problem based on a new protocol for the VOLE-in-the-head paradigm, which significantly reduces the signature size compared to previous works. We achieve a
    signature size of 2.5KB for a 128-bit security level. Compared to the state-of-the-art MQ-based signature schemes, our signature scheme achieves a factor from 3 to 4 improvement in terms of the signature size while keeping the computational efficiency
    competitive



    ## 2024/466

    * Title: Arctic: Lightweight and Stateless Threshold Schnorr Signatures
    * Authors: Chelsea Komlo, Ian Goldberg
    * [Permalink](https://eprint.iacr.org/2024/466)
    * [Download](https://eprint.iacr.org/2024/466.pdf)

    ### Abstract

    Threshold Schnorr signatures are seeing increased adoption in practice, and offer practical defenses against single points of failure. However, one challenge with existing randomized threshold Schnorr signature schemes is that signers must carefully
    maintain secret state across signing rounds, while also ensuring that state is deleted after a signing session is completed. Failure to do so will result in a fatal key-recovery attack by re-use of nonces.

    While deterministic threshold Schnorr signatures that mitigate this issue exist in the literature, all prior schemes incur high complexity and performance overhead in comparison to their randomized equivalents. In this work, we seek the best of both
    worlds; a deterministic and stateless threshold Schnorr signature scheme that is also simple and efficient.

    Towards this goal, we present Arctic, a lightweight two-round threshold Schnorr signature that is deterministic, and therefore does not require participants to maintain state between signing rounds. As a building block, we formalize the notion of a
    Verifiable Pseudorandom Secret Sharing (VPSS) scheme, and define Shine, an efficient VPSS construction. Shine is secure when the total number of participants is at least 2t − 1 and the adversary is assumed to corrupt at most t − 1; i.e., in the
    honest majority model.

    We prove that Arctic is secure under the discrete logarithm assumption in the random oracle model, similarly assuming at minimum 2t − 1 number of signers and a corruption threshold of at most t − 1. For moderately sized groups (i.e., when n ≤ 20),
    Arctic is more than an order of magnitude more efficient than prior deterministic threshold Schnorr signatures in the literature. For small groups where n ≤ 10, Arctic is three orders of magnitude more efficient.



    ## 2024/467

    * Title: Partially Non-Interactive Two-Round Lattice-Based Threshold Signatures * Authors: Rutchathon Chairattana-Apirom, Stefano Tessaro, Chenzhi Zhu
    * [Permalink](https://eprint.iacr.org/2024/467)
    * [Download](https://eprint.iacr.org/2024/467.pdf)

    ### Abstract

    This paper gives the first lattice-based two-round threshold signature based on lattice assumptions for which the first message is independent of the message being signed without relying on fully-homomorphic encryption. Our construction supports
    arbitrary thresholds and is scalable to support a large number of signers, say n = 1024.

    Our construction provides a careful instantiation of a generic threshold signature construction by Tessaro and Zhu (EUROCRYPT ’23) based on specific linear hash functions, which in turns can be seen as a generalization of the FROST scheme by Komlo and
    Goldberg (SAC ’20). Our reduction techniques are new in the context of lattice-based cryptography. Also, our scheme does not use any heavy tools, such as NIZKs or homomorphic trapdoor commitments.



    ## 2024/468

    * Title: Zero-Dimensional Gröbner Bases for Rescue-XLIX
    * Authors: Matthias Johann Steiner
    * [Permalink](https://eprint.iacr.org/2024/468)
    * [Download](https://eprint.iacr.org/2024/468.pdf)

    ### Abstract

    Rescue-XLIX is an Arithmetization-Oriented Substitution-Permutation Network over prime fields $\mathbb{F}_p$ which in one full round first applies a SPN based on $x \mapsto x^d$ followed by a SPN based on the inverse power map $x \mapsto x^\frac{1}{d}$.
    In a recent work, zero-dimensional Gröbner bases for SPN and Poseidon sponge functions have been constructed by utilizing weight orders. Following this approach we construct zero-dimensional Gröbner bases for Rescue-XLIX ciphers and sponge functions.



    ## 2024/469

    * Title: Malicious Security for Sparse Private Histograms
    * Authors: Lennart Braun, Adrià Gascón, Mariana Raykova, Phillipp Schoppmann, Karn Seth
    * [Permalink](https://eprint.iacr.org/2024/469)
    * [Download](https://eprint.iacr.org/2024/469.pdf)

    ### Abstract

    We present a construction for secure computation of differentially private sparse histograms that aggregates the inputs from a large number of clients. Each client contributes a value to the aggregate at a specific index. We focus on the case where the
    set of possible indices is superpolynomially large. Hence, the resulting histogram will be sparse, i.e., most entries will have the value zero.

    Our construction relies on two non-colluding servers and provides security against malicious adversaries that may control one of the servers and any numbers of clients. It achieves communication and computation complexities linear in the input size, and
    achieves the optimal error $O\big(\frac{\log(1/\delta)}{\epsilon}\big)$, independent of the size of the domain of indices. We compute the communication cost of our protocol, showing its scalability. For a billion clients, the communication cost for each
    server is under 26 KiB per client.

    Our paper solves an open problem of the work of Bell et al. (CCS'22) which presented a solution for the semi-honest setting while incurring sublinear overhead in its efficiency. We formalize a proof approach for proving malicious security in settings
    where the output and possible additional information revealed during the execution need to provide differential privacy.



    ## 2024/470

    * Title: Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations
    * Authors: Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow, Damien Vergnaud
    * [Permalink](https://eprint.iacr.org/2024/470)
    * [Download](https://eprint.iacr.org/2024/470.pdf)

    ### Abstract

    Secure multi-party computation aims to allow a set of players to compute a given function on their secret inputs without revealing any other information than the result of the computation. In this work, we focus on the design of secure multi-party
    protocols for shared polynomial operations. We consider the classical model where the adversary is honest-but-curious, and where the coefficients (or any secret values) are either encrypted using an additively homomorphic encryption scheme or shared
    using a threshold linear secret-sharing scheme. Our protocols terminate after a constant number of rounds and minimize the number of secure multiplications. In their seminal article at PKC 2006, Mohassel and Franklin proposed constant-rounds protocols
    for the main operations on (shared) polynomials. In this work, we improve the fan-in multiplication of nonzero polynomials, the multi-point polynomial evaluation and the polynomial interpolation (on secret points) to reach a quasi-linear complexity (
    instead of quadratic in Mohassel and Franklin's work) in the degree of shared input/output polynomials. Computing with shared polynomials is a core component of designing multi-party protocols for privacy-preserving operations on private sets, like
    private disjointness test or private set intersection. Using our new protocols, we are able to improve the complexity of such protocols and to design the first variant which always returns a correct result.



    ## 2024/471

    * Title: Knot-based Key Exchange protocol
    * Authors: Silvia Sconza, Arno Wildi
    * [Permalink](https://eprint.iacr.org/2024/471)
    * [Download](https://eprint.iacr.org/2024/471.pdf)

    ### Abstract

    We propose a new key exchange protocol based on the Generalised Diffie-Hellman Key Exchange. In the latter, instead of using a group-action, we consider a semigroup action. In our proposal, the semigroup is the set of oriented knots in $\mathbb{S}^3$
    with the operation of connected sum. As a semigroup action, we choose the action of the semigroup on itself through the connected sum. For the protocol to work, we need to use knot invariants, which allow us to create the shared secret key starting from
    the same knot represented in two different ways. In particular, we use finite type invariants. The security of the protocol is guaranteed by the hardness of decomposing knots in the semigroup.



    ## 2024/472

    * Title: Sailfish: Towards Improving Latency of DAG-based BFT
    * Authors: Nibesh Shrestha, Aniket Kate, Kartik Nayak
    * [Permalink](https://eprint.iacr.org/2024/472)
    * [Download](https://eprint.iacr.org/2024/472.pdf)

    ### Abstract

    Existing DAG-based BFT protocols exhibit long latency to commit decisions. The primary reason for such a long latency is having a leader every 2 or more “rounds”. Even under honest leaders, these protocols require two or more reliable broadcast (RBC)
    instances to commit the proposal submitted by the leader (leader vertex), and additional RBCs to commit other proposals (non-leader vertices). In this work, we present Sailfish, the first DAG-based BFT that supports a leader vertex in each round. Under
    honest leaders, Sailfish maintains a commit latency of one RBC round plus $1\delta$ to commit the leader vertex (where $\delta$ is the actual transmission latency of a message) and only an additional RBC round to commit non-leader vertices.



    ## 2024/473

    * Title: Extremely Simple Fail-Stop ECDSA Signatures
    * Authors: Mario Yaksetig
    * [Permalink](https://eprint.iacr.org/2024/473)
    * [Download](https://eprint.iacr.org/2024/473.pdf)

    ### Abstract

    Fail-stop signatures are digital signatures that allow a signer to prove that a specific forged signature is indeed a forgery. After such a proof is published, the system can be stopped.

    We introduce a new simple ECDSA fail-stop signature scheme. Our proposal is based on the minimal assumption that an adversary with a quantum computer is not able to break the (second) preimage resistance of a cryptographically-secure hash function. Our
    scheme is as efficient as traditional ECDSA, does not limit the number of signatures that a signer can produce, and relies on minimal security assumptions. Using our construction, the signer has minimal computational overhead in the signature producing
    phase and produces a signature indistinguishable from a 'regular' ECDSA signature.



    ## 2024/474

    * Title: Accumulation without Homomorphism
    * Authors: Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, William Wang
    * [Permalink](https://eprint.iacr.org/2024/474)
    * [Download](https://eprint.iacr.org/2024/474.pdf)

    ### Abstract

    Accumulation schemes are a simple yet powerful primitive that enable highly efficient constructions of incrementally verifiable computation (IVC). Unfortunately, all prior accumulation schemes rely on homomorphic vector commitments whose security is
    based on public-key assumptions.
    It is an interesting open question to construct efficient accumulation schemes that avoid the need for such assumptions.

    In this paper, we answer this question affirmatively by constructing an accumulation scheme from *non-homomorphic* vector commitments which can be realized from solely symmetric-key assumptions (e.g. Merkle trees).
    We overcome the need for homomorphisms by instead performing spot-checks over error-correcting encodings of the committed vectors.

    Unlike prior accumulation schemes, our scheme only supports a bounded number of accumulation steps.
    We show that such *bounded-depth* accumulation still suffices to construct proof-carrying data (a generalization of IVC).
    We also demonstrate several optimizations to our PCD construction which greatly improve concrete efficiency.



    ## 2024/475

    * Title: CheckOut: User-Controlled Anonymization for Customer Loyalty Programs * Authors: Matthew Gregoire, Rachel Thomas, Saba Eskandarian
    * [Permalink](https://eprint.iacr.org/2024/475)
    * [Download](https://eprint.iacr.org/2024/475.pdf)

    ### Abstract

    To resist the regimes of ubiquitous surveillance imposed upon us in every facet of modern life, we need technological tools that subvert surveillance systems. Unfortunately, while cryptographic tools frequently demonstrate how we can construct systems
    that safeguard user privacy, there is limited motivation for corporate entities engaged in surveillance to adopt these tools, as they often clash with profit incentives. This paper demonstrates how, in one particular aspect of everyday life -- customer
    loyalty programs -- users can subvert surveillance and attain anonymity, without necessitating any cooperation or modification in the behavior of their surveillors.

    We present the CheckOut system, which allows users to coordinate large anonymity sets of shoppers to hide the identity and purchasing habits of each particular user in the crowd. CheckOut scales up and systematizes past efforts to subvert loyalty
    surveillance, which have been primarily ad-hoc and manual affairs where customers physically swap loyalty cards to mask their real identities. CheckOut allows increased scale while ensuring that the necessary computing infrastructure does not itself
    become a new centralized point of privacy failure.


    [continued in next message]

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