Ciphertext-Policy ABE for $\mathsf{NC}^1$ Circuits with Constant-Size Ciphertexts from Succinct LWE

• URL: http://arxiv.org/abs/2603.16117v1
• Date: Tue, 17 Mar 2026 04:33:30 GMT
• Title: Ciphertext-Policy ABE for $\mathsf{NC}^1$ Circuits with Constant-Size Ciphertexts from Succinct LWE
• Abstract summary: We construct a lattice-based ciphertext-policy attribute-based encryption scheme for $mathsfNC1$ access policies with constant-size ciphertexts.<n>Our construction is selectively secure under the $operatornamepoly()$-succinct LWE assumption introduced by Wee.
• Score: 15.07118376631638
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We construct a lattice-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for $\mathsf{NC}^1$ access policies with constant-size ciphertexts. Let $λ$ be the security parameter. For an $\mathsf{NC}^1$ circuit of depth $d$ and size $s$ on $\ell$-bit inputs, our scheme has the public-key and ciphertext sizes $O(1)$ (independent of $d$), and secret-key size $O(\ell)$, where the $O(\cdot)$ hides $\operatorname{poly}(λ)$ factors. As an application, we obtain a broadcast encryption scheme for $N$ users with ciphertext size $\operatorname{poly}(λ)$ independent of $\log N$ and key sizes $\operatorname{poly}(λ,\log N)$. Our construction is selectively secure in the standard model under the $\operatorname{poly}(λ)$-succinct LWE assumption introduced by Wee (CRYPTO~2024).

Related papers

• Efficient Fuzzy Private Set Intersection from Secret-shared OPRF [41.88845480337768]
  Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items $q in Q$ for which there exists some $w in W$ under a given distance metric.<n>We propose efficient FPSI protocols for $L_p in [1, infty]$ distance metrics.<n>Our protocols achieve linear communication and computation complexity in the set sizes $m,n$, the dimension $d$, and the distance threshold $$.
  arXiv  Detail & Related papers  (2026-04-16T11:51:25Z)
• Bilinear Compressive Security [4.3725047448751235]
  We study a rather idealized known attack for recovering $Q$ from repeated observations of $y$'s for different, known $x_k$.<n>Our main result for BCS states that under a weak symmetry condition on the filter $h$, recovering $Q$ will require extensive sampling from transmissions of $Omegaleft(maxleft(n,(n/s)2right)$ messages $x_k$ if they are $s$-sparse.
  arXiv  Detail & Related papers  (2025-10-17T07:32:25Z)
• A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group [0.0]
  We propose a symmetric-key cryptosystem whose linear action takes place instead in the Burnside ring $A(G)$ of a compact Lie group $G$.<n>Messages of arbitrary finite length are encoded as finitely supported elements of $A(G)$ and encrypted via the Burnside product with $k$.<n>We show that any finite set of observations constrains the action only on a finite-rank submodule $W_Lsubset A(O(2))$, and we show information-theoretic non-identifiability of the key from such data.
  arXiv  Detail & Related papers  (2025-10-13T01:57:22Z)
• Homomorphic encryption schemes based on coding theory and polynomials [0.0]
  Homomorphic encryption is a powerful cryptographic tool that enables secure computations on the private data.<n>This is crucial for any sensitive application running in the Cloud, because we must protect data privacy even in the case when the server has falled victim to a cyber attack.
  arXiv  Detail & Related papers  (2025-09-17T07:58:18Z)
• Compact Lattice-Coded (Multi-Recipient) Kyber without CLT Independence Assumption [4.317605401561789]
  This work presents a joint design of encoding and encryption procedures for public key encryptions (PKEs) and key encapsulation mechanism (KEMs) such as Kyber.<n>Our design features two techniques: ciphertext packing and lattice packing.<n>Both DFR and CER are greatly decreased thanks to ciphertext packing and lattice packing.
  arXiv  Detail & Related papers  (2025-04-24T01:39:36Z)
• Optimal Computational Secret Sharing [51.599517747577266]
  In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants.<n>We present a construction achieving a share size of $tfrac|S|t + |K|t$.
  arXiv  Detail & Related papers  (2025-02-04T23:37:16Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Conditional Encryption with Applications to Secure Personalized Password Typo Correction [7.443139252028032]
  We introduce the notion of a conditional encryption scheme as an extension of public key encryption. A conditional encryption scheme for a binary predicate $P$ adds a new conditional encryption algorithm $mathsfCEnc$. We demonstrate how to use conditional encryption to improve the security of personalized password typo correction systems.
  arXiv  Detail & Related papers  (2024-09-10T00:49:40Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.