# Tagged Questions

The cryptography tag has no wiki summary.

**2**

votes

**0**answers

129 views

+50

### PRNG and coding theory

Let $k, n \in \mathbb{N}$, $k = (1 - \epsilon)n$ where $1 >\epsilon > 0$.
I want to find $f: \{0,1\}^k \to \{0, 1\}^n$
such that:
1) $f(a) \not= f(b)$ if $a \not=b $
2) for any $x \in ...

**2**

votes

**1**answer

66 views

### Future-Proof Encrypt for Multiple Independent Parties

I have a secret message which I want to encrypt such that any of several different keys can open it independently. The keys can't know about each other and it has to be able to work completely ...

**12**

votes

**2**answers

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

**1**

vote

**0**answers

56 views

### Showing that a crypto hash function is not permutation, possibly conditionally?

Let $f$ be some crypto hash function, say MD5 with output $n$ bits. Restrict the input to $n$ bits.
Cryptographer told me it is open problem if such restricted collision
exists, i.e. $f(x)=f(y),x \ne ...

**9**

votes

**2**answers

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

**1**

vote

**1**answer

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

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

**14**

votes

**5**answers

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

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

**2**

votes

**1**answer

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

**5**

votes

**1**answer

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

**0**

votes

**1**answer

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

**4**

votes

**0**answers

224 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)\::\: ...

**1**

vote

**1**answer

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

**2**

votes

**1**answer

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

**2**

votes

**0**answers

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

**0**

votes

**0**answers

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

vote

**2**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**5**

votes

**0**answers

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

**3**

votes

**2**answers

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

**0**

votes

**1**answer

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

**8**

votes

**2**answers

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

**9**

votes

**3**answers

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

**2**

votes

**0**answers

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

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

**11**

votes

**1**answer

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

**0**

votes

**0**answers

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

**27**

votes

**7**answers

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

**1**

vote

**0**answers

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

**12**

votes

**3**answers

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

**0**

votes

**2**answers

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

**7**

votes

**4**answers

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

**0**

votes

**0**answers

231 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$, ...

**9**

votes

**1**answer

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

**0**

votes

**0**answers

119 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

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

**0**

votes

**0**answers

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

**5**

votes

**1**answer

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

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

**2**

votes

**3**answers

279 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

**3**answers

278 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

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

**5**

votes

**3**answers

619 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

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

**3**answers

647 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

**0**answers

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

**5**

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

**1**

vote

**1**answer

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