CS Paper Radar

Cryptanalysis and Repair of "Decentralized Multi-authority ABE for NC$^1$ from BDH"

Xingwang Wang

cs.CR ·submitted 2026-10-21 05:30 UTC · v2
theory

Abstract

We present a plaintext-recovery attack on both the DBDH-based construction and the CBDH-based variant of Datta, Komargodski, and Waters (Journal of Cryptology, 2023). The attack succeeds with probability one in the claimed static security model using one corrupt authority and two users, each unauthorized even when granted the corrupt authority's attribute. The flaw is an invalid extension of the LSSS matrix-normalization lemma originating with Rouselakis and Waters (FC,~2015): preserving complete-share distributions does not preserve coordinate-wise ciphertext masks, which a corrupt authority can expose to remove identity binding from other users' shares. For both variants, replacing these masks with independent full linear sharings of zero preserves correctness and restores ciphertext-distribution invariance. We prove static security of both repaired variants in the random oracle model under their respective BDH assumptions, using the original hardcore-bit convention for the CBDH variant. Both proofs allow adaptive identity-hash queries. The modification retains the original matrix-width and row-labeling restrictions, keys, decryption, and ciphertext size, requiring only additional encryption randomness and finite-field arithmetic. We also attack both multi-authority attribute-based inner-product functional encryption constructions of Datta and Pal (PKC, 2023) and establish correctness and matrix-substitution invariance of the same repair. We prove static security of the repaired small-universe construction under asymmetric DBDH. For the large-universe construction, we identify a missing source-group encoding in the original reduction and give a complete static security proof under an augmented $L$-DBDH assumption, whose generic bilinear group hardness we establish.

Closest papers

Nearest neighbours by meaning across the whole index.

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

cs.CR ·2026-08-29 ·Sayantan Mukherjee
theory similarity 0.67
Abstract

However, no known work considered the functionality requirement in its most realistic setting. We propose a new security definition of BAEKS in the multi-user (with adaptive corruptions) and multi-challenge (both in terms of ciphertext and trapdoor in an interleaved manner) settings. We also study the question of the unforgeability of BAEKS. In fact, our strong hiding requirement already implies a significant amount of unforgeability. We then propose a new BAEKS construction in the bilinear pairing groups. We prove this scheme achieves adaptive tight full-hiding security under (almost) standard MDDH assumptions. Restricting our BAEKS construction for a single receiver also gives an efficient and tightly secure PAEKS construction. We further run experiments to implement and evaluate our scheme.

0.22

Constant-Rate Certified Deletion

cs.CR quant-ph ·2026-10-02 ·Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada
top venue similarity 0.58
Abstract

We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number of qubits per encrypted bit of certified-deletable plaintext. In contrast, we obtain the first constant-rate constructions in the plain model that achieve certified deletion while preserving everlasting security. Our approach applies to a wide range of "all-or-nothing"-type primitives based on BB84-style encodings, including commitment schemes, public-key encryption, attribute-based encryption, and fully homomorphic encryption. Beyond this class, we also obtain constant-rate certified deletion for primitives built from subspace coset states, such as blind delegation, secure software leasing, functional encryption, and differing-inputs iO, and CCA-PKE. Importantly, our framework does not introduce any additional assumptions beyond those required by the underlying certified deletion primitives. Finally, under the hardness of SIS, we show that public verifiability can be incorporated into BB84- and coset-based certified deletion. In combination with our constant-rate constructions, this yields publicly verifiable certified deletion schemes with constant rate.

0.38

zk-DEAP: A Zero-Knowledge Decentralized Encrypted Aggregation Protocol

cs.CR ·2026-11-04 ·Jude Ramanan, Georgiana Haldeman, Noah Apthorpe
similarity 0.58
Abstract · 19 pages, 5 figures, 5 tables

