CS Paper Radar

Simple Extremely Lossy Functions from Small-Exponent Hashing

Damiano Abram, Agni Datta, Archisman Dutta, Lawrence Roy

cs.CR cs.CC ·submitted 2026-10-05 20:20 UTC · v1

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.

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.64
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

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

cs.CR ·2026-11-04 ·Jude Ramanan, Georgiana Haldeman, Noah Apthorpe
similarity 0.63
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 Complexity-Theoretic Approach to Proofs of Space

cs.CR cs.CC ·2026-08-10 ·Marshall Ball, Jiaxin Guan
published similarity 0.59
Abstract

A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information. To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions. We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.

0.22

An Explicit Below Half Threshold Bound for the Local Leakage Resilience of Shamir's Secret Sharing Scheme

cs.CR cs.IT ·2026-11-09 ·Cheng Zhang, Xin Wang, Xiangliang Kong
similarity 0.59
Abstract

As a fundamental cryptographic primitive, secret sharing distributes a secret among multiple parties and allows certain authorized parties to recover the secret while preventing unauthorized parties from knowing the secret. However, local leakage from each party member allows an adversary to learn partial information from each share, which is not guaranteed by traditional security. In this paper, we study bounds on the reconstruction threshold of Shamir's secret sharing scheme over prime fields against arbitrary 1-bit local leakage. We show that, for all sufficiently large $n$ and every prime $p>n$, the $(n,t)$-Shamir's scheme is $\exp(-Ω(n))$-resilient whenever $t/n\geq 0.489$, for any choice of distinct nonzero evaluation points. Our proof refines the dual-code list recovery analysis and combines complementary Fourier estimates according to the support sizes and biases of the leakage functions, yielding an improved explicit reconstruction threshold bound.

0.17

Symmetric Cryptography via Dirichlet Convolution

cs.CR cs.IT ·2026-10-02 ·Artur Sowa, Elias Hassani Sangani, Francis Bui, Grant Harris, Jonathan Norton
similarity 0.58
Abstract · 19 pages, 2 figures, 1 table

We discuss a new symmetric-key cipher for digital data encryption. Its implementation is fast, memory efficient, and resilient against classical, AI-assisted, and quantum attacks. Let $x$, $k$, and $c$ be elements of a finite abelian group $G$ with operation $+$ and neutral element $0$. Suppose one is given ciphertext $c=x+k$. Retrieving the plaintext $x=c-k$ from the ciphertext is trivial when the key $k$ is known. Without the key, however, recovering $x$ amounts to a blind search. Even if an efficient criterion were available for identifying the plaintext among all group elements, the average number of trials would remain prohibitively large when the group is sufficiently large. The challenge in constructing a practical cryptosystem is therefore to identify a sufficiently rich group $G$, together with efficient algorithms that enable an immersion of \emph{real digital data} into $G$ and efficient evaluation of the group operations. The proposed cipher is based on generalized Dirichlet convolution over finite fields. We investigate its security against plaintext attacks from an information-theoretic perspective. The nonlocal structure of Dirichlet convolution naturally permits plaintext salting, providing protection against plaintext attacks while allowing controlled key reuse. We establish perfect masking properties over finite fields and prove that the resulting cipher achieves information-theoretic security under key reuse when the underlying arithmetic is carried out in $\mathbb{F}_p$ with $p>2$. For arithmetic over $\mathbb{F}_2$, some information leakage remains, leading to a finite key-reuse budget.

0.41

Improved lower bounds for decomposable randomized encoding

cs.CC cs.CRcs.DM ·2026-09-16 ·Justin Holmgren, Kewen Wu
theory similarity 0.58
Abstract · 24 pages

A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $Ω(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $Ω(n^2)$ lower bound on DRE size for non-explicit Boolean functions.

0.46

MCSI: A Masked Commutative Supersingular Isogeny Key Exchange with Blinded Ephemeral Keys

cs.CR math.NT ·2026-08-23 ·Furkan Cifci, Osman Emre Donder, Reyyan Cifci
theorycode/data similarity 0.57
Abstract · 38 pages, 6 figures, 6 tables. Reference implementation included as ancillary files and at https://github.com/FurkanCifci/mcsi-key-exchange

We introduce MCSI, a two message key exchange we design over the CSIDH class group action, in which each party sends its ephemeral public element under an authenticated encryption keyed by the value the two static keys determine. The design gives implicit mutual authentication, hides the ephemeral element from an eavesdropper, and lets a recipient discard an unauthenticated message after one tag check rather than after an evaluation of the group action, which is four orders of magnitude more expensive. On the analytic side, we prove that our protocol is correct with zero error, and prove three statements in the random oracle model, all reducing to the strong parallelisation problem: indistinguishability of the session key against a passive adversary, confidentiality of the blinded ephemeral element, and integrity of the blinded transport. None uses the decisional group action assumption, which is false for class group actions of non-prime discriminant. We also show that a blinding key cannot come from the session secret it is meant to establish. To instantiate the design we select parameters and show that a prime chosen for elliptic curve discrete logarithms is unusable: for $p = 2^{521}-1$, the NIST P-521 prime, the action admits no efficiently evaluable generator. On the practical side, we build and test the design. We implement the protocol twice, in C and independently in Python, cross check the two, and measure what a session costs in field operations, time and memory. We also audit our code for secret dependent control flow: the field arithmetic and the symmetric layer show none, while the group action leaks the key by construction, and two hundred timings separate two keys whose one-norms differ by five out of 370. Finally, we state what we do not prove, among them security under ephemeral key reveal, forward secrecy of the blinding, and constant time execution.

0.42

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.57
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