Questions tagged [cr.crypto-security]

Theoretical aspects of cryptography and information security.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
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?
user avatar
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 $\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
  • 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 ...
user avatar