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

learn more… | top users | synonyms

0
votes
2answers
410 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? ...
0
votes
0answers
127 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
0answers
239 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) ...
13
votes
2answers
1k 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 ...
2
votes
1answer
129 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 ...
5
votes
1answer
358 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$ ...
2
votes
3answers
284 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 $...
3
votes
3answers
282 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
1answer
380 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 ...
0
votes
0answers
179 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}}\...
0
votes
3answers
722 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 \...
4
votes
0answers
204 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 -...
1
vote
1answer
235 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, ...
7
votes
1answer
559 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 ...
2
votes
1answer
482 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.)$ "...
2
votes
0answers
594 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 ...
1
vote
0answers
313 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|$ ...
6
votes
3answers
2k 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 ...
2
votes
0answers
219 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 ...
3
votes
0answers
419 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 ...
2
votes
2answers
1k 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{...
8
votes
0answers
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 ...
12
votes
2answers
4k 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 ...
0
votes
1answer
706 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"...
5
votes
3answers
683 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 ...
0
votes
0answers
174 views

AES key schedule: round 1 and round 0 equal?

is there a key that gives round 1 and round 0 that are equal? (a0,b0,c0,d0) = (a1,b1,c1,d1) how many keys like that exist? can it continue to round 2? round3...?
4
votes
1answer
515 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 ...
9
votes
1answer
634 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 ...
14
votes
4answers
2k 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
0answers
472 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 ...
8
votes
4answers
1k 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 ...
10
votes
3answers
648 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,...
4
votes
2answers
2k 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 ...
1
vote
1answer
438 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
votes
2answers
299 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 ...
11
votes
5answers
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,...
33
votes
7answers
18k 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 ...
4
votes
5answers
3k 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 ...
0
votes
1answer
684 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 ...
2
votes
4answers
2k views

Recovering $\Phi(n)$ from a multiple?

I've been attending a series of lectures on Cryptography from an engineering perspective, which means that most of the assertions made are supplied without proof... here's one that the lecturer couldn'...
19
votes
4answers
2k 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 ...