All Questions
Tagged with cryptography algorithms
24 questions
1
vote
2
answers
278
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 ...
- 13
2
votes
0
answers
132
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 ...
- 21
5
votes
2
answers
534
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 $...
- 25.4k
4
votes
0
answers
137
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 ...
- 554
6
votes
1
answer
417
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 ...
- 13.9k
3
votes
0
answers
151
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 ...
- 103
1
vote
0
answers
83
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?
- 11
3
votes
1
answer
708
views
Is strictly harder than NP-hard cryptography possible?
Looks like there is cryptography based on NP-hard problem, e.g. McEliece cryptosystem. The algorithm is an asymmetric encryption algorithm and is based on the hardness of decoding a general linear ...
- 25.4k
23
votes
5
answers
1k
views
Securing privacy of "who communicates with whom" under Orwell-like conditions
Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...
- 19.6k
17
votes
5
answers
981
views
Mathematics of privacy?
I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...
- 10.8k
4
votes
0
answers
245
views
Can we make cryptography signature algorithm based on hardness of isomorphism?
In public key cryptography, Alice knows functions $f$ and its inverse
$f^{-1}$. $f$ is public and $f^{-1}$ is secret. To sign a message
$m$, she gives $(m,a=f^{-1}(m))$. To verify a signature, the ...
- 25.4k
10
votes
1
answer
1k
views
Cryptographic Secret Santa
Is there a protocol for conducting a Secret Santa without a central authority? Precisely, we want to sample uniformly a permutation that has no one-cycles and reveal to each member his or her ...
- 101
3
votes
1
answer
138
views
Given $n, c$ find $a>1,b$ such that $b ^ a \equiv c \pmod n$
Given a natural number $n$ (of unknown factorization) and an arbitrary number $c \in \mathbb{Z}^*_n$ (the set of natural numbers smaller than $n$ and coprime to it), is there an efficient algorithm ...
- 271
8
votes
1
answer
579
views
Inverting a function
I posted this question on crypto.SE but got no answer:
Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$
Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-i} } $ be the ...
user6671
9
votes
1
answer
756
views
Any nice examples of small cancellation theory appearing in applied mathematics?
Are there any nice discussions of applications of small cancellation theory, or other cases of the word problem, in applied mathematics or algorithms for seemingly non-group theoretic problems?
I ...
- 565
7
votes
1
answer
1k
views
Modular polynomials for elliptic curves point counting
The Schoof-Elkies-Atkin (SEA) algorithm (for counting points on elliptic curves over a finite field) performs computations over polynomials modulo some modular polynomials. Originally the "classical" ...
- 647
2
votes
1
answer
127
views
Future-Proof Encrypt for Multiple Independent Parties
I have a secret message which I want to encrypt such that any of several different keys can open it independently. The keys can't know about each other and it has to be able to work completely ...
- 123
3
votes
1
answer
164
views
Mestre-type algorithm for higher-genus curves?
Is there an analogous algorithm for genus $g>2$ curves that, given a complete set of invariants, outputs a curve with those invariants?
(I'm interested in particular in $g=3$.)
Any references ...
- 61
2
votes
1
answer
162
views
DL-problem on abelian variety
Let $A$ be an abelian variety over $\mathbb{F_q}$ with dimension $n$. Let $q$ be a constant.
Is there polynomial algorithm of finding discrete logarithm in $A$?
UPD: really I don't undestend: can we ...
- 2,576
5
votes
1
answer
423
views
Fastest algorithm to compute (a^(2^N))%m?
Hi.
There are well-known algorithms for cryptography to compute modular exponentiation $a^b\%c$ (like Right-to-left binary method here : http://en.wikipedia.org/wiki/Modular_exponentiation).
But do ...
- 151
2
votes
1
answer
711
views
Factoring and Index Calculus and duality between DL and factoring via compuational problems made easy through them
If factoring is in $P$ (with a blazing fast polynomial time in $P$), would it affect the index calculus algorithm used for Discrete Log calculation in any serious way?
Other connections
$1.)$ "...
- 800
2
votes
3
answers
398
views
Generating a set of integer passwords that can be securely authenticated
First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.
My question is as follows.
Given a positive integer $k$, determine a set of properties $S$ ...
- 135
0
votes
1
answer
997
views
The Discrete Logarithm problem [closed]
I am puzzled with the following discrete logarithm problem:
Given positive integers b, c, m where (b < m) is True it is to ...
- 555
2
votes
0
answers
44
views
largest size for a randomness extractor
I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature.
Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...
- 1,109