# Tag Info

17

Unfortunately, this doesn't seem to work (see below for details), and it seems hard to find a way to make this kind of idea yield a provably secure scheme. The problem with your general idea You're not the first to think of the idea of trying to base cryptography on NP-complete problems. The problem is that NP-hardness only ensures worst-case hardness, ...

16

The key phrases you are probably looking for are "information-theoretic cryptography" and "quantum cryptography". Searching the literature on these topics will turn up lots of work of the sort you are looking for. Some example highlights below: For confidentiality: the one-time pad, the Wyner wiretap channel, secret sharing, quantum key exchange, etc. For ...

11

Two answers that I learnt while writing a blog post about this question No: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. As Ron points out, this extends to computational complexity under plausible assumptions. Maybe: Nash equilibrium is arguably the flagship problem of "Christos ...

10

This is not an actual answer; I'm just sharing some results (which do not fit in one comment). Goldreich, Micali and Wigderson (J. ACM, 1991) proved that every language in NP has a zero-knowledge proof of language membership (assuming OWFs exist). To this end, their presented a ZK proof for graph 3-colorability. Later, Bellare and Goldreich (CRYPTO '92) ...

9

The main thing missing from your list is the beautiful 2006 paper of Klivans and Sherstov. They show there that PAC-learning even depth-2 threshold circuits is as hard as solving the approximate shortest vector problem.

9

SHA-1 was SHattered by Stevens et al. They demonstrated that collisions in SHA-1 are practical. They give the first instance of a collision for SHA-1. It is an identical-prefix collision attack that enabled the attacker to forge two distinct PDF documents that have the same SHA-1 hash value. I.e. They extended a given prefix $p$ with two distinct near-...

9

Boaz Barak addressed this in a blog post My takeaway from his post (roughly speaking) is that we only know how to design cryptographic primitives using computational problems that have some amount of structure, which we exploit. With no structure, we don't know what to do. With too much structure, the problem becomes efficiently computable (thus useless ...

9

