Questions tagged [cr.crypto-security]

Theoretical aspects of cryptography and information security.

Filter by
Sorted by
Tagged with
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
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
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
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
27 votes
4 answers
1k views

A lottery that you can be convinced that it is fair

(Sorry if this is well known.) I would like to give some item to one of $k$ agents, so that agent $j$ will get the item with probability $p_i$. Is there a cryptographic (or other) tool so that every ...
user avatar
  • 5,983
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
6 answers
802 views

Curriculum: Logical/Formal Methods in Security

At present I teach a small course (Four two hour lectures at the Masters level) on Logical Methods in Security, though the title Formal Methods in Security might be more apt. It covers briefly the ...
user avatar
  • 16.6k
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
23 votes
1 answer
691 views

Estimating a percentile among distributed nodes without revealing values

I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it. Problem: Suppose a list of N numbers is shared among a set of participants ...
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 ...
user avatar
21 votes
6 answers
3k views

Difference between theory and practice of security and cryptography?

What interesting differences are there between theory and practice of security and cryptography? Most interesting will of course be examples that suggest new avenues for theoretical research based on ...
21 votes
2 answers
973 views

PPAD and Quantum

Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
user avatar
  • 5,983
20 votes
4 answers
680 views

Is there current research into the implemention of Randomness Extractors?

Has there been research into implementing randomness extractor constructions? It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making ...
user avatar
20 votes
6 answers
1k views

Parallel pseudorandom number generators

This question is primarily related to a practical software-engineering problem, but I would be curious to hear if theoreticians could provide more insight in it. Put simply, I have a Monte Carlo ...
user avatar
20 votes
1 answer
988 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
20 votes
1 answer
687 views

Does cryptography have an inherent thermodynamic cost?

Reversible computing is a computational model that only allows thermodynamically reversible operations. According to Landauer's principle, which states that erasing a bit of information releases $kT ...
user avatar
  • 583
20 votes
2 answers
1k views

Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
user avatar
20 votes
2 answers
1k views

Can any computational challenge be transformed to proof-of-work?

The seemingly pointlessness of cryptocurrency mining raised the question of useful alternatives, see these questions on Bitcoin, CST, MO. I wonder whether there exists an algorithm that can convert ...
user avatar
  • 13.5k
18 votes
2 answers
522 views

