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
8
votes
1
answer
723
views
Is this obfuscation scheme unbreakable?
I've just come across this popular article about a breakthrough (which can be purchased here), published in Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium by a team of ...
- 18.7k
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
0
votes
0
answers
262
views
Lattice basis reductions and finding minimal values
While reading several articles about lattice basis reduction I am left with a few questions.
For one, I came across this piece of text
Let $\alpha$ and $\beta \in \mathbb{R}$. Also let $X>0$ and $...
- 1
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 ...
- 29k
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 ...
- 26.1k
17
votes
3
answers
23k
views
Which hard mathematical problems do you have to solve to earn bitcoins ?
A virtual currency called bitcoins has been in the news recently. It is said that in order to "mine" bitcoins, you have to solve hard mathematical problems.
Now, there are two kinds of mathematical ...
- 18.7k
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 ...
- 9
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
$\...
- 2,075
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: ...
- 1,441
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
...
- 125
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?
...
- 1
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).
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
20
votes
2
answers
2k
views
Bitcoin Research
I have recently been assigned to advise a student on a senior thesis. She has taken linear algebra, introductory real analysis, and abstract algebra. Her interest is in cryptography. And she has a ...
- 822
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 ...
- 1,441
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
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
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 ...
- 2,287
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
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 \...
- 24.9k
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 -...
- 897
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, ...
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
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 ...
- 133
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|$ ...
- 800
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
...
- 25.4k
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 ...
- 5,502
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
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 ...
- 81
13
votes
2
answers
9k
views
Encrypting a message for multiple recipients
Let $m$ be a secret message that needs to be sent to $n >1$ recipients. Let each recipient $r_i$ have a public key $p_i$ and private key $s_i$. Is there a scheme such that we can encrypt the ...
- 179
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
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 ...
- 1,673
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 ...
- 16.9k
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 ...
- 4,229
16
votes
4
answers
3k
views
Zero-knowledge proof of positivity
If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?
My bounty is ending ...
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
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 ...
- 193
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,...
- 265
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 ...
- 205
1
vote
1
answer
737
views
Matrix Conjugates over Finite Fields
Thinking about Diffe-Hillman for matrices brought me to the following question.
Given $\mathbb{F}_{p^k}$ the finite field with $p^k$ elements when can we find non-trivial solutions to
$\begin{...
- 4,842
4
votes
2
answers
331
views
Good quality data/packages for statistical/structure analysis of words in the English language
From time to time I find myself wishing to calculate basic statistics on words in the English language. For example, today I found myself wanting a graph of the number of English words vs. their ...
- 2,123
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,...
- 4,842
68
votes
8
answers
43k
views
Example of a good Zero Knowledge Proof
I am working on my zero knowledge proofs and I am looking for a good example of a real world proof of this type. An even better answer would be a Zero Knowledge Proof that shows the statement isn't ...
- 699
6
votes
5
answers
6k
views
Analog to the Chinese Remainder Theorem in groups other than Z_n.
The idea hit me when I was in my Elliptic Curve Cryptography class. $Z_n \leftrightarrow Z_{f_1} \times Z_{f_2} \times ...$ where $f_1 \times f_2 \times ... = n$ and $\{f_1, f_2, ...\}$ are pairwise ...
- 359
4
votes
3
answers
5k
views
modular exponentation for RSA, why is 2^16 + 1 commonly chosen?
I know that the number 216 + 1 is commonly used for RSA, since 0b 1 0000 0000 0000 0001 only contains two 1 bits. Many sites explain that this makes modular exponentiation faster, but I haven't come ...
- 59