There are essentially only two algorithms that I'm aware of: Use repeated-squaring, along the lines you mentioned. Factor $n$ using a state-of-the-art algorithm, then use the Chinese remainder thoerem. If $p$ is prime, you can compute $a^{b^c} \bmod p$ efficiently by computing $b^c \bmod p-1$ using fast exponentiation, call the result $d$, then computing $... 9 I will attempt to elaborate a bit on why CHKPRR shows that$\mathsf{PPAD}$is plausibly hard for quantum computers. At a high level, CHKPRR builds a distribution over end-of-line instances where finding a solution requires to either: break the soundness of the proof system obtained by applying the Fiat-Shamir heuristic to the famous sumcheck protocol, or ... 8 (wow! after three years of time passing, this is now easy to answer. funny how that goes! --Daniel) This "Learning with (Signed) Errors" (LWSE) problem, as invented-and-stated above by me (three years ago), trivially reduces from the Extended Learning with Errors (eLWE) problem first introduced in the work Bi-Deniable Public-Key Encryption by O'Neill, ... 8 Here is a "canned" answer that might be useful, but has no cryptographic depth (hopefully we get answers with depth as well). What makes for a good candidate OWF? The naive answer tends to boil down to "something that looks hard to invert to me", but the expert's response is usually more like "something that many smart people have tried to invert but failed"... 8 (Note: Andreas Björklund suggested a solution in the comments that I believe is better than the one described below. See http://eprint.iacr.org/2017/203, by Ball, Rosen, Sabin, and Vasudevan. In short, they give proofs of work based on problems like Orthogonal Vectors whose hardness is well understood and to which many problems (e.g., k-SAT) can be reduced ... 8 The application you mention is called "proof of useful work" in the literature, see for instance this article. You can use a fully homomorphic encryption scheme (where the plaintext is the CNF instance) to delegate the computation to an untrusted party without disclosing the input. This doesn't answer exactly your question, since such scheme doesn't map a ... 7 If there is an Arthur-Merlin protocol for knottedness similar to the [GMW85] and [GS86] Arthur-Merlin protocols for Graph Non Isomorphism, then I believe such a cryptocurrency proof-of-work could be designed, wherein each proof-of-work shows that two knots are not likely to be equivalent/isotopic. In more detail, as is well known in the Graph Non ... 7 The answer to your question is the same as with many other such assumptions in cryptography: despite a lot of effort no one has found any substantially faster quantum algorithms for lattice problems. Why do we assume that RSA is secure? We don't have any particular justification for its classical hardness other than the fact that no one has found any fast ... 7 One can encrypt an n-qubit state using a 2n-bit classical secret key. The idea is to use the key to select a random Pauli operator, and apply that operator to the secret as an encryption. (The inverse operator is applied to decrypt.) The resulting scheme is perfectly secure -- if the key is selected uniformly at random, then even an attacker who know a ... 6 In a CPA game, a key pair$(sk,pk)$is generated, and$pk$is given to the adversary. The adversary outputs a pair of messages$(m_0,m_1)$in the message space, such that$|m_0|=|m_1|$. A random bit$b \in \{0,1\}$is then generated, and$m_b$is encrypted and returned as the cipher$c = E_{pk}(m_b ; r)$, where$r$is the randomness used for encryption. The ... 6 All of what I am going to say is well-known (all the links are to Wikipedia), but here it goes: The approach used in RSA using pairs of primes can also be applied in a more general framework of cyclic groups, notably the Diffie-Helmann protocol that generalizes$\left(\mathbb{Z}/pq\mathbb{Z}\right)^{\times}$to an arbitrary group, notably elliptic curves ... 6 Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing. The easiest way to see this is to note that IND-CPA (left-or-right indistinguishability) implies real-or-random indistinguishability under chosen-plaintext attack:... 6 Yes, you can use Levin universal search to construct a "universal one-way function" (e.g., these lecture notes). From this one-way function you can then construct symmetric-key encryption primitives (pseudorandom generators, block ciphers, CPA/CCA-secure encryption) using standard theoretical constructions. One-way function$\to$pseudorandom generator: ... 6 To expand somewhat on Sasho Nikolov's comment... LWE is at least as hard as finding approximate solutions to SVP, but the approximation factors for which the reduction from SVP to LWE works are larger than the approximation factors for which we know NP-hardness ...the following is a reasonably complete view of things: This was part of Oded Regev's talk ... 6 Here is the problem: if$M$has low entropy (for example, if the attacker has side information that narrows$M$down to just two possible messages), then conditioned on$M+K$, the key$K$also has low entropy (there are only two possibilities for$K$). If the eavesdropper stores the first message (which was an encryption of$K$), then she can use it to ... 6 Feigenbaum in, Encrypting Problem Instances, proposes a definition (Def. 1) of encryption function for NP-complete problems which satisfies your requirements. She proves that the NP-complete problem Comparative Vector Inequalities admits such encryption function. She concludes with the main theorem that all NP-complete problems that are p-isomorphic to CNF-... 6 This question is probably too broad to be answerable here, because the answer depends on what kinds of security requirements you have, what the threat model is, and what assumptions we're willing to make -- there are many different versions of those. In other words, the "secure voting" problem is not one problem, but a broad class of problems. I suggest ... 5 Depth-2 TC0 probably can't be PAC learned in subexponential time over the uniform distribution with a random oracle access. I don't know of a reference for this, but here's my reasoning: We know that parity is only barely learnable, in the sense that the class of parity functions is learnable in itself, but once you do just about anything to it (such as ... 5 This We called Domain Separation, when we use same algorithm for different output size. Separation is necessary because if i found two messages which have hash value (SH256), differs only in last octet and then i can publish the hash value as first 7 octet showing i used SHA224. since i already have two messages colliding on SHA224 which i can use later for ... 5 No, there is no information-theoretic analog that is secure against computationally-unbounded adversaries. To form an analog, we'd need an injection$\varphi$that maps$x$in fine representation to$x$in coarse representation. But then Diffie-Hellman involves Alice sending$\varphi(x)$publicly, and Bob sending$\varphi(y)\$ publicly. An eavesdropper can ...

5

Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, Alain Tapp. "Authentication of Quantum Messages", FOCS 2002. http://www.cse.psu.edu/~ads22/pubs/PS-CSAIL/BCGST02-focs-final.pdf As with encryption, there is a protocol that requires no computational assumptions. It uses a key of length about 2n+2k to authenticate n qubits with security level 2^{-...

5

I believe you are talking about the existence of information-theoretically (unconditionally) secure key agreement schemes. You can prove that such schemes cannot be achieved with only authenticated channels from Alice to Bob and Bob to Alice. Nevertheless, if Alice, Bob, and Eve are in possession of some sort of correlated randomness, then it may be ...

Only top voted, non community-wiki answers of a minimum length are eligible