Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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 ...
The Rook's user avatar
  • 528
42 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
38 votes
3 answers
5k 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 ...
Giorgio Camerani's user avatar
20 votes
1 answer
1k 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 ...
v s's user avatar
  • 2,208
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 ...
Artem Kaznatcheev's user avatar
35 votes
6 answers
6k 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 ...
Huck Bennett's user avatar
  • 4,888
31 votes
3 answers
19k 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 ...
Thomas Owens's user avatar
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 ...
Andy Drucker's user avatar
  • 4,634
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-...
Anonymous's user avatar
  • 4,041
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 ...
Joshua Herman's user avatar
22 votes
2 answers
2k views

Can a fully homomorphic encryption be used for oblivious code execution?

After reading this answer a while ago, I took an interest in fully homomorphic encryption. After reading the introduction of Gentry's thesis, I started wondering if his encryption scheme could be used ...
Alex ten Brink's user avatar
18 votes
2 answers
981 views

Are theoretically sound pseudorandom generators used in practice?

As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they ...
Henry Yuen's user avatar
  • 3,798
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 ...
Sadeq Dousti's user avatar
  • 16.5k
16 votes
1 answer
573 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?
Hendrik Brummermann's user avatar
16 votes
2 answers
346 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 $\...
Suresh Venkat's user avatar
16 votes
3 answers
738 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 ...
Sadeq Dousti's user avatar
  • 16.5k
15 votes
3 answers
721 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 ...
Per Vognsen's user avatar
  • 2,161
11 votes
2 answers
504 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 ...
Yasser Sobhdel's user avatar
10 votes
1 answer
379 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 ...
Omid Etesami's user avatar
10 votes
1 answer
365 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 ...
Sariel Har-Peled's user avatar
9 votes
2 answers
985 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 ...
Sadeq Dousti's user avatar
  • 16.5k
9 votes
2 answers
360 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 ...
Kaveh's user avatar
  • 21.7k
7 votes
1 answer
418 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 ...
Kaveh's user avatar
  • 21.7k
5 votes
0 answers
147 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 \...
Michael Wehar's user avatar
4 votes
2 answers
589 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 ...
Sadeq Dousti's user avatar
  • 16.5k
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 ...
Maverickgugu's user avatar
3 votes
1 answer
1k 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 ...
Yasser Sobhdel's user avatar
3 votes
0 answers
194 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 ...
Yasser Sobhdel's user avatar