Questions tagged [cryptography]
Questions about the construction and analysis of protocols and algorithms for secure computation and communication (including authentication, integrity, and privacy aspects).
269 questions
2
votes
0
answers
88
views
Does my understanding violate anything known about NP-intermediate classes and crypto?
I've been sort of thinking about $C^{poly}$ witnesses for a certain reason for several years and sort of weaker senses of reductions of problems in the back of my mind, but I just recently saw results ...
- 53
0
votes
0
answers
87
views
Why is the Adlemanβs index calculus complexity constant relative to the size modulus's size?
According to https://pages.cs.wisc.edu/~cs812-1/adleman.pdf the complexity is stated to be $e^\sqrt{log_eqΓlog_elog_eq}$, but since the algorithm operates in a similar fashion than the Pohlig Hellman (...
- 59
0
votes
0
answers
127
views
Open Problem: Structural Learnability of Pseudo-Random Boolean Circuits
I would like to propose an open problem at the intersection of computational complexity, pseudorandomness, and circuit theory. This problem has potential implications for cryptography, AI model ...
- 1
0
votes
1
answer
63
views
Two vertical bars between 1xn matrix and a nonnegative integer in a cryptography paper
I am reading Indistinguishability Obfuscation from Well-founded Assumptions (pdf file) by Jain, Lin and Sahai, an important paper relating to program obfuscation in cryptography.
However, I think this ...
- 31
0
votes
1
answer
46
views
Fast heuristic for RSA key public vs. private matching
Lets say, full data about RSA keypair is known, as per PKCS#11:
...
2
votes
2
answers
81
views
How does the Goldreich-Levin Theorem imply the existence of secure pseudorandom generators?
I am reading the text "Computational Complexity, A Modern Approach". On pg183 it is explained how the Goldreich-Levin theorem implies the existence of a secure pseudorandom generator. The ...
- 33
1
vote
2
answers
145
views
Transform any string into the shortest coherent/unique numeric identifiant
Is there some algorithm that can transform any string input (of any length) into a shortest possible coherent/unique numeric identifiant.
By "coherent", I mean that the same input will ...
- 111
3
votes
1
answer
96
views
Weaknesses of the alternative RSA-like algorithm
Disclaimer: it is a purely out-of-curiosity question. We discussed this implementation with a friend and could not find any breaches, but I have a gut feeling that there might be some.
Consider a ...
- 964
1
vote
1
answer
111
views
Applications of a SAT Solver Oracle for Determining the Uniqueness of Solutions
I am exploring two kinds of model $π_{π,π,k}$ and $S_{m,n,k}$ within the realm of satisfiability problems (SAT).
Formal construction of $π_{π,π,k}$
To construct the $π_{π,π,k}$ model in ...
- 399
1
vote
1
answer
102
views
Can you unwind a cryptographic hash function's last round?
Given a cryptographic hash, $ \text{hash}(A || B || C) $, and the last block added to the hash, $ C $, can you determine $ \text{hash}(A || B) $?
In other words, can you roll back the last round of a ...
- 155
1
vote
2
answers
265
views
Reversible streaming hash function
Do any streaming hash functions exist that provide the same result if the input is reversed?
That is to say, is there some hash function, $h$, such that:
$$ h(h(h(h(0, x_1), x_2), ...), x_n) = h(h(h(h(...
- 155
-3
votes
1
answer
338
views
If Q* can break encryption would that prove P=NP?
At 12:11 in this video the creator talks about unverified rumors the Q* algorithm can break AES-192 encryption. If this is true, would this mean P = NP?
- 97
1
vote
1
answer
97
views
Converting encrypted messages to unencrypted results of an equally hard to reverse function
If we have some function, $f$ with an exponentially sized domain, mapping the set $\{0, 1\}^N$ to $\{0, 1\}$, could we do something like this:
For ease, let's say $E(x) = x^e (\text{mod} \; n)$. This ...
- 55
-1
votes
1
answer
96
views
(Zero-knowledge?) Proof of Connection
I have a conundrum to solve but am not knowledgeable enough about cryptography to know whether it's possible to do, and if so, what method to use.
I am a Provider and my task is to prove to some ...
- 99
3
votes
1
answer
79
views
What is the definition of security of universal hashing
As a cryptographic primitive, universal hashing should have somewhat a criterion on its security. How is its (computational) security defined? Or, in other words, what "breaks" a universal ...
- 117