Secure aggregation in domains such as federated learning, Internet of Things, and voting requires operating on private inputs while preserving confidentiality, verifying that each input satisfies constraints, and avoiding trusted parties. Existing protocols achieve at most two of these requirements. We present zk-DEAP, a protocol combining lifted ElGamal homomorphic encryption, FROST threshold cryptography, and zero-knowledge proofs (Bulletproofs, zk-SNARKs, or zk-STARKs) for fully decentralized, verifiable, privacy-preserving aggregation. Our core technical contribution is a cryptographic binding mechanism preventing substitution attacks, where a valid proof for one input is paired with a ciphertext encrypting a different, malicious value. For Bulletproofs, we bind via ciphertext-derived randomness modification. For zk-SNARKs/zk-STARKs, to bind across algebraic structures (a well-known challenge in practical cryptography), we introduce a novel blinded arithmetic hash commitment with an embedded Schnorr constraint. These binding techniques force the ZKP's private witness to equal the encrypted value, ensuring any circuit-verified constraint applies to the ciphertext. We implement three production-ready, defense-in-depth variants in Rust and evaluate across 5-500 participants. Compared to unverified aggregation, zk-DEAP adds modest overhead while providing cryptographic guarantees against input manipulation that statistical defenses cannot match.

0.28

A Bleichenbacher bit-by-bit oracle attack from partial message knowledge

cs.CR ·2026-11-15 ·Juan Carlos García Escartín
similarity 0.58
Abstract · Comments welcome

Oracle attacks show the importance of a correct implementation of cryptographic standards when translated into code. A notable example is the Bleichenbacher attack on RSA with PKCS#1 v1.5 padding and all the improvements that have been suggested over the decades. This paper shows how an attacker knowing a few least significant bytes of an RSA message can take advantage of a server with an oracle side-channel to decrypt the full message bit by bit. We will consider two oracles that can be tested with chosen ciphertexts: one revealing whether the decrypted message starts with the 00 02 bytes and a second one revealing if the decrypted message is fully PKCS compliant. For an attacker knowing the three least significant bytes of the message, the first oracle provides an attack where one oracle call gives the next least significant bit of the message and the second an attack which requires, with high probability, a small constant number of oracle calls to the oracle, with a constant which depends on the length of the message and the desired probability of success. The attack divides the message bits into two sections, one with the known part and one with the unknown part, and then chooses transformations that will keep the unknown part, except for the last unknown bit, orders of magnitude below the integer coming from the known part. The resulting string either gives a valid padding or not depending on the value of the unknown bit. The attacker can minimize the number of oracle calls at the cost of some local computation. Finally, the same method is adapted to show how it can also be used to extract the few least significant bytes of the message with an increased cost where the main complexity is finding a second valid message with a correct padding starting from the original captured ciphertext.

0.37

Leakage-Resilient Computation via Matrix Refreshing

cs.CR ·2026-11-03 ·Stefan Dziembowski, Sebastian Faust
theory similarity 0.56
Abstract

Leakage-resilient cryptography protects secrets against side-channel attacks, in which a physical implementation reveals partial information about its internal state. A fundamental primitive in this area is a leakage-resilient storage, which allows a secret to be stored in a way that remains secure even if an adversary learns some information about the storage's internal state. A popular approach represents a secret as the inner product of two $n$-bit vectors, called shares. The shares are stored and processed separately by two parts of the implementation, called the left and right parties. Because leakage accumulates over time, the shares must be refreshed repeatedly. We prove that a simple refresh, in which the left party multiplies its share by a uniform invertible matrix $M$ and the right party multiplies its share by $M^{-1}$, is secure under continual local leakage. After $T$ refreshes, each allowing at most $λ$ bits of leakage per party, the transcripts for two stored secrets are at statistical distance at most $C\cdot T\cdot 2^{6λ-n/9}$ for an absolute constant $C$. We also obtain a Boolean-circuit compiler with statistical privacy error at most $C\cdot S\cdot 2^{18λ-n/27}$ for $S$ operations and at most $λ$ bits of local leakage per party per operation. The guarantee covers repeated stateful evaluations with adaptively chosen public inputs, with $S$ counting all operations across invocations. Thus, for polynomial-size circuits, a constant leakage fraction is tolerated with share length depending only on the security parameter. We formalize the refreshing bound, the composition and compiler guarantees, and the expected-work bounds in Lean 4. Our results also provide efficient simulation: the leakage can be reproduced from the public inputs and the circuit outputs alone, with expected polynomial overhead.

