[continued from previous message]

* Authors: Lorenzo Grassi, Fukang Liu, Christian Rechberger, Fabian Schmid, Roman Walch, Qingju Wang
* [Permalink](https://eprint.iacr.org/2024/791)
* [Download](https://eprint.iacr.org/2024/791.pdf)

### Abstract

The Rasta design strategy allows building low-round ciphers due to its efficient prevention of statistical attacks and algebraic attacks by randomizing the cipher, which makes it especially suitable for hybrid homomorphic encryption (HHE), also known as
transciphering. Such randomization is obtained by pseudorandomly sampling new invertible matrices for each round of each new cipher evaluation. However, naively sampling a random invertible matrix for each round significantly impacts the plain evaluation
runtime, though it does not impact the homomorphic evaluation cost. To address this issue, Dasta was proposed at ToSC 2020 to reduce the cost of generating the random matrices.

In this work, we address this problem from a different perspective: How far can the randomness in Rasta-like designs be reduced in order to minimize the plain evaluation runtime without sacrificing the security? To answer this question, we carefully
studied the main threats to Rasta-like ciphers and the role of random matrices in ensuring security. We apply our results to the recently proposed cipher $\text{PASTA}$, proposing a modified version called $\text{PASTA}_\text{v2}$ instantiated with one
initial random matrix and fixed linear layers - obtained by combining two MDS matrices with the Kronecker product - for the other rounds.

Compared with $\text{PASTA}$, the state-of-the-art cipher for BGV- and BFV-style HHE, our evaluation shows that $\text{PASTA}_\text{v2}$ is up to 100% faster in plain while having the same homomorphic runtime in the SEAL homomorphic encryption library
and up to 30% faster evaluation time in HElib, respectively.



## 2024/792

* Title: Stickel's Key Agreement Algebraic Variation
* Authors: Daniel Nager
* [Permalink](https://eprint.iacr.org/2024/792)
* [Download](https://eprint.iacr.org/2024/792.pdf)

### Abstract

In this document we present a further development of non-commutative algebra based key agreement due to E. Stickel and a way to deal with the algebraic break due to V. Sphilrain.



## 2024/793

* Title: Hide-and-Seek and the Non-Resignability of the BUFF Transform
* Authors: Jelle Don, Serge Fehr, Yu-Hsuan Huang, Jyun-Jie Liao, Patrick Struck * [Permalink](https://eprint.iacr.org/2024/793)
* [Download](https://eprint.iacr.org/2024/793.pdf)

### Abstract

The BUFF transform, due to Cremers et al. (S&P'21), is a generic transformation for digital signature scheme, with the purpose of obtaining additional security guarantees beyond unforgeability: exclusive ownership, message-bound signatures, and non-
resignability. Non-resignability (which essentially challenges an adversary to re-sign an unknown message for which it only obtains the signature) turned out to be a delicate matter, as recently Don et al. (CRYPTO'24) showed that the initial definition
is essentially unachievable; in particular, it is not achieved by the BUFF transform. This led to the introduction of new, weakened versions of non-resignability, which are (potentially) achievable. In particular, it was shown that a salted variant of
the BUFF transform does achieves some weakened version of non-resignability. However, the salting requires additional randomness and leads to slightly larger signatures. Whether the original BUFF transform also achieves some meaningful notion of non-
resignability remained a natural open question.

In this work, we answer this question in the affirmative. We show that the BUFF transform satisfies the (almost) strongest notions of non-resignability one can hope for, facing the known impossibility results. Our results cover both the statistical and
the computational case, and both the classical and the quantum setting. At the core of our analysis lies a new security game for random oracles that we call Hide-and-Seek. While seemingly innocent at first glance, it turns out to be surprisingly
challenging to rigorously analyze.



## 2024/794

* Title: Detecting Rogue Decryption in (Threshold) Encryption via Self-Incriminating Proofs
* Authors: James Hsin-yu Chiang, Bernardo David, Tore Kasper Frederiksen, Arup Mondal, Esra Yeniaras
* [Permalink](https://eprint.iacr.org/2024/794)
* [Download](https://eprint.iacr.org/2024/794.pdf)

### Abstract

Keeping decrypting parties accountable in public key encryption is notoriously hard since the secret key owner can decrypt any arbitrary ciphertext. Threshold encryption aims to solve this issue by distributing the power to decrypt among a set of parties,
who must interact via a decryption protocol. However, such parties can employ cryptographic tools such as Multiparty Computation (MPC) to decrypt arbitrary ciphertexts without being detected. We introduce the notion of (threshold) encryption with Self-
Incriminating Proofs, where parties must produce a self-incriminating proof of decryption when decrypting every ciphertext. In the standard public key encryption case, the adversary could destroy these proofs, so we strengthen our notion to guarantee
that the proofs are published when decryption succeeds. This creates a decryption audit trail, which is useful in scenarios where decryption power is held by a single trusted party (e.g., a Trusted Execution Environment) who must be kept accountable. In
the threshold case, we ensure that at least one of the parties who execute the decryption protocol will learn a self-incriminating proof, even if they employ advanced tools such as MPC. The fact that a party learns the proof and may leak it at any moment
functions as a deterrent for parties who do not wish to be identified as malicious decryptors (e.g., a commercial operator of a service based on threshold encryption). We investigate the (im)possibility and applications of our notions while providing
matching constructions under appropriate assumptions. In the threshold case, we build on recent results on Individual Cryptography (CRYPTO 2023).



## 2024/795

* Title: New Limits of Provable Security and Applications to ElGamal Encryption * Authors: Sven Schäge
* [Permalink](https://eprint.iacr.org/2024/795)
* [Download](https://eprint.iacr.org/2024/795.pdf)

### Abstract

We provide new results showing that ElGamal encryption cannot be proven CCA1-secure – a long-standing open problem in cryptography. Our result follows from a very broad, meta-reduction-based impossibility result on random self-reducible relations with
efficiently re-randomizable witnesses. The techniques that we develop allow, for the first time, to provide impossibility results for very weak security notions where the challenger outputs fresh challenge statements at the end of the security game. This
can be used to finally tackle encryption-type definitions that have remained elusive in the past. We show that our results have broad applicability by casting several known cryptographic setups as instances of random self-reducible and re-randomizable
relations. These setups include general semi-homomorphic PKE and the large class of certified homomorphic one-way bijections. As a result, we also obtain new impossibility results for the IND-CCA1 security of the PKEs of Paillier and Damg ̊ard–Jurik,
and many one-more inversion assumptions like the one-more DLOG or the one-more RSA assumption.



## 2024/796

* Title: Weak Consistency mode in Key Transparency: OPTIKS
* Authors: Esha Ghosh, Melissa Chase
* [Permalink](https://eprint.iacr.org/2024/796)
* [Download](https://eprint.iacr.org/2024/796.pdf)

### Abstract

The need for third-party auditors in privacy-preserving Key Transparency (KT) systems presents a deployment challenge. In this short note, we take a simple privacy-preserving KT system that provides strong security guarantees in the presence of an honest
auditor (OPTIKS) and show how to add a auditor-free mode to it. The auditor-free mode offers slightly weaker security. We formalize this security property and prove that our proposed protocol satisfies our security definition.



## 2024/797

* Title: Nonadaptive One-Way to Hiding Implies Adaptive Quantum Reprogramming
* Authors: Joseph Jaeger
* [Permalink](https://eprint.iacr.org/2024/797)
* [Download](https://eprint.iacr.org/2024/797.pdf)

### Abstract

An important proof technique in the random oracle model involves reprogramming it on hard to predict inputs and arguing that an attacker cannot detect that this occurred. In the quantum setting, a particularly challenging version of this considers
adaptive reprogramming wherein the points to be reprogrammed (or output values they should be programmed to) are dependent on choices made by the adversary. Frameworks for analyzing adaptive reprogramming were given by, e.g., by Unruh (CRYPTO 2014),
Grilo-Hövelmanns-Hülsing-Majenz (ASIACRYPT 2021), and Pan-Zeng (PKC 2024).

We show, counterintuitively, that these adaptive results follow directly from the non-adaptive one-way to hiding theorem of Ambainis-Hamburg-Unruh (CRYPTO 2019). These implications contradict beliefs (whether stated explicitly or implicitly) that some
properties of the adaptive frameworks cannot be provided by the Ambainis-Hamburg-Unruh result.



## 2024/798

* Title: Incompressible Functional Encryption
* Authors: Rishab Goyal, Venkata Koppula, Mahesh Sreekumar Rajasree, Aman Verma * [Permalink](https://eprint.iacr.org/2024/798)
* [Download](https://eprint.iacr.org/2024/798.pdf)

### Abstract

Incompressible encryption (Dziembowski, Crypto'06; Guan, Wichs, Zhandry, Eurocrypt'22) protects from attackers that learn the entire decryption key, but cannot store the full ciphertext. In incompressible encryption, the attacker must try to compress a
ciphertext within pre-specified memory bound $S$ before receiving the secret key.

In this work, we generalize the notion of incompressibility to functional encryption. In incompressible functional encryption, the adversary can corrupt non-distinguishing keys at any point, but receives the distinguishing keys only after compressing the
ciphertext to within $S$ bits. An important efficiency measure for incompressible encryption is the ciphertext-rate ( i.e., $\mathsf{rate} = \frac{|m|}{|\mathsf{ct}|}\;$). We give many new results for incompressible functional encryption:

1. Incompressible attribute-based encryption for circuits from standard assumptions, with $\mathsf{ct}$-rate-$\frac{1}{2}$ and short secret keys,
2. Incompressible functional encryption for circuits from (non-incompressible) functional encryption, with
(a) $\mathsf{ct}$-rate-$\frac{1}{2}$ and short secret keys,
(b) $\mathsf{ct}$-rate-$1$ and large secret keys.

Our results achieve optimal efficiency, as incompressible attribute-based/functional encryption with $\mathsf{ct}$-rate-$1$ as well as short secret keys has strong implausibility barriers. Moreover, our assumptions are minimal as incompressible attribute-
based/functional encryption are strictly stronger than their non-incompressible counterparts.



## 2024/799

* Title: Symmetric Signcryption and E2EE Group Messaging in Keybase
* Authors: Joseph Jaeger, Akshaya Kumar, Igors Stepanovs
* [Permalink](https://eprint.iacr.org/2024/799)
* [Download](https://eprint.iacr.org/2024/799.pdf)

### Abstract

We introduce a new cryptographic primitive called symmetric signcryption, which differs from traditional signcryption because the sender and recipient share a secret key. We prove that a natural composition of symmetric encryption and signatures achieves
strong notions of security against attackers that can learn and control many keys. We then identify that the core encryption algorithm of the Keybase encrypted messaging protocol can be modeled as a symmetric signcryption scheme. We prove the security of
this algorithm, though our proof requires assuming non-standard, brittle security properties of the underlying primitives.



## 2024/800

* Title: A Note on Zero-Knowledge for NP and One-Way Functions
* Authors: Yanyi Liu, Noam Mazor, Rafael Pass
* [Permalink](https://eprint.iacr.org/2024/800)
* [Download](https://eprint.iacr.org/2024/800.pdf)

### Abstract

We present a simple alternative exposition of the the recent result of Hirahara and Nanashima (STOC’24) showing that one-way functions exist if (1) every language in NP has a zero-knowledge proof/argument and (2) ZKA contains non-trivial languages. Our
presentation does not rely on meta-complexity and we hope it may be useful for didactic purposes.



## 2024/801

* Title: Algebraic Structure of the Iterates of $\chi$
* Authors: Björn Kriepke, Gohar Kyureghyan
* [Permalink](https://eprint.iacr.org/2024/801)
* [Download](https://eprint.iacr.org/2024/801.pdf)

### Abstract

We consider the map $\chi:\mathbb{F}_2^n\to\mathbb{F}_2^n$ for $n$ odd given by $y=\chi(x)$ with $y_i=x_i+x_{i+2}(1+x_{i+1})$, where the indices are computed modulo $n$. We suggest a generalization of the map $\chi$ which we call generalized $\chi$-maps.
We show that these maps form an Abelian group which is isomorphic to the group of units in $\mathbb{F}_2[X]/(X^{(n+1)/2})$. Using this isomorphism we easily obtain closed-form expressions for iterates of $\chi$ and explain their properties.



## 2024/802

* Title: On Maximum Size Simultaneous Linear Approximations in Ascon and Keccak and Related Translation and Differential Properties
* Authors: Nicolas T. Courtois, Frédéric Amiel, Alexandre Bonnard de Fonvillars
* [Permalink](https://eprint.iacr.org/2024/802)
* [Download](https://eprint.iacr.org/2024/802.pdf)

### Abstract

In this paper we study the S-box known as Chi or \chi initially proposed by Daemen in 1995 and very widely used ever since in Keccak, Ascon, and many other. This type of ciphers is typically analyzed [in recent research] in terms of subspace trail
attacks [TeDi19] and vector space invariants. An interesting question is then, when different spaces are mapped to each other by translations with a constant.
In this paper we relax this fundamental question and we consider arbitrary sets of points and their translations. We generalize previous S-box partial linearization results on Keccak and Ascon from Eurocrypt 2017. We basically introduce new ways to
linearize the Ascon S-box to the maximum possible extent. On this basis we show further remarkable properties and some surprising connections between [simultaneous] linear and [prominent] differential properties. We exhibit a new family of maximum size
and optimal approximation properties with 11 points, beyond the maximum size of any set in the DDT table.
We prove a theorem which guarantees that this type of properties are stable by arbitrary input-side translations which holds for all quadratic permutations. All this will be placed in the context of previous work on classification of 5-bit quadratic
permutations.



## 2024/803

* Title: Can We Beat Three Halves Lower Bound?: (Im)Possibility of Reducing Communication Cost for Garbled Circuits
* Authors: Chunghun Baek, Taechan Kim
* [Permalink](https://eprint.iacr.org/2024/803)
* [Download](https://eprint.iacr.org/2024/803.pdf)

### Abstract

Recent improvements to garbled circuits are mainly focused on reducing their size.
The state-of-the-art construction of Rosulek and Roy (Crypto 2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting.
This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans (Eurocrypt 2015).
Whether their construction is optimal in a more inclusive model than the linear garbling model still remains open.

This paper begins by providing a comprehensive model for a large class of practical garbling schemes
and proves the lower bound for the size of the garbled AND gates in our model. We show that garbled AND gates require at least $1.5\kappa$ bits in our new model with the free-XOR setting.

It is remarkable to see that the construction by Rosulek and Roy is already optimal
despite the fact that our model possibly captures any potential extension of their construction.



## 2024/804

* Title: Analysis on Sliced Garbling via Algebraic Approach
* Authors: Taechan Kim
* [Permalink](https://eprint.iacr.org/2024/804)
* [Download](https://eprint.iacr.org/2024/804.pdf)

### Abstract

Recent improvements to garbled circuits are mainly focused on reducing their size.
The state-of-the-art construction of Rosulek and Roy~(Crypto~2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting.
This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans~(Eurocrypt~2015).

Recently, Ashur, Hazay, and Satish~(eprint 2024/389) proposed a scheme that requires $4/3\kappa + O(1)$ bits for garbling AND gates.
Precisely they extended the idea of \emph{slicing} introduced by Rosulek and Roy to garble 3-input gates of the form $g(u,v,w) := u(v+w)$.
By setting $w = 0$, it can be used to garble AND gates with the improved communication costs.

However, in this paper, we observe that the scheme proposed by Ashur, Hazy, and Satish leaks information on the permute bits,
thereby allowing the evaluator to reveal information on the private inputs.
To be precise, we show that in their garbling scheme, the evaluator can compute the bits $\alpha$ and $\beta + \gamma$,
where $\alpha$, $\beta$, and $\gamma$ are the private permute bits of the input labels $A$, $B$, and $C$, respectively.



## 2024/805

* Title: DiTRU: A Resurrection of NTRU over Dihedral Group
* Authors: Ali Raya, Vikas Kumar, Sugata Gangopadhyay
* [Permalink](https://eprint.iacr.org/2024/805)
* [Download](https://eprint.iacr.org/2024/805.pdf)

### Abstract

NTRU-like cryptosystems are among the most studied lattice-based post-quantum candidates. While most NTRU proposals have been introduced over a commutative ring of quotient polynomials, other rings can be used. Noncommutative algebra has been endorsed as
a direction to build new variants of NTRU a long time ago. The first attempt to construct a noncommutative variant was due to Hoffstein and Silverman motivated by more resistance to lattice attack. The scheme has been built over the group ring of a
dihedral group. However, their design differed from standard NTRU and soon was found vulnerable to algebraic attacks. In this work, we revive the group ring NTRU over the dihedral group as an instance of the GR-NTRU framework.
Unlike many proposals of noncommutative variants in the literature, our work focuses on putting the scheme into practice. We clear all the aspects that make our scheme implementable by proposing an efficient inversion algorithm over the new setting of
the noncommutative ring, describing the decryption failure model, and analyzing the lattice associated with our instantiation. Finally, we discuss the best-known attacks against our scheme and provide an implementation targeting 128-bit, 192-bit, and 256-
bit levels of security as proof of its practicality.



## 2024/806

* Title: Resettable Statistical Zero-Knowledge for NP
* Authors: Susumu Kiyoshima
* [Permalink](https://eprint.iacr.org/2024/806)
* [Download](https://eprint.iacr.org/2024/806.pdf)

### Abstract

Resettable statistical zero-knowledge [Garg--Ostrovsky--Visconti--Wadia, TCC 2012] is a strong privacy notion that guarantees statistical zero-knowledge even when the prover uses the same randomness in multiple proofs.

In this paper, we show an equivalence of resettable statistical zero-knowledge arguments for $NP$ and witness encryption schemes for $NP$.
- Positive result: For any $NP$ language $L$, a resettable statistical zero-knowledge argument for $L$ can be constructed from a witness encryption scheme for $L$ under the assumption of the existence of one-way functions.
- Negative result: The existence of even resettable statistical witness-indistinguishable arguments for $NP$ imply the existence of witness encryption schemes for $NP$ under the assumption of the existence of one-way functions.
The positive result is obtained by naturally extending existing techniques (and is likely to be already well-known among experts). The negative result is our main technical contribution.

To explore workarounds for the negative result, we also consider resettable security in a model where the honest party's randomness is only reused with fixed inputs. We show that resettable statistically hiding commitment schemes are impossible even in
this model.



## 2024/807

* Title: Optimal Consensus in the Presence of Overlapping Faults and Total Omission
* Authors: Julian Loss, Kecheng Shi, Gilad Stern
* [Permalink](https://eprint.iacr.org/2024/807)
* [Download](https://eprint.iacr.org/2024/807.pdf)

### Abstract

Understanding the fault tolerance of Byzantine Agreement protocols is an important question in distributed computing. While the setting of Byzantine faults has been thoroughly explored in the literature, the (arguably more realistic) omission fault
setting is far less studied. In this paper, we revisit the recent work of Loss and Stern who gave the first protocol in the mixed fault model tolerating $t$ Byzantine faults, $s$ send faults, and $r$ receive faults, when $2t+r+s<n$ and omission faults do
not overlap. We observe that their protocol makes no guarantees when omission faults can overlap, i.e., when parties can simultaneously have send and receive faults. We give the first protocol that overcomes this limitation and tolerates the same number
of potentially overlapping faults. We then study, for the first time, the total omission setting where all parties can become omission faulty. This setting is motivated by real-world scenarios where every party may experience connectivity issues from
time to time, yet agreement should still hold for the parties who manage to output values. We show the first agreement protocol in this setting with parameters $s<n$ and $s+r=n$. On the other hand, we prove that there is no consensus protocol for the
total omission setting which tolerates even a single overlapping omission fault, i.e., where $s+r=n+1$ and $s>2$, or a broadcast protocol for $s+r=n$ and $s>1$ even without overlapping faults.



## 2024/808

* Title: Arma: Byzantine Fault Tolerant Consensus with Horizontal Scalability
* Authors: Yacov Manevich, Hagar Meir, Kaoutar Elkhiyaoui, Yoav Tock, May Buzaglo
* [Permalink](https://eprint.iacr.org/2024/808)
* [Download](https://eprint.iacr.org/2024/808.pdf)

### Abstract

Arma is a Byzantine Fault Tolerant (BFT) consensus system designed to
achieve horizontal scalability across all hardware resources: network bandwidth, CPU, and disk I/O. As opposed to preceding BFT protocols, Arma separates the dissemination and validation of client transactions from the consensus process, restricting the latter to totally ordering only metadata of batches of transactions.
This separation enables each party to distribute compute and storage resources for transaction validation, dissemination and disk I/O among multiple machines, resulting in horizontal scalability.
Additionally, Arma ensures censorship resistance by imposing a maximum
time limit on the inclusion of client transactions. We built and evaluated two Arma prototypes. The first is an independent system handling over 200,000 transactions per second, the second integrated into Hyperledger Fabric, speeding its consensus by an
order of magnitude.



## 2024/809

* Title: Reducing Overdefined Systems of Polynomial Equations Derived from Small Scale Variants of the AES via Data Mining Methods
* Authors: Jana Berušková, Martin Jureček, Olha Jurečková
* [Permalink](https://eprint.iacr.org/2024/809)
* [Download](https://eprint.iacr.org/2024/809.pdf)

### Abstract

This paper deals with reducing the secret key computation time of small scale variants of the AES cipher using algebraic cryptanalysis, which is accelerated by data mining methods. This work is based on the known plaintext attack and aims to speed up the
calculation of the secret key by processing the polynomial equations extracted from plaintext-ciphertext pairs. Specifically, we propose to transform the overdefined system of polynomial equations over GF(2) into a new system so that the computation of
the Gröbner basis using the F4 algorithm takes less time than in the case of the original system. The main idea is to group similar polynomials into clusters, and for each cluster, sum the two most similar polynomials, resulting in simpler polynomials.
We compare different data mining techniques for finding similar polynomials, such as clustering or locality-sensitive hashing (LSH). Experimental results show that using the LSH technique, we get a system of equations for which we can calculate the Grö
bner basis the fastest compared to the other methods that we consider in this work. Experimental results also show that the time to calculate the Gröbner basis for the transformed system of equations is significantly reduced compared to the case when
the Gröbner basis was calculated from the original non-transformed system. This paper demonstrates that reducing an overdefined system of equations reduces the computation time for finding a secret key.



## 2024/810

* Title: The Perils of Limited Key Reuse: Adaptive and Parallel Mismatch Attacks with Post-processing Against Kyber
* Authors: Qian Guo, Erik Mårtensson, Adrian Åström
* [Permalink](https://eprint.iacr.org/2024/810)
* [Download](https://eprint.iacr.org/2024/810.pdf)

### Abstract

In this paper, we study the robustness of Kyber, the Learning With Errors (LWE)-based Key Encapsulation Mechanism (KEM) chosen for standardization by NIST, against key mismatch attacks. We demonstrate that Kyber's security levels can be compromised with
a few mismatch queries by striking a balance between the parallelization level and the cost of lattice reduction for post-processing. This highlights the imperative need to strictly prohibit key reuse in CPA-secure Kyber.

We further propose an adaptive method to enhance parallel mismatch
attacks, initially proposed by Shao et al. at AsiaCCS 2024, thereby significantly reducing query complexity. This method combines the adaptive attack with post-processing via lattice reduction to retrieve the final secret key entries. Our method proves
its efficacy by reducing query complexity by 14.6 % for Kyber512 and 7.5 % for Kyber768/Kyber1024.

Furthermore, this approach has the potential to substantially improve multi-value Plaintext-Checking (PC) oracle-based side-channel attacks against the CCA-secure version of Kyber KEM.



## 2024/811

* Title: Traceable Secret Sharing Based on the Chinese Remainder Theorem
* Authors: Charlotte Hoffmann
* [Permalink](https://eprint.iacr.org/2024/811)
* [Download](https://eprint.iacr.org/2024/811.pdf)

### Abstract

Traceable threshold secret sharing schemes, introduced by Goyal, Song and Srinivasan (CRYPTO'21), allow to provably trace leaked shares to the parties that leaked them. The authors give the first definition and construction of traceable secret sharing
schemes. However, the size of the shares in their construction are quadratic in the size of the secret. Boneh, Partap and Rotem (CRYPTO'24) recently proposed a new definition of traceable secret sharing and the first practical constructions. In their
definition, one considers a reconstruction box $R$ that contains $f$ leaked shares and, on input $t-f$ additional shares, outputs the secret $s$. A scheme is traceable if one can find out the leaked shares inside the box $R$ by only getting black-box
access to $R$. Boneh, Partap and Rotem give constructions from Shamir's secret sharing and Blakely's secret sharing. The constructions are efficient as the size of the secret shares is only twice the size of the secret.

In this work we present the first traceable secret sharing scheme based on the Chinese remainder theorem. This was stated as an open problem by Boneh, Partap and Rotem, as it gives rise to traceable secret sharing with weighted threshold access
structures. The scheme is based on Mignotte's secret sharing and increases the size of the shares of the standard Mignotte secret sharing scheme by a factor of $2$.



## 2024/812

* Title: Relations among new CCA security notions for approximate FHE
* Authors: Sébastien Canard, Caroline Fontaine, Duong Hieu Phan, David Pointcheval, Marc Renard, Renaud Sirdey
* [Permalink](https://eprint.iacr.org/2024/812)
* [Download](https://eprint.iacr.org/2024/812.pdf)

### Abstract

In a recent Eurocrypt'24 paper, Manulis and Nguyen have proposed a new CCA security notion, vCCA, and associated construction blueprints to leverage both CPA-secure and correct FHE beyond the CCA1 security barrier. However, because their approach is only
valid under the correctness assumption, it leaves a large part of the FHE spectrum uncovered as many FHE schemes used in practice turn out to be approximate and, as such, do not satisfy the correctness assumption. In this paper, we improve their work by
defining and investigating a variant of their security notion which is suitable for a more general case where approximate FHE are included. As the passive security of approximate FHE schemes is more appropriately captured by CPAD rather than CPA security,
we start from the former notion to define our vCCAD new security notion. Although, we show that vCCA and vCCAD are equivalent when the correctness assumption holds, we establish that vCCAD security is strictly stronger than vCCA security in the general
case. In doing so, we interestingly establish several new separation results between variants of CPAD security of increasing strength. This allows us to clarify the relationship between vCCA security and CPAD security, and to reveal that the security
notions landscape is much simpler for exact FHE than when approximate ones are included --- in which case, for example, we establish that multiple challenges security notions are strictly stronger than single-challenge ones for both CPAD and vCCAD
security. Lastly, we also give concrete construction blueprints, showing how to leverage some of the blueprints proposed by Manulis and Nguyen to achieve vCCAD security. As a result, vCCAD security is the strongest CCA security notion so far known to be
achievable by both correct and approximate FHE schemes.



## 2024/813

* Title: How to Redact the Bitcoin Backbone Protocol
* Authors: Mehmet Sabir Kiraz, Enrique Larraia, Owen Vaughan
* [Permalink](https://eprint.iacr.org/2024/813)
* [Download](https://eprint.iacr.org/2024/813.pdf)

### Abstract

We explain how to extend the Bitcoin backbone model of Garay et al. (Eurocrypt, 2015) to accommodate for redactable blockchains. Our extension captures fluid blockchain-based databases (with mutability requirements) and compliance with existing
legislation, such as the GDPR right to be forgotten, or the need to erase offending data from nodes’ databases that would otherwise provoke legal shutdowns. Our redactable backbone protocol retains the essential properties of blockchains. Leveraging
zero-knowledge proofs, old data can be erased without requiring trusted third parties or heuristics about past chain validation. Our solution can be implemented on Bitcoin immediately without hard-forks, and it is scalable. It allows the redaction of
data from UTXOs or unconfirmed transactions that have not yet flooded the network, while guaranteeing invariance of the Bitcoin state. Thus, offending data does not need to persist in the system, not even temporarily.



## 2024/814

* Title: Succinct Homomorphic Secret Sharing
* Authors: Damiano Abram, Lawrence Roy, Peter Scholl
* [Permalink](https://eprint.iacr.org/2024/814)
* [Download](https://eprint.iacr.org/2024/814.pdf)

### Abstract


[continued in next message]

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