The cryptography tag has no usage guidance.

**7**

votes

**1**answer

551 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

**1**answer

475 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

**0**answers

580 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 ...

**0**

votes

**0**answers

305 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

**3**answers

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

**0**answers

203 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

**0**answers

409 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

**2**answers

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

**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 ...

**10**

votes

**2**answers

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

**1**answer

682 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

**3**answers

641 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

**0**answers

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

**1**answer

487 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

**1**answer

622 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

**4**answers

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

**0**answers

456 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

**4**answers

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

**3**answers

643 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

**2**answers

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

**1**answer

428 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

**2**answers

296 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

**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 ...

**30**

votes

**7**answers

14k 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 ...

**2**

votes

**5**answers

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

**1**answer

659 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

**4**answers

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

**4**answers

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 ...