**16**

votes

**1**answer

506 views

### Is hyperelliptic cryptography “practical”?

Previosly my impression on this subject was that hyperelliptic cryptography systems (as well as other possible cryptosystems based on abelian varieties of dimension $>1$) have no advantages over ...

**0**

votes

**1**answer

76 views

### isogeny based cryptography

Isogeny based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is theorem:
Elliptic curves ...

**-1**

votes

**0**answers

89 views

### Soft question: take complex analysis or cryptology? [migrated]

I am math major junior considering math grad school. I need to decide whether to take complex analysis or cryptology this semester. Complex analysis seems to be a recommended course for people ...

**0**

votes

**0**answers

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

**1**

vote

**1**answer

61 views

### Reduced echelon form of sparce matrices and constructing hash function

Let $G$ be a $d$-regular graph, and $A$ be the incidence matrix of $G$. Also suppose $B$ is a reduced echelon form of $A$ such that computations are in $\mathbb F_2$. Given matrix $B$, can we find ...

**1**

vote

**1**answer

117 views

### Does this modification of the General Number Field Sieve factor integers?

The General Number Field Sieve
factors composite $n$ basically this way.
Select homogeneous polynomials with integer coefficients $f(x,y),g(x,y)$
s.t. $f(x,1),g(x,1)$ have common root modulo $n$ but ...

**3**

votes

**1**answer

123 views

### Equivalence between Diffie Hellman and Discrete Log

For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?
Is there any group for which we suspect them to be different?
Could there be a finite ...

**2**

votes

**0**answers

134 views

### What should I read to prepare for research in Number Theoretic Cryptography? [closed]

I am not sure if this is the correct place to ask this, and if it is not the correct place, I would appreciate if you could direct me to where I could get this problem answered.
I have just begun my ...

**0**

votes

**0**answers

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

**2**

votes

**1**answer

103 views

### Mestre-type algorithm for higher-genus curves?

Is there an analogous algorithm for genus $g>2$ curves that, given a complete set of invariants, outputs a curve with those invariants?
(I'm interested in particular in $g=3$.)
Any references ...

**9**

votes

**3**answers

355 views

### “Most Similar Vector Problem” on an Integer Lattice?

I am currently working on problem that I think could be expressed as an integer lattice problem.
Given $u \in \mathbb{R}^n$ and a bounded integer lattice $L = \mathbb{Z}^n \cap [-M,M]^n$ I would like ...

**1**

vote

**1**answer

64 views

### Optimal covering and CSPNG

Consider a function $f: \{0,1\}^n \to \{0,1\}^{cn}$, where $c>1$.
A random $f$ with high probability generates optimal covering of $\{0,1\}^{cn}$,
i. e.:
$\forall x \in \{0,1\}^{cn}$ $\exists y ...

**-4**

votes

**1**answer

123 views

### Elliptic Curve Multiplication [closed]

What would happen if I performed Elliptic Curve multiplication on some random point within the FiniteField that wasn't actually on the curve? I assume that I would get a point in return but would that ...

**11**

votes

**2**answers

481 views

### “The Two Sheriffs” puzzle -2: threshold for security

I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects.
...

**12**

votes

**2**answers

634 views

### Factorization when a factor is partially known

Let's say that I have a very large number of the order ($10^{250+}$) which is composite. I have been given one of its factor partially to a significant amount of digits (say 75+). Then, how can I ...

**6**

votes

**3**answers

388 views

### A balls and urns model for a hashing problem

Fix $N \in \mathbb{N}$. Suppose we throw $N$ numbered balls into $N$ numbered urns, so that for each $b \in \{1,\ldots,N\}$, ball $b$ lands in urn $j$ with equal probability $1/N$. Choose a number $c ...

**2**

votes

**0**answers

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

**2**

votes

**1**answer

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

**1**

vote

**0**answers

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

**2**

votes

**1**answer

119 views

### Combinations Question about the construction of some special sets [closed]

Let $n$ and $k$ be two given numbers. The goal is to choose $n$ subsets from $\{1,2,...,n\}$ such that the union of any $k$ of these subsets is the set $\{1,2,...,n\}$ and the union of any $m < k$ ...

**2**

votes

**1**answer

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

**7**

votes

**1**answer

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

**1**

vote

**1**answer

102 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

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

**2**

votes

**1**answer

226 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

102 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

57 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

**1**answer

100 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

**2**answers

213 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

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

55 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

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

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

**16**

votes

**5**answers

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

**0**

votes

**0**answers

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

**12**

votes

**1**answer

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

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

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

**8**

votes

**1**answer

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

**0**

votes

**1**answer

699 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

**4**answers

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

244 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

395 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

**2**answers

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

**0**

votes

**0**answers

126 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

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

**13**

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

**2**

votes

**1**answer

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

**5**

votes

**1**answer

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

**2**

votes

**3**answers

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