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

0
votes
0answers
14 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 ...
16
votes
1answer
510 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
1answer
77 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
0answers
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
0answers
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
1answer
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
1answer
118 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
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
0answers
135 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
0answers
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
1answer
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
3answers
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
1answer
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
1answer
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
2answers
482 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
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
3answers
389 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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
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
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
0answers
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
0answers
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
1answer
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
2answers
214 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
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
0answers
331 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
615 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
170 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
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
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 ...
8
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
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
1answer
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
2answers
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
0answers
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
0answers
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
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 ...
2
votes
1answer
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
1answer
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$ ...