On Ideal Secret-Sharing Schemes for $k$-homogeneous access structures

• URL: http://arxiv.org/abs/2309.07479v1
• Date: Thu, 14 Sep 2023 07:37:19 GMT
• Title: On Ideal Secret-Sharing Schemes for $k$-homogeneous access structures
• Authors: Younjin Kim, Jihye Kwon, Hyang-Sook Lee,
• Abstract summary: A $k$-homogeneous access structure is represented by a $k$-uniform hypergraph $mathcalH$. In this paper, we characterize ideal $k$-homogeneous access structures using the independent sequence method.
• Score: 0.16385815610837165
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: A $k$-uniform hypergraph is a hypergraph where each $k$-hyperedge has exactly $k$ vertices. A $k$-homogeneous access structure is represented by a $k$-uniform hypergraph $\mathcal{H}$, in which the participants correspond to the vertices of hypergraph $\mathcal{H}$. A set of vertices can reconstruct the secret value from their shares if they are connected by a $k$-hyperedge, while a set of non-adjacent vertices does not obtain any information about the secret. One parameter for measuring the efficiency of a secret sharing scheme is the information rate, defined as the ratio between the length of the secret and the maximum length of the shares given to the participants. Secret sharing schemes with an information rate equal to one are called ideal secret sharing schemes. An access structure is considered ideal if an ideal secret sharing scheme can realize it. Characterizing ideal access structures is one of the important problems in secret sharing schemes. The characterization of ideal access structures has been studied by many authors~\cite{BD, CT,JZB, FP1,FP2,DS1,TD}. In this paper, we characterize ideal $k$-homogeneous access structures using the independent sequence method. In particular, we prove that the reduced access structure of $\Gamma$ is an $(k, n)$-threshold access structure when the optimal information rate of $\Gamma$ is larger than $\frac{k-1}{k}$, where $\Gamma$ is a $k$-homogeneous access structure satisfying specific criteria.

Related papers

• Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
  We show how to parameterise topological masks as a learnable function of a weighted adjacency matrix. Our efficient masking algorithms provide strong performance gains for tasks on image and point cloud data.
  arXiv  Detail & Related papers  (2024-10-04T14:24:06Z)
• Low-degree Security of the Planted Random Subgraph Problem [12.329446579556606]
  We prove the low-degree hardness of detecting planted random subgraphs up to $kleq n1 - Omega(1)$. We apply the conjecture towards (1) communication-optimal multiparty PSM protocols for random functions and (2) bit secret sharing with share size $(1 + epsilon)log n$ for any $epsilon > 0$ in which arbitrary minimal coalitions of up to $r$ parties can reconstruct and secrecy holds against all unqualified subsets of up to $ell = o(epsilon log n)1/(r-1)$
  arXiv  Detail & Related papers  (2024-09-24T16:42:00Z)
• 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)
• A Unified Characterization of Private Learnability via Graph Theory [18.364498500697596]
  We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. We identify graph-theoretic dimensions that characterize DP learnability: the clique dimension and fractional clique dimension. We also reveal properties of the contradiction graph which may be of independent interest.
  arXiv  Detail & Related papers  (2023-04-08T12:25:08Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries. We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $pi*$. As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.
  arXiv  Detail & Related papers  (2022-02-22T04:14:45Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  We study the approximation of two-layer compositions $f(x) = g(phi(x))$ via deep networks with ReLU activation. We focus on two intuitive and practically relevant choices for $phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets.
  arXiv  Detail & Related papers  (2020-08-06T09:50:29Z)
• Cospectrality preserving graph modifications and eigenvector properties via walk equivalence of vertices [0.0]
  Cospectrality is a powerful generalization of exchange symmetry and can be applied to all real-valued symmetric matrices. We show that the powers of a matrix with cospectral vertices induce further local relations on its eigenvectors. Our work paves the way for flexibly exploiting hidden structural symmetries in the design of generic complex network-like systems.
  arXiv  Detail & Related papers  (2020-07-15T10:54:31Z)

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.