0.20

Physalia: Redistribution-Resistant Content Protection for Decentralized Storage

cs.CR ·2026-09-23 ·Giacomo Giuliari, Karl Wüst
similarity 0.56
Abstract

In decentralized storage systems, access control is often implemented by encrypting the data before upload and sharing the decryption key with authorized parties. A leaked key, however, makes the data publicly accessible, which lowers the barrier to content piracy below that of traditional systems, where piracy requires redistributing the full data. We present Physalia, an end-to-end access-control system for decentralized storage that secret-shares the data itself, instead of just the key, across multiple servers. Leaking the data then requires transmitting it in full: We formalize this intuition and introduce the redistribution bandwidth an adversary must pay to leak protected content and show that Physalia raises it to the size of the data. Sharing across untrusted servers requires robustness against corrupted shares. We develop a robustness transform that turns any computational secret sharing scheme into a robust one and which is of independent interest. In contrast to existing schemes that rely on error correction, it uses signatures with ephemeral keys and adds only constant-size metadata per share. We show that this transform is secure and evaluate Physalia end-to-end on the Walrus decentralized storage system with an on-chain access policy.

0.28

Simple Extremely Lossy Functions from Small-Exponent Hashing

cs.CR cs.CC ·2026-10-05 ·Damiano Abram, Agni Datta, Archisman Dutta, Lawrence Roy
similarity 0.55
Abstract

Extremely Lossy Functions (ELFs) are a standard model primitive that captures many useful properties of random oracles (Zhandry, Crypto 2016). While there are many variations of ELFs with additional properties, every construction (excluding obfuscation) has followed essentially the same template of bootstrapping from a sequence of ELFs secure only against fixed-size adversaries, and every construction was based on only the exponential hardness of DDH (or $k$-Lin), an assumption that is only reasonable over elliptic curves. We introduce and construct Extremely Lossy Trapdoor Hashing (ELTDH), a stronger notion that implies all known variations of ELFs. Our construction achieves ELTDH in one go, without bootstrapping from schemes secure for only fixed-size adversaries, which makes it simpler and more efficient than existing ELFs. We assume exponential security of the small-exponent discrete logarithm, together with polynomial security of decisional composite residuosity (DCR). Exponential security is only required in the size of the secret exponent, not the size of the group, so the assumption plausibly holds for multiplication modulo $N^2$ (and for many other cryptographic groups), despite the subexponential-time discrete logarithm attacks from index calculus. Our results diversify the assumptions underlying ELFs, while also giving a simpler construction.

0.23

Improved Degree Tables for Secure Distributed Matrix Multiplication

cs.IT math.CO ·2026-09-06 ·John Byrne, Rafael G. L. D'Oliveira, Michael Tait
theory similarity 0.55
Abstract

In secure distributed matrix multiplication, a user wishes to compute the product of two matrices with the assistance of servers, in such a way that any $T$ colluding servers learn nothing about either matrix. Degree tables are a combinatorial tool for constructing polynomial codes for this problem and underlie several state-of-the-art schemes, including $\mathsf{GASP}_r$, $\mathsf{GASP}_{r,s}$, and $\mathsf{DOG}_{r,s}$. We introduce a periodic-gap framework for constructing degree tables that contains these three families as special cases and leads to two new constructions, $\mathsf{SHIFT}_{r,s}$ and $\mathsf{COVER}_r$. We determine their exact recovery thresholds and show that, in many cases, they outperform the current state of the art. We also prove a new lower bound on the recovery threshold of ordinary integer degree tables. In the balanced case, in which the partitioning parameters and the security parameter are equal, we sharpen this bound to match $\mathsf{SHIFT}_{r,s}$ up to lower-order terms, showing that it is asymptotically optimal among degree-table constructions.

0.14