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

**5**

votes

**0**answers

341 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

242 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)\::\: t_1,...

**4**

votes

**0**answers

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

**3**

votes

**0**answers

46 views

### Do the normal forms for braid groups really conceal information about better than randomly applying the braid relations?

In braid based cryptography, one typically wants to conceal the way a certain braid $b$ has been obtained. One therefore puts $b$ into some normal form. Since every braid has a unique normal form, the ...

**3**

votes

**0**answers

174 views

### 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 \{0,1\}...

**3**

votes

**0**answers

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

**0**answers

107 views

### Inverting a function

I posted this question on crypto.SE but got no answer:
Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$
Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-i} } $ be the ...

**2**

votes

**0**answers

104 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

36 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

56 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

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**0**

votes

**0**answers

68 views

### Algebraic operations with memory hardness properties

In cryptography, there are password hash functions like scrypt and argon2 for which the fastest known algorithms employ large ...

**0**

votes

**0**answers

43 views

### lower bound for solve ECDLP

Let $P$ and $Q$ are two points of NIST elliptic curve $E$ (defined over $F_{2^m}$ with prime $m$) and $k$ is a private key such that $k.P=Q$. Suppose $\ell$ be the number of bits in $k$, and let $k_i$ ...

**0**

votes

**0**answers

42 views

### How much p-adic logarithm with precision 2 speeds discrete logarithm modulo $p^2$?

Let $p$ be large prime and $g$ generator of the multiplicative
group modulo $p^2$.
The discrete logarithm (DL) modulo $p^2$ asks : given $g,A,p$, find $x$
satisfying $g^x \equiv A \pmod{p^2}$.
...

**0**

votes

**0**answers

60 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

183 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

246 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$, $L=s^e\...

**0**

votes

**0**answers

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

**0**answers

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

**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} \frac{1}{n}\log_{2}\left(\dbinom{k_{1}}{p_{1}}\...

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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