The tag has no wiki summary.

learn more… | top users | synonyms

29
votes
7answers
13k views

Example of a good Zero Knowledge Proof.

I am working on my zero knowledge proofs and I am looking for a good example of a real world proof of this type. An even better answer would be a Zero Knowledge Proof that shows the statement isn't ...
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 ...
19
votes
4answers
2k views

Discrete logs vs. factoring

One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction ...
14
votes
5answers
590 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 ...
14
votes
4answers
2k views

Zero-knowledge proof of positivity

If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x? My bounty is ending ...
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 ...
12
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 ...
12
votes
2answers
604 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 ...
11
votes
5answers
2k views

Introducing Cryptology to Undergraduates

This summer I am going to give some lectures to some REU students. I am still tossing around ideas for what I am going to talk about, but one thing I would at least like to give one or two lectures ...
11
votes
2answers
460 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. ...
11
votes
1answer
422 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 ...
9
votes
3answers
626 views

Predicting if something is a code

I'm trying to help a non-mathematical friend by posting a question of his here. He studies literature and has come across a book which is written in a made-up language. The book is hundreds of ...
9
votes
1answer
621 views

What can I say about the permutation $\alpha\beta$ if I know the permutation $\beta\alpha$?

I'm looking into a secret sharing scheme that has a secret permutation $\theta$ which has the cycle structure (n/2)+(n/2) (i.e. two (n/2)-cycles). The permutation $\theta$ is decomposed into two ...
9
votes
2answers
3k views

Encrypting a message for multiple recipients

Let $m$ be a secret message that needs to be sent to $n >1$ recipients. Let each recipient $r_i$ have a public key $p_i$ and private key $s_i$. Is there a scheme such that we can encrypt the ...
9
votes
1answer
372 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 ...
8
votes
2answers
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 ...
8
votes
4answers
1k views

Is there a two-party multiplicative and additive secret sharing scheme ?

A secret sharing scheme such as Shamir's secret sharing allow to perform addition and multiplication for secret values so far as there is at least 3 participants. Addition of two secret values is done ...
8
votes
0answers
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 ...
7
votes
4answers
961 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 ...
7
votes
1answer
547 views

Any nice examples of small cancellation theory appearing in applied mathematics?

Are there any nice discussions of applications of small cancellation theory, or other cases of the word problem, in applied mathematics or algorithms for seemingly non-group theoretic problems? I ...
6
votes
3answers
331 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 ...
5
votes
3answers
634 views

Torus based cryptography

In cryptography one needs finite groups $G$ in which the discrete logarithm problem is infeasible. Often they use the multiplicative group $\mathbb{G}_m(\mathbb{F}_p)$ where $p$ is a prime number of ...
5
votes
1answer
354 views

Fastest algorithm to compute (a^(2^N))%m?

Hi. There are well-known algorithms for cryptography to compute modular exponentiation $a^b\%c$ (like Right-to-left binary method here : http://en.wikipedia.org/wiki/Modular_exponentiation). But do ...
5
votes
1answer
340 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$ ...
5
votes
3answers
2k views

Reduction from factoring to solving Pell equation

The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims There are reductions from factoring to solving Pell’s equation, and from solving Pell’s ...
5
votes
1answer
223 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" ...
5
votes
0answers
310 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
1answer
478 views

A silly question: is the number of points on a Jacobian (of a curve, over a finite field) known?

In a cryptography book I read that people does not known how to compute the number of points on a Jacobian of a hyperelliptic curve $C$ over a finite field $F_q$? Is this true? It seems easy to ...
4
votes
2answers
2k views

Whitening a random bit sequence

Given an (infinite) stream of uncorrelated random bit with a known "reasonable" bias (say 15-85% 1's) I want to whiten it, e.i. produce a shorter stream of bits that has no bias. The restriction is ...
4
votes
2answers
294 views

Good quality data/packages for statistical/structure analysis of words in the English language

From time to time I find myself wishing to calculate basic statistics on words in the English language. For example, today I found myself wanting a graph of the number of English words vs. their ...
4
votes
0answers
230 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)\::\: ...
4
votes
0answers
198 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
3answers
280 views

Cryptography and iterations

Hi, Here is a question in cryptography which is probably naive, and a reference request. I was wondering about the following key-exchange scheme, which is a variant on Diffie-Hellman. Consider a ...
3
votes
0answers
408 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
5answers
2k views

Analog to the Chinese Remainder Theorem in groups other than Z_n.

The idea hit me when I was in my Elliptic Curve Cryptography class. $Z_n \leftrightarrow Z_{f_1} \times Z_{f_2} \times ...$ where $f_1 \times f_2 \times ... = n$ and $\{f_1, f_2, ...\}$ are pairwise ...
2
votes
4answers
1k views

Recovering $\Phi(n)$ from a multiple?

I've been attending a series of lectures on Cryptography from an engineering perspective, which means that most of the assertions made are supplied without proof... here's one that the lecturer ...
2
votes
1answer
80 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 ...
2
votes
2answers
1k views

Weil pairing and Miller's algorithm

I'm studying Weil pairing and its applications in cryptography. I already know that it can be defined like this: $$w(P, Q) = (-1)^n\frac{f_P(Q)}{f_Q(P)}\frac{f_Q}{f_P}(\mathcal{O})$$ where ...
2
votes
1answer
458 views

Factoring and Index Calculus and duality between DL and factoring via compuational problems made easy through them

If factoring is in $P$ (with a blazing fast polynomial time in $P$), would it affect the index calculus algorithm used for Discrete Log calculation in any serious way? Other connections $1.)$ ...
2
votes
1answer
132 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 ...
2
votes
3answers
282 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 ...
2
votes
1answer
211 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
163 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
0answers
94 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
0answers
33 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 ...
2
votes
0answers
577 views

Elliptic Curves and cryptography. Recommended Reading [closed]

I have been studying RSA cryptography and want to extend this to ECC. I am interested in any books on the topic, that start off with basic principles of elliptic curves as I have almost zero knowledge ...
2
votes
0answers
199 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
1answer
420 views

Matrix Conjugates over Finite Fields

Thinking about Diffe-Hillman for matrices brought me to the following question. Given $\mathbb{F}_{p^k}$ the finite field with $p^k$ elements when can we find non-trivial solutions to ...
1
vote
2answers
188 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 ...