Questions tagged [cryptography]

Questions concerning the mathematics of secure communication. Relevant topics include elliptic curve cryptography, secure key exchanges, and public-key cryptography (eg. the RSA cryptosystem).

Filter by
Sorted by
Tagged with
1 vote
0 answers
56 views

Why do we get a connected 2-regular graph?

In reading "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES" by Rostovtsev and Stolbunov, they claim on page 8 that the set $U=\{E_i(\mathbb{F}_p)\}$ of elliptic curves with a specific prime $l$ ...
Shean's user avatar
  • 111
1 vote
0 answers
57 views

When is the number-theoretic transform of small vectors again small?

I am currently working on an idea in the context of lattice-based cryptography, but the problem that I am currently stuck on seems to have almost nothing to do with lattices anymore. In particular, my ...
Simon Pohmann's user avatar
5 votes
0 answers
96 views

Equidistribution of Hecke points and Steinitz classes

Let $K$ be a number field and $\mathcal{P}$ be a prime ideal of $K$. Let $k_{\mathcal{P}}$ be the residue field $\mathcal{O}_K/\mathcal{P}$. Consider the following construction used very often in ...
Breakfastisready's user avatar
1 vote
0 answers
86 views

Select random point on elliptic curve

If I have an elliptic curve $E$ over some finite field $F_p$ what is a step by step algorithm to pick a random point that lays on this curve? There is definitely a naive approach to brute force all ...
R Artur's user avatar
  • 11
4 votes
1 answer
237 views

Is there a category theoretic definition of a cryptographic commitment scheme?

I'm trying to come up with a composeable framework for cryptographic commitment schemes, where inclusion proofs can be combined in different ways. I'm thinking this can be done with category theory, ...
eryb's user avatar
  • 153
2 votes
0 answers
92 views

Pollard's rho algorithm for ECDLP using supersingular elliptic curves over a field with characteristic equal to a Mersenne prime

I have been playing with Pollard's rho algorithm for elliptic curves over finite fields. I have noticed after some experimenting, that the algorithm almost always 'fails' for supersingular elliptic ...
Anton Odina's user avatar
4 votes
0 answers
166 views

Square hidden number problem

Suppose I have a mystery number $m$ modulo $p$ that I wish to find. I know the value of $m+x_i^2$ where $x_i$ is randomly chosen modulo $p$ for some large number of different $x_i$, $N$ many, $N \gg \...
mtheorylord's user avatar
0 votes
0 answers
84 views

On MSB and LSB of Diffie Hellman

