32 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 ...
- 48.4k
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 ...
- 200k
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 ...
- 200k
13 votes
Cryptographic Secret Santa
Cryptographic Protocols with Everyday Objects (section 5) Typical cryptographic Secret Santa protocols require a fully homomorphic encryption system. These protocols are thus suitable for those ...
- 200k
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 &...
- 11.7k
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
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 ...
- 29.8k
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 $...
- 161k
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 $$...
- 124k
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,...
- 31.4k
7 votes
Conjecturally unsafe RSA primes $p=27a^2+27a+7$
This appears special case of "A New Special-Purpose Factorization Algorithm": https://pdfs.semanticscholar.org/1843/73605e846f90b0a9d7252931bab4c47a1ec7.pdf From the abstract: a new factorization ...
- 25.7k
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
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,477
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, ...
- 48.4k
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
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$ ...
- 38.3k
5 votes
Accepted
Breaking the rotate-then-substitute alphabetic cipher
As you point out, frequency analysis will yield (for cipher texts long enough, say longer than Shannon's unicity distance) a non-English text which has been transformed from English via the position ...
- 10.6k
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,206
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,434
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,456
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\...
- 4,744
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,395
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
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 ...
- 9,572
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
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,456
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
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
Only top scored, non community-wiki answers of a minimum length are eligible