Public key cryptosystems based on Iterated Functions Systems

• URL: http://arxiv.org/abs/2309.05917v1
• Date: Tue, 12 Sep 2023 02:12:39 GMT
• Title: Public key cryptosystems based on Iterated Functions Systems
• Authors: Jacques Peyriere, Fengxia Liu, Zhiyong Zheng, Zixian Gong,
• Abstract summary: We define a cryptosystem whose public key is$g$. The message to be encrypted is a word$w and the associated cryptogram is $Phi_g,w$. The private key allows to recover $Phi_f,w$ from $Phi_g,w$.
• Score: 2.4374097382908477
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Let $f=(f_0,f_1,\dots, f_{\nu-1})$ be a collection of one-to-one functions from some space~$X$ into itself such that the sets $f_j(X)$ are disjoint. If $w=w_1w_2\cdots w_k$ is a word on the alphabet $\{0,1,\dots,\nu-1\}$, let $\Phi_{f,w} = f_{w_1}\circ f_{w_2}\circ\cdots\circ f_{w_k}$. Given a function~$F$ of which we know that it can be written as $\Phi_{f,w}$, it is easy to recover~$w$. We give some examples of this situation where everything can be scrambled up by using some private key to get a new system $g=(g_1,g_2,\dots,g_{\nu-1})$ on another set~$Y$ in such a way that the images of the $g_j$ are no longer disjoint. We define a cryptosystem whose public key is~$g$. The message to be encrypted is a word~$w$ and the associated cryptogram is $\Phi_{g,w}$. The private key allows to recover $\Phi_{f,w}$ from $\Phi_{g,w}$.

Related papers

• Message Recovery Attack in NTRU via Knapsack [0.0]
  We introduce a message-recovery attack based on the Modular Knapsack Problem.<n>A FLATTER reduction successfully recovers the message, in practice when $epsilonapprox 0.45$.
  arXiv  Detail & Related papers  (2025-10-29T22:31:33Z)
• 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)
• A Generalized $χ_n$-Function [15.15494896344824]
  We introduce and analyze the generalized mapping $chi_n, m$ defined by $y=chi_n,m(x)$ with $y_i=x_i+x_i+m (x_i+m-1+1)(x_i+m-2+1) cdots (x_i+m-1+1)(x_i+m-1+1) cdots (x_i+m-1+1) cdots (x_i+m
  arXiv  Detail & Related papers  (2025-09-25T08:10:02Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  We introduce $mathsfPREM$ (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that a relative error guarantee for statistical queries under $(varepsilon, delta)$ differential privacy (DP) We complement our algorithm with nearly matching lower bounds.
  arXiv  Detail & Related papers  (2025-02-20T18:32:02Z)
• Optimal Computational Secret Sharing [51.599517747577266]
  In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants. We present a construction achieving a share size of $tfrac|S|t + |K|t$.
  arXiv  Detail & Related papers  (2025-02-04T23:37:16Z)
• 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)
• 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 Multiparty Commutative Hashing Protocol based on the Discrete Logarithm Problem [0.0]
  We will propose a protocol that enables the calculation of a hash function $H:mathcalXnrightmathcalY$. In this paper, we will propose a protocol that enables the calculation of a hash function $H:mathcalXnrightmathcalY$.
  arXiv  Detail & Related papers  (2023-11-29T10:19:34Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• Realization of an arbitrary structure of perfect distinguishability of states in general probability theory [0.0]
  All subsets with a single element are of course in $mathcal A$, and since smaller collections are easier to distinguish, if $Hin mathcal A$ and $L subset H$ then $Lin mathcal A$; in other words, $mathcal A$ is a so-called $textitindependence system$ on the set of indices $[n]$.
  arXiv  Detail & Related papers  (2023-01-16T18:33:39Z)
• When Variable-Length Codes Meet the Field of Error Detection [0.0]
  In the spirit of citeJK97,N21, the error detection-correction capability of variable-length codes can be expressed in term of conditions over $tau_d,k$. We examine whether those conditions are decidable for a given regular code.
  arXiv  Detail & Related papers  (2022-08-31T08:14:28Z)
• 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)
• Fair Representation Clustering with Several Protected Classes [13.53362222844008]
  We study the problem of fair $k$-median where each cluster is required to have a fair representation of individuals from different groups. We present an $O(log k)$-approximation algorithm that runs in time $nO(ell)$.
  arXiv  Detail & Related papers  (2022-02-03T03:45:45Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• Improved Hardness of BDD and SVP Under Gap-(S)ETH [6.876125456469918]
  We show improved fine-grained hardness of two key lattice problems in the $ell_p$ norm.<n>The problems areBounded Distance Decoding to within an $alpha$ factor of the minimum distance and the (decisional) $gamma$-approximate Shortest Vector Problem.
  arXiv  Detail & Related papers  (2021-09-09T03:53:57Z)
• Gray Cycles of Maximum Length Related to k-Character Substitutions [0.0]
  Given a word binary relation $tau$ we define a $tau$-Gray cycle over a finite language $X$ to be a permutation $left(w_[i]right)_0le ile |X|-1$ of $X$. We compute the bound $lambda(n)$ for all cases of the alphabet cardinality and the argument $n$.
  arXiv  Detail & Related papers  (2021-08-31T07:49:15Z)
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
  We give an algorithm for this task that achieves an expected $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$. On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$ holds not only in expectation but always.
  arXiv  Detail & Related papers  (2020-12-16T17:58:45Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

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.