Given generator $g$ of multiplicative cyclic group modulo $p$ a prime and two elements $h_1$ and $h_2$ such that there are $x_1$ and $x_2$ respectively satisfying $g^{x_i}=h_i\bmod p$ at every $i\in\{...
Turbo's user avatar
  • 13.6k
2 votes
0 answers
154 views

Will Coppersmith's method work for this bivariate modular polynomial shape?

I have a bivariate modular polynomial of shape $$f(x,y)=x^2y-g(x)\equiv 0\bmod q$$ where $q=(2p-1)(2p+1)$ is a product of two primes $2p-1$ and $2p+1$, $g(x)\in\mathbb Z[x]$ is of degree four and $f(...
Turbo's user avatar
  • 13.6k
4 votes
0 answers
120 views

Road map for learning about the computational/general theory of modular curves/isogenies of abelian varieties for cryptography

I am a graduate math/crypto student. So I've had some free time last year and I heard about elliptic curves in cryptography and how a resilient cryptosystem got demolished by a spectacular attack ...
Rayane B.'s user avatar
1 vote
0 answers
99 views

Question on definition of inverse number theoretic transformation

In the paper Porkodi and Arumuganathan - Public key cryptosystem based on number theoretic transforms I found the following statement on the second page regarding the Inverse Number Theoretic ...
TreeBook1's user avatar
2 votes
0 answers
49 views

Counting permutations of $X^2$ that induce 4 quasigroup operations up to isotopy

Let $X$ be a finite set. Recall that a binary operation $\ast$ on $X$ is said to be a quasigroup operation if there are binary operations $/,\backslash$ where $(x/y)\ast y=(x\ast y)/y=x$ and $x\ast(x\...
Joseph Van Name's user avatar
2 votes
0 answers
33 views

Criterion for unicity and existence of pre-image in multivariate cryptography

Repost from math.stackexchange since no one could help me there and it concerns my research. I am reading Ding's Multivariate Public Key Cryptosystems and in the book the author explains the so-called ...
Saegusa's user avatar
  • 173
3 votes
0 answers
61 views

Efficiently finding solutions to the Rainbow cryptosystem using quotient spaces

Repost of a mathematics stackexchange question here as this concerns my research and it went unanswered on there. In this paper, Ward Beullens gives another way to look at the Rainbow cryptosystem. In ...
Saegusa's user avatar
  • 173
1 vote
0 answers
97 views

Hardness of solving $0=\sum_{i=1}^k \operatorname{linear}_i(x_1,\ldots,x_n)^D$ over the rationals

This is related to cryptography and this question and another question. In short, we are asking about decomposing multivariate polynomial as sum of perfect powers of linear polynomials. Working over $\...
joro's user avatar
  • 24.2k
2 votes
0 answers
86 views

Complexity of finding solutions of trapdoored polynomial?

Related to this question Cryptography signature scheme based on hardness of finding points on varieties. Working over $K=\mathbb{Q}[x_1,...,x_n,y_1,...y_m]$. By abuse of notation, for polynomial $f$, ...
joro's user avatar
  • 24.2k
2 votes
0 answers
94 views

Cryptography signature scheme based on hardness of finding points on varieties?

Related to this question Complexity of finding solutions of trapdoored polynomial. I am trying to build signature scheme based on hardness of finding points on varieties. Let $K$ be field and $M=K[x_1,...
joro's user avatar
  • 24.2k
1 vote
0 answers
53 views

Over a given finite field, how many couples of matrices there are, for which their minimal polynomials are co-prime?

Let ${\mathbb F}_{q}$ be a given finite field. How many couples of $n\times n$ matrices $\left(A,B\right)$ over ${\mathbb F}_{q}$, such that $\gcd\left(\mu_{A}\left(\lambda\right),\mu_{B}\left(\lambda\...
Yossi Peretz's user avatar
1 vote
2 answers
186 views

Distribution of "good" and "bad" basis in lattice families?

I'm trying to learn more about lattice based cryptosystems. One of the fundamental ideas behind lattice based cryptosystems is that there can be many equivalent basis for a single lattice. Formally, ...
weissguy's user avatar
1 vote
1 answer
111 views

Deduce kernel of isogeny from action on torsion points

I'm stuck with the following problem: In Petit's work "Faster Algorithms for Isogeny Problems using Torsion Point Images", p. 8, he says that we can deduce $\ker \psi_{N_2}$ knowing the ...
Manuel Bravi's user avatar
3 votes
1 answer
242 views

What is meant by a meet-in-the-middle approach?

I'm studing C. Petit's work "Faster algorithms for isogeny problems using torsion point images" (link) and he talks about meet-in-the-middle approach/strategy for solve some isogenies ...
Manuel Bravi's user avatar
8 votes
2 answers
396 views

Knot Diffie–Hellman

Here's an idea for a knot-based Diffie–Hellman exchange: Public: random (oriented) knot $P$. Private: random (oriented) knots $A$ and $B$. Exchange: Alice sends (randomized or canonical ...
yoyo's user avatar
  • 487
1 vote
0 answers
75 views

Why is the kernel cyclic if and only if the walk does not backtrack?

I'm reading Mathematics of Isogeny Based Cryptography by Luca De Feo. At some point (pg. 32), he says "A walk of length $e_A$ in the $l_A$-isogeny graph corresponds to a kernel of size $l_A^{e_A};...
Manuel Bravi's user avatar
2 votes
0 answers
121 views

On choosing the correct square root of $g^{4n}$ modulo primes

Let $p$ be prime congruent to $3$ modulo $4$. The discrete logarithm problem asks: given $g,a,p$ such that $g^x \equiv a \pmod{p}$, find $x$. Assume $g$ is of maximal multiplicative order. In an ...
joro's user avatar
  • 24.2k
2 votes
0 answers
111 views

Solving efficiently a quadratic equation in a large finite field of characteristic two

I'm trying to solve efficiently a quadratic equation in the finite field $\text{GF}(2^{128})$ represented as $(\mathbb{Z}/2\mathbb{Z})[x] / (x^{128} + x^7 + x^2 + x + 1)$. Until now, I came across ...
ocalex86's user avatar
1 vote
0 answers
131 views

The security of one-time digital signatures from a solution to a diophantine equations

I wonder how well arbitrary Diophantine equations can be used to make one time digital signature schemes. For our one-time digital signature scheme, the public key is a collection of polynomials $f_1(...
Joseph Van Name's user avatar
1 vote
2 answers
250 views

Method to solve system of exponential sums of the form $a^x+b^x=c$ given more equations than variables [closed]

Cross post with mse For example, let's say I have the following equations. \begin{gather*} a^{x-1}+b^{x-1}=337 \\ a^{x}+b^{x}=1267 \\ a^{x+1}+b^{x+1}=4825 \\ a^{x+2}+b^{x+2}=18751. \end{gather*} What ...
WARA's user avatar
  • 13
2 votes
1 answer
89 views

Proving that a function is a trapdoor function

I am working on a problem that involves an iterative application of a function I think might be a trapdoor function. Formally, I have a function $f:X \to X$ that can be described as $$ [x_{1,N+1}, ...,...
Andrei Kucharavy's user avatar
2 votes
0 answers
41 views

Linkable Ring Signatures test

I did a work that uses LRS to sign documents. LRS is a ring signatures model in which the feature of linking signatures made by the same signer is added. Using LRS two messages m1 and m2 are signed ...
Cesar11031's user avatar
4 votes
0 answers
120 views

Lattice reduction of basis with non-integer coefficients

Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$. I would like to perform lattice ...
george's user avatar
  • 554
1 vote
0 answers
94 views

Reference request: Time and proofs of shared pasts

Is there research about structures for notions of time with distributed systems of information, as with blockchains? I am thinking of tuples $(I, T, P, A, \prec, s, \eta, u)$ where $I$, $T$ and $P$ ...
Gerrit Begher's user avatar
1 vote
0 answers
67 views

What is the complexity of elgamal cryptosystem? [closed]

Its clear generation of keys based On cyclic group and its generator for z_p So my question Does finding the generator efect on complexity Moreove does the size of message M effect on the complexity?
Me_u090's user avatar
  • 11
1 vote
0 answers
41 views

If statement in the algebraic group model (AGM)

In the algebraic group model (https://eprint.iacr.org/2017/620.pdf), can one use "if" statement? For example, can one do the following in AGM? input: x, y, z if (x = y) then z = x else z = ...
jsliyuan's user avatar
  • 651
3 votes
0 answers
128 views

determine degree of boolean polynomial given as black box

I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
Math-fort's user avatar
  • 103
2 votes
1 answer
166 views

On roots of irreducible quadratics modulo composites

Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$ Is this problem equivalent to any hardness results?
Turbo's user avatar
  • 13.6k
4 votes
1 answer
262 views

Discrete logarithms and primitive elements in finite fields

The recent papers: R. Granger, T. Kleinjung, J. Zumbragel, "On the Discrete Logarithm Problem in Finite Fields of Fixed Characteristic," Trans. Amer. Math. Soc., 370(5) (2018), 3129–3145. T....
aleph's user avatar
  • 503
-1 votes
1 answer
181 views

Public key cryptography based on non-invertible matrices, part II

Closely related to this question and extending comment of R. van Dobben de Bruyn. Working over $\mathbb{F}_p$ and all matrices of square $n \times n$. Alice chooses invertible $X_A$ and non-...
joro's user avatar
  • 24.2k
5 votes
1 answer
551 views

Public key cryptography based on non-invertible matrices?

Added Wed 13 Apr 2022 I have written a short note with experimental data, which shows not all pseudo keys are good keys. Public key cryptography based on non-invertible matrices We got public key ...
joro's user avatar
  • 24.2k
0 votes
1 answer
115 views

Are there trapdoor functions breakable by moderate polynomial degree complexity algorithm?

Trapdoor function is a function $f$ that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) $f^{-1}$ without special information, called the &...
joro's user avatar
  • 24.2k
6 votes
1 answer
357 views

Groups in which Computational Diffie Hellman is in $P$ but Discrete Logarithm is not known to be in $P$

The Computational Diffie Hellman (CDH) problem is to compute $g^{XY}$ given $g^X$ and $g^Y$ where $g$ generates the group. The Discrete Logarithm (DLOG) problem is to compute $X$ given $g^X$. The ...
Turbo's user avatar
  • 13.6k
0 votes
1 answer
490 views

A good approximation for collision probability between (two) sets of random variables

We face many places to find the collision probability of two sets (or more) in my case the cryptographic hash functions. We can formalize as; Given two sets of random variables $\mathbf{A}$ and $\...
kelalaka's user avatar
  • 115
5 votes
2 answers
493 views

Diffie Hellman cryptography based on graph isomorphism?

We got a cryptographic algorithm and computer implementation based on graph isomorphism. An isomorphism between two graphs is a bijection between their vertices that pre serves the edges. For a graph $...
joro's user avatar
  • 24.2k
2 votes
2 answers
624 views

Difference between Shannon entropy and min-entropy

I would like to construct a sequence of discrete random variable $X_2, X_3,...,X_n,...$, where $X_n \in\{0,1,2,...,n-1\}$. Given any $\epsilon \in (0,1)$, its Shannon entropy and min-entropy should ...
Luis's user avatar
  • 23
7 votes
0 answers
457 views

Zero-knowledge proofs for answers to the $P=NP$ question

Are there zero-knowledge proofs for every answer to the $P=NP$ question? For instance, if you have a polynomial-time algorithm of moderate complexity for the graph-coloring problem, then it is easy to ...
Manfred Weis's user avatar
  • 12.6k
1 vote
1 answer
87 views

Can a polynomial be evaluated from evaluations of partial interpolations? (Or: can the unique solution of congruences be written in a certain way?)

Formally, let $K$ be a field, $a \in K[x]$, $D \subseteq K$, and $E = \{(x_i, a(x_i)) \mid x_i \in D\}$ be distinct evaluations of $a$ where $\lvert E\rvert > \operatorname{deg}(a)$ (so $E$ ...
Joe Bebel's user avatar
  • 539
3 votes
1 answer
258 views

p-adic logarithms with fixed precision

Probably this is easy, but we would like to see it on paper. Let $p$ be prime and $D,g,n$ positive integers. Let $A=g^n \bmod p^D$. Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$. In ...
joro's user avatar
  • 24.2k
5 votes
1 answer
336 views

Discrete logarithm and the sequence $a(n)=(g^n \bmod p)^{p-1} \bmod p^2$

Let $p$ be prime and $g,n$ integers. Define $a(n)=(g^n \bmod p)^{p-1} \bmod p^2$ By mod p we don't mean congruence, but the reduction modulo $p$ operator. $A \bmod ...
joro's user avatar
  • 24.2k
1 vote
0 answers
79 views

Encryption based on boolean satisfiability?

We got sketch of algorithm for public key encryption based on satisfiability of hidden boolean formula. It is easy to break in its current form, but we are interested if it can be improved. Alice ...
joro's user avatar
  • 24.2k
2 votes
1 answer
230 views

Are there any homomorphic analog error correction code?

Are there any analog error correction codes that are additively and multiplicatively homomorphic?
myshkin's user avatar
  • 41
5 votes
2 answers
401 views

Maximum number of vectors with upper bound on pairwise inner products

I have a collection $\{v_1,...,v_k\}$ of vectors in $\{\pm 1\}^n$ with the property that for all $i\neq j$ we have $\langle v_i, v_j \rangle \le c\log_2(n)$. I am looking for an upper bound on $k$ in ...
DPL's user avatar
  • 63