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).
203 questions
2
votes
1
answer
204
views
Is there a security analysis of the GQ digital signature scheme?
I'm doing summer cryptography research and I am have been looking for a security analysis of the Guillou-Quisquater (GQ) digital signature scheme, but I have been unable to find one.
Since this is not ...
CommunityBot
- 1
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 ...
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 ...
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 ...
- 30.5k
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" ...
- 20.4k
1
vote
1
answer
204
views
Functional Encryption for Inner Product Predicates
I want to try to implement a functional encryption scheme proposed in http://eprint.iacr.org/2011/410. The first problem I faced with is a TrapGen algorithm. In the paper theorem 3.1 states that:
...
- 113
4
votes
0
answers
264
views
Polynomial dynamical systems
The question is somewhat related to the theory of permutation polynomials. Let $\mathbb{F}_p$ be a finite field of $p$ elements ($p$ is prime) and $\mathcal{V} = \mathbb{F}_p^2 = \{ (t_1,t_2)\::\: t_1,...
- 411
1
vote
1
answer
205
views
Connection between inf-entropy rate and min-entropy
I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...
- 752
2
votes
1
answer
801
views
Canonical lifts from $\mathbb F_q$ and CM-theory
One knows that (ordinary) Jacobians of hyperelliptic curves over a finite field $\mathbb F_q$ (mostly of genus 1 (elliptic curves) and 2) are extensively studied by cryptographers, as a platform for ...
- 1,254
2
votes
0
answers
132
views
Genus 2 hyperelliptic cryptography : typical discriminant and class number
As far as I know, there is no standard yet for cryptography based on the DLP over Jacobians of genus 2 curves. Yet, what can we say about the class number, and the discriminant of the complex ...
- 647
0
votes
0
answers
81
views
Encrypting the same message using different schemes
$E_1$ and $E_2$ are IND-CPA secure encryption schemes.
$E$ is defined as:
$k_1,k_2 \leftarrow K_1 \times K_2$ .
$E_{k_1,k_2}(m) \leftarrow E_{1,k_1}(m)||E_{2,k_2}(m)$.
Hope the notations are in an ...
- 1
2
votes
2
answers
1k
views
Anomalous elliptic curves over finite rings
I was wondering if it is possible to solve the discrete logarithm on an Elliptic Curve E(Z/nZ) (defined over the ring of integers modulo a composite n) with #E(Z/nZ)=n by applying a method analogous ...
- 25.4k
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
2
votes
0
answers
63
views
Private Randomness extractor
Suppose we are given two random variables $X$ and $Y$ with fixed marginal and joint distribution. What is the maximum randomness that we can extract from $Y$ that is independent from $X$, that is, if $...
- 1,109
5
votes
2
answers
3k
views
Whitening a random bit sequence
Given an (infinite) stream of uncorrelated random bit with a known "reasonable" bias (say 15-85% 1's) I want to whiten it, e.i. produce a shorter stream of bits that has no bias. The restriction is ...
- 846
0
votes
1
answer
748
views
Pairing on elliptic curve
Let $E(\mathbb{F_q})$ - elliptic curve.
$G_1 = E(\mathbb{F_q})[r]$. $|G_1| = r$.
$k$ is minimal such $r | q^k - 1$.
$\pi_q$ - $q$-power Frobenius endomorphism.
$G_2 = E(\mathbb{F_{q^k}})[r] \cap ...
CommunityBot
- 1
8
votes
3
answers
710
views
Predicting if something is a code
I'm trying to help a non-mathematical friend by posting a question of his here. He studies literature and has come across a book which is written in a made-up language. The book is hundreds of pages,...
CommunityBot
- 1
3
votes
0
answers
257
views
Oracle separating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on DDH)
Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP?
Such an oracle ...
CommunityBot
- 1
8
votes
4
answers
3k
views
Is there a two-party multiplicative and additive secret sharing scheme ?
A secret sharing scheme such as Shamir's secret sharing allow to perform addition and multiplication for secret values so far as there is at least 3 participants. Addition of two secret values is done ...
- 121
12
votes
1
answer
577
views
Are there very strongly pseudorandom permutations?
A pseudorandom permutation can be defined formally as a function $\phi$ from $\{0,1\}^k\times\{0,1\}^n$ to $\{0,1\}^n$ such that for every $x\in\{0,1\}^k$ the function $\phi_x:y\mapsto\phi(x,y)$ is a ...
- 311
1
vote
0
answers
115
views
Collision resistance of hash functions after permuting one hash digest
Given a hash function H and a fixed permutation pi of the digest set. Consider "collisions" of the form H(x) = pi(H(x')). How is resistance against this kind of ...
- 11
14
votes
3
answers
3k
views
Will quantum computing kill cryptography ? [closed]
I apologize as this question is not really mathematical, and therefore perhaps not
well-suited for this site. Please feel free to close it if you think it is not. My reason
for asking it here is that ...
- 71
0
votes
2
answers
524
views
cryptographic primitive process
Is there a cryptographic primitive process/method for creating cryptographic tools like symmetric encryption/decryption, Hash code generator, MAC generator and Random number generator?
...
CommunityBot
- 1
9
votes
4
answers
1k
views
The "interplay" between additive and multiplicative structure in a field
A field is an ordered triple $(F, +,\cdot)$ of a set $F$ and binary operations $+,\times$ on $F$ such that $(F,+)$ and $(F\backslash 0,\times)$ are abelian groups satisfying the distributive laws
$\...
CommunityBot
- 1
0
votes
0
answers
267
views
Is Guillou-Quisquater existentially unforgeable against adaptive message attack under a random oracle model?
First of all, the Guillou-Quisquater digital signature scheme is:
Note everything is $\bmod n$. Message is denoted by $m$.
Private key: $s$
Public key: Hash function $H$, $e$, $L=s^e\bmod n$
To sign: ...
CommunityBot
- 1
10
votes
1
answer
2k
views
Attack on CRT-RSA
The survey paper of Prof. Dan Boneh entitled
"Twenty years of attacks on the RSA cryptosystem" mentioned that (Page 5)
one can attack CRT-RSA in square root of decryption exponent. However no
...
- 16.8k
0
votes
0
answers
143
views
Knowing md5(c+x), is it possible to find md5(x)?
Suppose:
md5(c1 + x) = c2
md5(x) = y
Is it possible to find y, if c1 and c2 are known and x is uknown? Basically, I know md5(salt + key) and I want to find md5(key).
1
vote
0
answers
343
views
Diophantine approximation
Say absolute values of $a,b,c$ is $O(log^{k}{n})$ for some positive constant $k$.
Given positive integer $n$ that is reasonably large, we cannot always find integers $a,b,c$ such that $|a{b^{c}} - n|$ ...
- 188k
0
votes
0
answers
316
views
Cryptography and Availability
Hi,
Here is a question in cryptography which is probably naive, and a reference request.
Suppose I have 3 matrices(I1, I2, and I3 -same size) that I want to combine them some how(? do not know yet) ...
- 1
6
votes
1
answer
453
views
Computing the correlation between two vectors without divulging them
Alice and Bob respectively know a vector of $N$ real numbers $u$ and $v$. They would both like to know $\rho = \langle u,v \rangle/N$ but Alice does not want Bob to gain anymore information about $u$ ...
- 1,902
8
votes
0
answers
1k
views
Question on randomness extractors
Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.
The adversary doesn't ...
- 5,502
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$ ...
- 1
3
votes
3
answers
337
views
Cryptography and iterations
Hi,
Here is a question in cryptography which is probably naive, and a reference request.
I was wondering about the following key-exchange scheme, which is a variant on Diffie-Hellman. Consider a ...
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 ...
- 96.4k
5
votes
3
answers
950
views
Torus based cryptography
In cryptography one needs finite groups $G$ in which the discrete logarithm problem is infeasible. Often they use the multiplicative group $\mathbb{G}_m(\mathbb{F}_p)$ where $p$ is a prime number of ...
- 347
0
votes
0
answers
191
views
Asymtotic Complexity Analysis using logarithms and binomial coefficients
On page 11 of "Smaller decoding exponents: ball-collision decoding" by Berstein et.al. they have the formula \begin{equation}\lim_{n \rightarrow \infty} \frac{1}{n}\log_{2}\left(\dbinom{k_{1}}{p_{1}}\...
- 101
1
vote
3
answers
1k
views
Weil pairing, Kummer theory, help to decrypt what Wikipedia says
I do not quite understand the sentence in the Wikipedia article:
http://en.wikipedia.org/wiki/Weil_pairing
Section "Formulation" line 3:
"... for given points $P,Q \in E(K)[n]$, where $E(K)[n]=\{T \...
- 47.4k
4
votes
0
answers
214
views
factorising an integer with certain bound on the factors
Can we count the no. of $x$ where $ p^{\alpha -1} < x < p^{\alpha}$ , $gcd(x, 2p)=1$ and if $d |x$ and $d < p ^{\beta}$ for some $1< \beta<\alpha-1$ then $ \frac {x} {d} > p^{\alpha -...
- 39.9k
10
votes
3
answers
3k
views
Reduction from factoring to solving Pell equation
The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims
There are reductions from factoring to solving Pell’s equation, and from solving Pell’s
...
1
vote
1
answer
288
views
Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without "being able to know" one of the discrete logs involved (formal definition given in question)?
Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, ...
CommunityBot
- 1
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
0
answers
688
views
Elliptic Curves and cryptography. Recommended Reading [closed]
I have been studying RSA cryptography and want to extend this to ECC. I am interested in any books on the topic, that start off with basic principles of elliptic curves as I have almost zero knowledge ...
CommunityBot
- 1
3
votes
0
answers
458
views
Does this algorithm exist - a secret secret?
I'm not quite sure how to phrase this question mathematically, so I am going to express it in words first:
Let us suppose I have a secret $m_1$ and a plausible innocent secret $m_2$. Is there an ...
3
votes
2
answers
3k
views
Weil pairing and Miller's algorithm
I'm studying Weil pairing and its applications in cryptography. I already know that it can be defined like this:
$$w(P, Q) = (-1)^n\frac{f_P(Q)}{f_Q(P)}\frac{f_Q}{f_P}(\mathcal{O})$$
where
$\textrm{...
- 131
12
votes
5
answers
2k
views
Introducing Cryptology to Undergraduates
This summer I am going to give some lectures to some REU students. I am still tossing around ideas for what I am going to talk about, but one thing I would at least like to give one or two lectures on,...
- 3,867
0
votes
1
answer
1k
views
Elliptic curve over finite field: scalar multiplication
I'm implementing arithmetics for elliptic curves over secp256r1 as a homework assignment.
For scalar multiplication, the assignment specifically specifies that $k$ is "any hexidecimal encoded integer"...
- 3
5
votes
1
answer
667
views
A silly question: is the number of points on a Jacobian (of a curve, over a finite field) known?
In a cryptography book I read that people does not known how to compute the number of points on a Jacobian of a hyperelliptic curve $C$ over a finite field $F_q$? Is this true? It seems easy to ...
- 66.3k
10
votes
1
answer
744
views
What can I say about the permutation $\alpha\beta$ if I know the permutation $\beta\alpha$?
I'm looking into a secret sharing scheme that has a secret permutation $\theta$ which has the cycle structure (n/2)+(n/2) (i.e. two (n/2)-cycles).
The permutation $\theta$ is decomposed into two ...
- 118k
26
votes
4
answers
6k
views
Discrete logs vs. factoring
One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction ...
0
votes
0
answers
562
views
Reducing two variable linear Diophantine equation to modular inversion
I'm in the field of secure multiparty computation using Homomrphic encryption or secret sharing. I want to implement a secure protocol to compute the GCD of two encrypted numbers.
To calculate the ...
- 193