The cryptography tag has no wiki summary.

**9**

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

**5**

votes

**0**answers

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

**4**

votes

**0**answers

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

**4**

votes

**0**answers

394 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

**0**answers

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

**2**

votes

**0**answers

23 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

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

**2**

votes

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

113 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

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

171 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

**0**answers

280 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

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

**0**

votes

**0**answers

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