Questions concerning the mathematics of secure communication. Relevant topics include elliptic curve cryptography, secure key exchanges, and public-key cryptography (eg. the RSA cryptosystem).

learn more… | top users | synonyms

7
votes
5answers
1k views

Zero knowledge proof of equality

Alice and Bob each secretly chooses an integer between 1 and 10, a and b. They want to know (with high probability) whether or ...
1
vote
1answer
39 views

Dual lattices up to a q scaling factor

In this paper : https://eprint.iacr.org/2011/501.pdf There is an equality page 10, in the second paragraph considered by the authors as "easy to check". If someone could explain to me why the set at ...
0
votes
0answers
66 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 ...
18
votes
1answer
540 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 ...
1
vote
1answer
169 views

Finding cyclic subgroups of points on elliptic curves for 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 a theorem: Elliptic curves ...
0
votes
0answers
42 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
1answer
62 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
1answer
126 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
1answer
133 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
0answers
142 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 ...
6
votes
1answer
171 views

Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult. Is there a polynomial analog of this problem ...
0
votes
0answers
41 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
1answer
107 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
3answers
372 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
1answer
68 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
1answer
127 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
2answers
494 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
2answers
637 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
3answers
407 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 ...
3
votes
0answers
171 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
1answer
94 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
0answers
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 ...
2
votes
1answer
129 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
1answer
142 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
1answer
310 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
1answer
117 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
0answers
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
1answer
237 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
0answers
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 ...
0
votes
0answers
59 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
1answer
105 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
2answers
227 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
0answers
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
0answers
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 ...
5
votes
0answers
337 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
5answers
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
5answers
636 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
0answers
179 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
1answer
436 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
0answers
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
3answers
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 ...
9
votes
1answer
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
1answer
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
4answers
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
0answers
245 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
1answer
411 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
2answers
400 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
0answers
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
0answers
232 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
2answers
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 ...