27
$\begingroup$

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 from each other.

Question: Is there a good single reference (or short list) to gain a big-picture view of what is possible in crypto (and in the allied field of "security") without intractability assumptions? This could save civilization one day, and would also be nice to peruse in the meantime.

Discussion: Most of the cryptographic tasks we now study (OWFs, PRGs, PKE) are provably impossible in the $P = NP$ world (a world dubbed "Algorithmica" in an influential essay by Impagliazzo), but some things remain possible: communication with a one-time pad; distributed secret sharing; private info retrieval; and some other nice things. (Certain kinds of physical mechanisms such as locked boxes, devices implementing oblivious transfer, and quantum states can also come in handy. Of course there is always some kind of physical assumption about who can see what information.)

One can distinguish between information-theoretic security (which works against a computationally unbounded adversary) and "unconditional" security (which may require a bounded adversary, but still shows security under no unproven assumptions). I'm most interested in the info-theoretic case.

For starters, here is one bibliography of information-theoretic security (which, for my purposes, is unmanageably long and disparate).

Improve this question
$\endgroup$
8
  • $\begingroup$ Nice question, this isn't really an answer, but it might be of interest. Alfred Menezes and Neal Koblitz have a nice series of "Another Look" papers where they ask some questions similar to your own, but also go into the whole "models of security" direction as well. I discussed it briefly in this answer, but I am not sure if this is too applied of an approach. $\endgroup$
    – Artem Kaznatcheev ♦
    Commented Dec 4, 2013 at 5:37
  • 3
    $\begingroup$ I would suspect that one can use such a SAT algorithm itself to find alternatives to current PKCs and unconditionally secure systems. $\endgroup$
    – Turbo
    Commented Dec 4, 2013 at 10:41
  • $\begingroup$ Note that RSA is not NP-Complete, so requiring P=NP to factor might be overkill. $\endgroup$
    – user834
    Commented Dec 4, 2013 at 16:26
  • $\begingroup$ a large part of modern crypto hinges on intractability assumptions not for simplification/convenience but because no better results/provable limits are available from complexity theory (esp average case complexity)... see also crypto.se $\endgroup$
    – vzn
    Commented Dec 4, 2013 at 17:13
  • 3
    $\begingroup$ Here is a survey by Ueli Maurer which, although a bit dated, is quite informative: ftp.inf.ethz.ch/pub/crypto/publications/Maurer99.pdf‎ $\endgroup$
    – user20492
    Commented Dec 5, 2013 at 5:41

3 Answers 3

Reset to default
16
$\begingroup$

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 integrity and authentication: universal hash functions.

  • For anonymity: anonymous communication (e.g., DC nets, onion-based schemes, p2p networks based upon rapidly mixing random walks), distance bounding protocols.

  • For security based upon physical assumptions: PUFs (physically unclonable functions), integrity codes (Capkun et al.), quantum cryptography, security using TPMs or tamper-resistant hardware.

There are lots of papers on those topics; too many to summarize all the results in the literature.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks D.W. I know it's too much ground to summarize in an answer; I'm hoping to find useful books or surveys. $\endgroup$
    – Andy Drucker
    Commented Dec 4, 2013 at 2:27
  • $\begingroup$ @AndyDrucker, my recommendation would be to read the seminal or state-of-the-art papers on the topics of interest to you. I'm not sure you're going to find a book that covers all the work in this area (some of which has happened in the past 5-10 years). Even if you get lucky and discover some book, it'll already start falling behind the latest research literature by the time it appears on book shelves. $\endgroup$
    – D.W.
    Commented Dec 4, 2013 at 2:29
  • 2
    $\begingroup$ I don't even aspire to the state-of-the-art. There's no truly up-to-date textbook for any area of TCS; yet one can still pick up Goldreich's books and get oriented to the fundamental results and concepts of complexity-based crypto. I wondered if anything similar had appeared for the info-theoretic side. $\endgroup$
    – Andy Drucker
    Commented Dec 4, 2013 at 2:42
4
$\begingroup$