Is it possible to encrypt a CNF?

Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that The function $\Psi$ can be computed in polynomial time from some secret random parameter $r$. $\Psi(\mathcal ...
user avatar
  • 13.5k
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
17 votes
2 answers
937 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 ...
user avatar
  • 3,708
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.4k
17 votes
0 answers
349 views

Does Factoring have a Statistical Zero Knowledge Proof?

The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to ...
user avatar
  • 3,708
17 votes
0 answers
519 views

Quantum Hardness of Finding Nash Equilibria

This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen. Their main result is that the existence of ...
user avatar
  • 5,973
16 votes
5 answers
980 views

Do "One Way Functions" have any applications outside crypto ?

A function $f \colon \{0, 1\}^* \to \{0, 1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm $A$, $\Pr[f(A(f(x))) = f(x)] < ...
user avatar
16 votes
3 answers
414 views

What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?

I am reading the classic "Hardness vs Randomness" by Nisan and Wigderson. Let $B=\{0,1\}$, and fix a function $l\colon \mathbb{N} \to \mathbb{N}$. They define a family of functions $G = \{G_n : B^{l(...
user avatar
  • 163
16 votes
2 answers
1k views

Does bit commitment yield oblivious transfer in the information-theoretic security model?

Suppose you have two arbitrarily powerful participants who don't trust each other. They have access to bit commitment (e.g., sealed envelopes containing data that one player can hand to the other but ...
user avatar
16 votes
1 answer
1k views

Password hashing using NP complete problems

Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
user avatar
  • 777
16 votes
1 answer
564 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
16 votes
1 answer
464 views

Complexity classes for proofs of knowledge

Prompted by a question Greg Kuperberg asked me, I'm wondering if there are any papers that define and study complexity classes of languages admitting various kinds of proofs of knowledge. Classes ...
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.4k
14 votes
2 answers
476 views

Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

In a paper titled "On Deniability in the Common Reference String and Random Oracle Model," Rafael Pass writes: We note that when proving security according to the standard zero-knowledge ...
user avatar
  • 16.4k
14 votes
2 answers
1k views

Best method of Error Correction in Quantum Key Distribution

As far as I can tell, almost all implementations of QKD use Brassard and Salvail's CASCADE algorithm for error correction. Is this really the best known method of correcting errors in a shared ...
user avatar
14 votes
1 answer
347 views

Generating Graphs with Trivial Automorphisms

I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism. It is "commonplace" (yet controversial!) to assume the existence ...
user avatar
  • 16.4k
14 votes
3 answers
670 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
14 votes
0 answers
242 views

Is it possible to make trapdoor board games?

Motivated partly by this MO question, I am wondering if it's possible to design a board game where there is a simple winning strategy but it's hard to find. For example, the game of picking a random ...
user avatar
  • 13.5k
14 votes
0 answers
296 views

Pseudorandom functions in ACC^0?

In the lower bound result by Ryan Williams (Non-uniform $\mathsf{ACC}$ circuit lower bounds), there is a mention of "little evidence that Pseudorandom function generators exist in $\mathsf{ACC}^0$. Is ...
user avatar
  • 1,334
13 votes
3 answers
3k views

How can DES have 6x4 S-Boxes and still be reversible?

Wouldn't data be lost when mapping 6-bit values to 4-bit values in DES's S-Boxes? If so, how can we reverse it so the correct output appears?
user avatar
13 votes
1 answer
567 views

What languages have been successfully cryptographically trapdoored?

An observation associated with asymmetric cryptography is that some functions are (believed to be) easy to perform in one direction but difficult to invert. Furthermore, if there exists some 'trapdoor'...
12 votes
2 answers
1k views

What is special about $2^{32}/\phi$ in cryptography?

In the Tiny Encryption Algorithm: Different multiples of a magic constant are used to prevent simple attacks based on the symmetry of the rounds. The magic constant, 2654435769 or 9E3779B916 is ...
user avatar
12 votes
3 answers
4k views

What are some examples of secret sharing schemes actually being used in real-world applications?

The concept of a secret sharing scheme is often attributed to Shamir (A. Shamir, How to share a secret, Comm. ACM, 22 (1979), pp. 612-613.) and Blakey (G. R. Blakey, Safeguarding cryptographic keys, ...
user avatar
12 votes
1 answer
2k views

Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits?

In chapter 10 of HAC (10.4.2), we see the well-known Feige-Fiat-Shamir identification protocol based on a zero-knowledge proof using the (presumed) difficulty of extracting square roots modulo a ...
user avatar
  • 1,003
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
11 votes
2 answers
608 views

On fooling $AC^0$

I have a few questions regarding fooling constant depth circuits. It's known that $\log^{O(d)}(n)$-wise independence is necessary to fool $AC^0$ circuits of depth $d$, where $n$ is the size of the ...
user avatar
11 votes
2 answers
313 views

Solvability of matrix filling

Matrix $A$ has dimension $n \times n(n-1)$. We want to fill $A$ using integers between $1$ and $n$, inclusive. Requirements: Each column of $A$ is a permutation of $1, \dots, n$. Any submatrix ...
user avatar
  • 777
11 votes
1 answer
400 views

Lower bounds on the period in integer factorization?

In 1975, Miller has shown how to reduce the factorization of integer $N$ to finding the period $r$ of a function $f(x)=a^x\;\bmod\;N$ such that $f(x+r)=f(x)$ with some randomly chosen $a<N$. It is ...
user avatar
11 votes
1 answer
1k views

Non-Uniform vs. Uniform Adversaries

This question arose in the context of cryptography, but below I will present it in terms of complexity theory, since people here are more acquainted with the latter. This question is related to ...
user avatar
  • 16.4k
11 votes
2 answers
477 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

1
2 3 4 5 6