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

2
votes
3answers
283 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
281 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
371 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} ...
0
votes
3answers
707 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
203 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
234 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
553 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
479 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
586 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
306 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
207 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 ...
3
votes
0answers
410 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 ...
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 ...
11
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
700 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 ...
5
votes
3answers
666 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
172 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
496 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
629 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
461 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
644 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 ...
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
430 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 ...
4
votes
2answers
297 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 ...
30
votes
7answers
15k 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
2k 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
666 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
1k 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 ...
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 ...