This is a fairly complex question, as we really don't have a good overview of the area. Partially this is due to the fact the information-theory and the crypto community have been working on similar topics without really interacting enough with each other. Many good points have been given above. I would just like to add a few extra observations:

  • We have had a large body of works dealing with the problem of secret-key agreement (and secure communication) with a given setup. Here, a setup means for example that the parties in the system (say Alice, Bob, and the adversary Eve) share some correlated information coming from a tripartite probability distribution. An alternative setup could consist of noisy channels (e.g., Alice can send information to Bob and Eve through noisy channels). Additionally, Alice and Bob are connected through a communication channel (which may or may not be authenticated). This line of work started with Aaron Wyner in the 70s, who introduced the Wiretap channel model, and was further cleaned up by Maurer and others in the 90s. Also, lots of techniques in this area (privacy amplification, information reconciliation) ended up being used in the Quantum Key-Distribution (QKD) setting. A fair amount of work is being done here even to date, for example in related areas such as non-malleable extractors, etc. The bounded-storage model is also a setting which is different from the above, but uses similar techniques and has similar goals.

  • Beyond just secret sharing, you will find a large body of works on information-theoretically secure multi-party computation (MPC). In particular, the line of works initiated by the BGW protocol is completely information theoretical.

  • Also, I am not sure how far the scope of the question goes: If for example P = NP indeed holds, but we can somehow justify the presence of a random oracle in the sky, then symmetric cryptography is still possible. Sometimes, such models are indeed used to prove security of certain cryptographic constructions (like hash functions or block ciphers), and the techniques are completely information-theoretic.

  • Information-theoretic techniques in cryptography also come up often as an intermediate tool in complexity-theoretic results, but I think this is beyond the scope of the question. (See Maurer's work on random systems and on indistinguishability amplification as an example of this type of work.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ " we can somehow justify the presence of a random oracle in the sky" what are you exactly talking here? How is symmetric 'public' key crypt possible here? $\endgroup$
    – Turbo
    Commented Dec 6, 2013 at 15:37
  • 1
    $\begingroup$ @J.A I believe he means Bellare and Rogaway's random oracle model, see e.g. cseweb.ucsd.edu/~mihir/papers/ro.html. This model is a heuristic, often a useful one, but there there are good reasons to be skeptical: arxiv.org/abs/cs/0010019 $\endgroup$
    – Sasho Nikolov
    Commented Dec 6, 2013 at 18:49
  • $\begingroup$ ic.. what exactly goes on here? do you have an idea at a concrete level? All info theoretic symmetric key schemes I have seen are based on extracting common information from correlated ones and hence possibly cannot be made into a public key version. Is there a fundamental idea here that enables a feasible public key crypto solution that is info theoretically secure? $\endgroup$
    – Turbo
    Commented Dec 6, 2013 at 19:30
  • 2
    $\begingroup$ Let me elaborate: In the random oracle model, where all parties have access to a random oracle RO, honest parties possessing a secret key SK can encrypt a message M securely as (R, M + RO(SK||R)), where R is the encryption randomness (and is freshly generated upon each encryption), + denotes bit-wise xor (here assume that RO's output length equals the message length). The security of this scheme relies only on the random-oracle being random. In contrast, it is known by the work of Impagliazzo and Rudich that public-key encryption is not achievable in the random-oracle model. $\endgroup$
    – Stefano Tessaro
    Commented Dec 7, 2013 at 15:07
3
$\begingroup$

Some research groups in Europe have pursued this line of research; more specifically, because of my interest in information theory I have ran into the work of Ueli Maurer and his school, which is both significant from purely information theoretic point of view (which I am more familiar with) and also offers some practical approaches to information theoretic security.

Related to the above line of work, some places you might want to consider looking at are the PhD thesis of Christian Cachin and also Renato Renner (more quantum).

Of course, there is a whole different approach with keywords including BB84, Preskill-Shor, Artur Ekert, etc.

The above of course only reflects my limited experience, and surely there are many more approaches and interesting lines of work.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.