33
votes
Accepted
Cryptography and elliptic curves
Not directly, as far as I know, since explicitly computing large multiples of points in $E(\mathbb Q)$ is infeasible. However, people have considered lifting points from $E(\mathbb F_p)$ to $E(\mathbb ...
- 49.2k
26
votes
Accepted
A cipher proposed by Littlewood
Littlewood's cypher is a one-time-pad, which would be unbreakable if fed by a true random number generator, but Littlewood's pseudo-random number generator is broken. See Breaking Littlewood's cypher ...
- 208k
17
votes
Accepted
Primality test using the Golden Ratio
The primality test fails. For odd integers $n$, one has $\lfloor \phi^n \rfloor =L_n$, the $n$-th Lucas number. Now $L_{2737}\bmod 2737=1$, but $2737=7\cdot 17\cdot 23$ is composite.
There are three ...
- 208k
11
votes
Accepted
Number theory in symmetric cryptography
Here are a few interesting examples of symmetric primitives whose claimed security is/was based on number-theoretic problems:
From the 1980s: the famous Blum-Blum-Shub deterministic random bit ...
- 889
11
votes
Number theory in symmetric cryptography
The non-linearity in the block cipher AES comes from the pseudo-inversion function on the finite field $\mathbb{F}_{2^8}$, defined by
$$ p(x) = \begin{cases} x^{-1} & \text{if $x \not=0$} \\ 0 &...
- 12.2k
10
votes
Accepted
Knot Diffie–Hellman
Here I assume that by “addition” of knots you mean the usual connect sum, as defined here. With that said, I think you correctly ask the relevant question: “Is factoring knots difficult?”
In favour ...
- 30.2k
9
votes
Is strictly harder than NP-hard cryptography possible?
I think I may not understand your model of cryptography. My model would be that encryption is a polynomial time computable, injective, function from plaintexts of length $m$ to cipher texts of length $...
- 163k
8
votes
Primality test using the Golden Ratio
This is a variation of the Fermat primality test and it has pseudoprimes, related to the notion of a Lucas or Fibonacci pseudoprime. As Carlo says we are essentially considering the Lucas numbers
$$...
- 125k
7
votes
Accepted
Inverting a function
Yes, you can use the Lehmer-Permutation to make a function that is suitable for cryptography, whose solution is just as hard as the Diffie-Helman problem. The relevant papers are:
(1) Roberto Mantaci,...
- 32.1k
7
votes
Accepted
Explicit formulas of cardinal on an elliptic curve
Elliptic curves of the form $y^2=x^3+b$ were studied by Schrutka in the article Ein Beweis für die Zerlegbarkeit der Primzahlen von der Form $6n +1$ in ein einfaches und ein dreifaches Quadrat. He ...
- 13.5k
6
votes
Extending Vigenère method using arbitrary function
Suppose that I create a list of intgers $(a_1,a_2,a_3,\dots)$, where the $0\le a_i<26$ are chosen randomly, e.g., using quantum effects or micro-temperature changes. Then I share the list with you, ...
- 49.2k
6
votes
Number theory in symmetric cryptography
The book Stream Ciphers and Number Theory by Cusick, Ding and Renvall is devoted to this topic, stream ciphers being one kind of symmetric cipher. I give some examples from there that are not that ...
- 10.6k
6
votes
Accepted
How to compute the Müller modular polynomials?
The definition of the coefficients $a_{r,k}$ is given by theorem III.17 on page 53 of "Elliptic curves in cryptography" by I.F. Blake, G. Seroussi, N.P. Smart (Cambridge University Press, 1999) (also ...
- 5,543
6
votes
Accepted
On roots of irreducible quadratics modulo composites
Ability to find all roots leads to finding factorization of $N$. For example, if $N=pq$ is a product of two odd primes, and we find a root $x'$ of $x^2-1\equiv 0\pmod N$ such that $x'\equiv 1\pmod p$ ...
- 39.4k
5
votes
Which hard mathematical problems do you have to solve to earn bitcoins ?
Another way to earn bitcoin is not to mine them, but to have them wired to you from other bitcoin accounts. The transactions are signed using ECDSA. So if you solve the discrete logarithm problem in ...
- 1,256
5
votes
A p-adic logarithm as a limit of discrete logs
For $p\ge 3$ if $g$ is a generator of $(\Bbb{Z}/(p^2))^\times$ then it is a generator of all $(\Bbb{Z}/(p^k))^\times$. For $a\in \Bbb{Z}_p^\times$ there is a unique $l_{g,k}(a)\in \Bbb{Z}/(p-1)p^{k-1}...
- 3,482
5
votes
Are there trapdoor functions breakable by moderate polynomial degree complexity algorithm?
Q1 goes right back to the dawn of public-key cryptography, with Merkle's Secure communications over insecure channels (see also Merkle's historical note on this). Merkle showed that running this ...
- 889
5
votes
Accepted
Proving that a function is a trapdoor function
First, there is a site crypto.stackexchange.com that is typically better for questions like this.
Second,
Coming from a CS background, if I wanted to prove a problem was NP-hard, I would try to prove ...
- 2,486
5
votes
Knot Diffie–Hellman
Edit: Thanks to @SamNead, for pointing out that the conjugacy problem is polynomial time, albeit with horrible constants. See video here
There is some literature on Braid group cryptography.
Here is ...
- 10.6k
5
votes
A candidate for one-way functions
3-majority can be modeled with 2-SAT, so $f$ can be inverted in polynomial time. The majority of $x_1,x_2,x_3$ is 1 iff $(x_1\lor x_2)\land(x_1\lor x_3)\land(x_2\lor x_3)$, and it is 0 iff $(\lnot x_1\...
- 5,733
4
votes
Discrete logarithm for polynomials
Since you bring up binary linear feedback shift registers at the end, I feel that it may be of interest to describe a relevant simple special case I once worked out when a slightly perpelexed ...
- 1,372
4
votes
Number theory in symmetric cryptography
Lattice-based Cryptography (where "lattice" is in the sense of Euclidean lattices) can be used to develop both symmetric and asymmetric primitives.
One particularly interesting example is ...
- 2,486
4
votes
Are there algorithms for deciding or solving conjugacy in integer quaternion rings?
If you are talking about quaternions, then you can rewrite the equation $y = z^{-1}xz$ as $zy - xz = 0$ which is $\mathbb{R}$-linear in $z$. Therefore both problems can be solved quite easily using ...
- 10.4k
4
votes
Accepted
Given $n, c$ find $a>1,b$ such that $b ^ a \equiv c \pmod n$
After much struggling, I found out that this is currently deemed a hard problem; so there is no known efficient algorithm to solve it.
From the Encyclopedia of Cryptography and Security (2011):
...
- 281
4
votes
Cryptography with general RSA type integers?
Having more than two prime factors is already supported by the PKCS#1 standard. This is called a "multiprime RSA" algorithm.
On the plus size, this may offer some computational performance ...
- 10.6k
4
votes
Is it theoretically possible to find a factoring algorithm that runs in polynomial time?
I'm not sure this is a research level question but since it is about an open problem I'll interpret it as such. At this point, we cannot prove that there is a polynomial time factoring algorithm. ...
- 8,626
4
votes
Accepted
Maximum number of vectors with upper bound on pairwise inner products
This is an interesting twist on the usual question.
Relevant results are due to Welch, Kabatianski, Levenshtein, Sidelnikov. Welch's applies to arbitrary vectors, real or complex. The others apply to ...
- 10.6k
4
votes
Accepted
Can a polynomial be evaluated from evaluations of partial interpolations? (Or: can the unique solution of congruences be written in a certain way?)
No. The interpolating polynomial is a weighted sum $a(x) = \sum_{x_i} a(x_i) P_i(x)$ and the independence of the $a(x_i)$ from each other imposes the independence of the $P_i$ from each other, which ...
- 8,188
4
votes
Diffie Hellman cryptography based on graph isomorphism?
This protocol as it is stated is broken using a quotient attack. I am going to explain this technique in as general of a context that I can (this idea should also break generalizations of this ...
- 29.2k
4
votes
Method to solve system of exponential sums of the form $a^x+b^x=c$ given more equations than variables
I'm not sure about your method, but such equations can easily be turned into polynomial equations by introducing $u:=a^{x-1}$ and $v:=b^{x-1}$:
\begin{cases}
u+v=337 \\
au+bv=1267 \\
a^2u+b^2v=4825 \\
...
- 39.4k
Only top scored, non community-wiki answers of a minimum length are eligible