Questions tagged [cryptography]
Questions on the mathematics behind cryptography, cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
1,942 questions
-2 votes
0 answers
36 views
Related precise SAT encoding of SHA-256. [closed]
Respected mathematicians, I would like to know if there is any GitHub repository that accurately converts SHA-family algorithms into SAT problems. So far, I found the SAT encoder by Saeed Nataj to be ...
2 votes
1 answer
32 views
Help understanding this Carter-Wegman proof on the lower bound of collisions in a hash family
In this paper: https://www.sciencedirect.com/science/article/pii/0022000079900448 Proposition 1 explains how the probability of a collection of hash functions $H$ with each $f\in H$ mapping $A$ to $B$ ...
2 votes
1 answer
67 views
Semifield / Division Ring and Gaussian elimination.
Discrete logarithm is difficult because, unlike integer division where magnitudes exist, and calculation can proceed iteratively by test-comparing and subtracting, the concept of magnitude doesn't ...
- 355
1 vote
0 answers
27 views
Grouping of Polynomial Ring Calculation [duplicate]
I am currently working my way through The Beginner’s Textbook for Fully Homomorphic Encryption by Ronny Ko. I cant wrap my head around how he grouped those terms up (p.100). If anybody could help me ...
- 27
1 vote
2 answers
138 views
How to solve system of 2 arbitrary bivariate quadratic equations over finite field?
I'm in the process of needing a solver for bivariate quadratic system of 2 equations over finite field - this is to estimate the time complexity of breaking an algorithm that I'm designing. Most ...
- 355
3 votes
1 answer
96 views
Proving isomorphism from $\mathbb{Z}_2 \times \pm QR_n$ to $\mathbb{Z}^*_n$ ($QR$ being quadratic residue) for a safe biprime $n$
The statement is, For any safe biprime $n = p \cdot q$ with $p = 2p' +1$ and $q = 2q' +1$, it holds that $\mathbb{Z}^*_n$ is isomorphic to $\mathbb{Z}_2 \times \pm QR_n$, $\pm QR_n$ being the union of ...
1 vote
0 answers
59 views
Are there proven lower bounds for collision search complexity in hash functions built from pseudorandom permutations?
It is well known that the birthday paradox suggests that finding collisions in an n-bit hash function requires about $O(2^{n/2})$ evaluations. This heuristic underlies the common assumption that ...
- 11
1 vote
1 answer
54 views
Is $f(a, b) = g(a) \oplus h(a \oplus b)$ buildable from XOR and 1 when constant over $a$?
Context I have a model of computation in which the only operations I can use are functions of the form $f(a, b) = g(a) \oplus h(a \oplus b)$, where $g, h : \mathbb{B}^n \rightarrow \mathbb{B}$ are ...
0 votes
0 answers
85 views
Possible RSA Coppersmith attack with given leak and quadratic
I am scratching my head with this cryptography problem but can't seem to find the attack: ...
user1656803
1 vote
1 answer
100 views
Understanding the group structure of Curve25519: decomposition and cyclicity
I am struggling with understanding the group structure of points on the elliptic curve Curve25519, which is widely used in cryptography. I read that the group of points $E(\mathbb{F}_p)$ on Curve25519 ...
- 11
0 votes
1 answer
100 views
Lattice SVP and minimum distance of linear code
Both of the problems in the title have a decision version which is NP-hard. My question is whether if SVP can be computed for a tractable example, can a minimum distance codeword for a related linear ...
- 335
7 votes
3 answers
206 views
Probability that a linear combination of given matrices over a finite field is invertible
Given finite field ${\Bbb F}_q$ and invertible and linearly independent matrices $S_1, S_2, \dots, S_m \in {\Bbb F}_q^{n \times n}$, if one samples $k_1, \dots, k_m \in {\Bbb F}_q$ uniformly, is there ...
- 1,220
1 vote
1 answer
30 views
Breaking CDH (computation diffie hellman) based on bilinear pairing
I am reading the paper entitled "Identity-Based Distributed Provable Data Possession in Multicloud Storage". On page 10, it gives a security analysis of the proposed protocol using proof by ...
- 209
0 votes
0 answers
21 views
Feldman’s VSS Scheme and one way homomorphisms
NOTE: I am cross posting between math stack exchange and crypto stack exchange. I am not sure who would be more appropriate to ask. I’m working on an educational resource that discusses Feldman’s ...
- 3,051
2 votes
0 answers
82 views
Caesar Cipher and Bayes Theorem [closed]
I recently came across this thesis, where the author discusses, on pages 42–45, how probability can be used to decipher ciphers like the Caesar cipher using Bayes' theorem. While I am familiar with ...
- 161