Questions tagged [cr.crypto-security]
Theoretical aspects of cryptography and information security.
26
questions
11
votes
7
answers
3k
views
How does Theoretical Computer Science relate to security?
When I think of software that is insecure I think that it is "too useful" and can be abused by an attacker. So in a sense securing software is the process of making software less useful. In ...
- 538
36
votes
3
answers
4k
views
Consequences of Factoring being in P?
Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a ...
- 6,615
20
votes
1
answer
986
views
Is there a better than linear lower bound for factoring and discrete log?
Are there any references that provide details about circuit lower bounds for specific hard problems arising in cryptography such as integer factoring, prime/composite discrete logarithm problem and ...
- 2,198
39
votes
3
answers
4k
views
Is the integer factorization problem harder than RSA factorization: $n = pq$?
This is a cross-post from math.stackexchange.
Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $...
user17
18
votes
1
answer
3k
views
Bitcoin and preventing double spending in decentralized digital currencies
A recent approach to creating a decentralized online currency, called Bitcoin, has been generating some interest. The goal is to have a way to transfer currency without a central authority and without ...
- 10.1k
30
votes
3
answers
18k
views
What is the difference between a second preimage attack and a collision attack?
Wikipedia defines a second preimage attack as:
given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1).
Wikipedia defines a collision attack as:
find two arbitrary ...
- 403
35
votes
5
answers
5k
views
Fast Reduction from RSA to SAT
Scott Aaronson's blog post today gave a list of interesting open problems/tasks in complexity. One in particular caught my attention:
Build a public library of 3SAT instances, with as few variables ...
- 4,493
27
votes
3
answers
2k
views
Cryptography without assumptions -- seeking an overview
Suppose $P = NP$ and a fast linear-time algorithm for SAT appears tomorrow. Suddenly RSA is insecure, much of our modern communication system is broken, and we need to reconsider how to keep secrets ...
- 4,584
25
votes
4
answers
4k
views
Arguments for existence of one-way functions
I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-...
- 3,993
23
votes
1
answer
2k
views
Knot Recognition as a Proof of Work
Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion.
Is it possible to use a Decision problem ...
- 1,631
16
votes
1
answer
563
views
Why is it important that the secret is at the end when signing with MD5?
it is often said that when using the MD5 algorithm to sign some arbitrary information, the shared secret has to be at the end. Why?
16
votes
2
answers
319
views
On the status of learnability inside $\mathsf{TC}^0$
I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\...
- 31.8k
9
votes
2
answers
832
views
One-Way Permutations without Trapdoor
In Short: Assuming one-way permutations exist, can we construct one that has no trapdoor?
More info:
A one-way permutation is a permutation $\pi$ which is easy to compute, but hard to invert (see the ...
- 16.3k
3
votes
1
answer
944
views
Subexponential hardness assumption
Edited
I want to read more about subexponential hardness assumption, but I didn't find any good survey on this. I just took a look at Heavy-tailed distribution and Some properties of subexponential ...
- 654
15
votes
3
answers
684
views
Hardness Guarantees for AES
Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring.
I wonder whether such kind of provable security exists for ...
- 16.3k
14
votes
3
answers
669
views
Associative hash mixing
Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths ...
- 2,151
11
votes
2
answers
476
views
straight-line simulatability
Does any body know any good reference for meaning of straight-line simulatability?
I am currently deep into Universal Composability (UC) framework of Canetti but I can't find any good reference for ...
- 654
10
votes
1
answer
332
views
Can we construct a k-wise independent permutation on [n] using only constant time and space?
Let $k>0$ be a fixed constant.
Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that:
The construction uses constant time and space (i.e. preprocessing takes constant ...
- 9,566
7
votes
1
answer
376
views
Separation between existence of crypto primitives
I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My ...
- 21.3k
3
votes
0
answers
190
views
Simulator Efficiency versus Algorithm Efficiency
I have a question about the simulator efficiency. I am reading a group key exchange protocol which is UC-Secure (the security is proven on universal composability framework of Canetti). The proof uses ...
- 654
17
votes
1
answer
1k
views
Where's the Flaw in Blum-Feldman-Micali's Method
Blum, Micali, and Feldman (BFM) put forward a new (cryptographic) model, in which all parties (honest or adversarial) have access to some string. The string is assumed to be selected according to some ...
- 16.3k
10
votes
1
answer
369
views
Reducing factoring prime products to factoring integer products (in average-case)
My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring.
Assuming the problem of
FACTORING:[Given $N ...
- 101
8
votes
2
answers
351
views
Using negative results to prove positive results in computability theory
Many results in cryptography depend on impossibility results/conjectures in complexity theory. For example, public-key cryptography using RSA is believed to be possible because of the conjecture about ...
- 21.3k
5
votes
0
answers
143
views
How hard is it to generate a set of relatively prime numbers between two given bounds?
Informal Question
How hard is it to generate a set of relatively prime numbers between two given bounds?
Decision Problem
Given $a$, $b$, and $k \in \mathbb{N}$. Does there exist a set $S \...
- 4,900
4
votes
2
answers
559
views
Resources on Cryptographic Applications of Expander Graphs
I want to read papers on cryptography like
How to Recycle Random Bits
or Security Preserving Amplification of Hardness. They use random walks on expander graphs.
I need a short introduction to the ...
- 16.3k
4
votes
1
answer
3k
views
The significance of NP-Hard Problems in Cryptography
I didn't refer any literature but thought this was ideal to get views from people here..
Assuming that P=NP is proved would cryptography(only provable security) be impossible? Since the adversary can ...
- 269