<p>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:</p>

<ul>
<li><p>For confidentiality: the one-time pad, the Wyner wiretap channel, secret sharing, quantum key exchange, etc.</p></li>
<li><p>For integrity and authentication: universal hash functions.</p></li>
<li><p>For anonymity: anonymous communication (e.g., DC nets, onion-based schemes, p2p networks based upon rapidly mixing random walks), distance bounding protocols.</p></li>
<li><p>For security based upon physical assumptions: PUFs (physically unclonable functions), integrity codes (Capkun et al.), quantum cryptography, security using TPMs or tamper-resistant hardware.</p></li>
</ul>

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

CC BY-SA 3.0
2013-12-04T02:27:14.113Z
Thanks D.W.  I know it's too much ground to summarize in an answer; I'm hoping to find useful books or surveys.
Andy Drucker
CC BY-SA 3.0
2013-12-04T02:29:31.030Z
@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.
D.W.
CC BY-SA 3.0
2013-12-04T02:42:11.197Z
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.
Andy Drucker
CC BY-SA 3.0
2013-12-04T02:10:14.237Z
2013-12-04T02:10:14.237Z
D.W.
<p>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:</p>

<ul>
<li><p>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.</p></li>
<li><p>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. </p></li>
<li><p>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. </p></li>
<li><p>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.)</p></li>
</ul>

CC BY-SA 3.0
2013-12-06T15:37:38.170Z
" 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?
Turbo
CC BY-SA 3.0
2013-12-06T18:49:00.267Z
@J.A I believe he means Bellare and Rogaway's random oracle model, see e.g. http://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: http://arxiv.org/abs/cs/0010019
Sasho Nikolov
CC BY-SA 3.0
2013-12-06T19:30:32.520Z
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?
Turbo
CC BY-SA 3.0
2013-12-07T15:07:16.850Z
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.
Stefano Tessaro
CC BY-SA 3.0
2013-12-06T12:58:01.623Z
2013-12-06T12:58:01.623Z
Stefano Tessaro
<p>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. </p>

<p>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). </p>

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

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

CC BY-SA 3.0
2013-12-05T04:32:28.350Z
2013-12-05T04:32:28.350Z
Mohammad Bavarian
<p>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. </p>

<p><strong>Question:</strong> 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") <em>without</em> intractability assumptions? This could save civilization one day, and would also be nice to peruse in the meantime. </p>

<p><strong>Discussion:</strong> 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 <a href="http://cseweb.ucsd.edu/~russell/average.ps">essay</a> by Impagliazzo), but some things remain possible: communication with a <a href="http://en.wikipedia.org/wiki/One-time_pad">one-time pad</a>; distributed <a href="http://en.wikipedia.org/wiki/Secret_sharing">secret sharing</a>; <a href="http://en.wikipedia.org/wiki/Private_information_retrieval">private info retrieval</a>; and some other nice things.
(Certain kinds of physical mechanisms such as <a href="http://en.wikibooks.org/wiki/Cryptography/Public_Key_Overview">locked boxes</a>, devices implementing <a href="http://en.wikipedia.org/wiki/Oblivious_transfer">oblivious transfer</a>, and <a href="http://en.wikipedia.org/wiki/Quantum_key_distribution">quantum states</a> can also come in handy.  Of course there is always some kind of physical assumption about who can see what information.)</p>

<p>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.  </p>

<p>For starters, here is one <a href="http://itsecurity.orgfree.com">bibliography</a> of information-theoretic security (which, for my purposes, is unmanageably long and disparate).</p>

CC BY-SA 3.0
2013-12-04T05:37:01.297Z
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"](http://anotherlook.ca/) 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](http://cstheory.stackexchange.com/a/7299/1037), but I am not sure if this is too applied of an approach.
Artem Kaznatcheev
CC BY-SA 3.0
2013-12-04T10:41:20.887Z
I would suspect that one can use such a SAT algorithm itself to find alternatives to current PKCs and unconditionally secure systems.
Turbo
CC BY-SA 3.0
2013-12-04T16:26:42.617Z
Note that RSA is not NP-Complete, so requiring P=NP to factor might be overkill.
user834
CC BY-SA 3.0
2013-12-04T17:13:54.533Z
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](http://crypto.stackexchange.com/)
vzn
CC BY-SA 3.0
2013-12-05T16:36:33.953Z
see also [why isnt there crypto based on NP hard problems](http://cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard) cs.se
vzn
CC BY-SA 3.0
2015-07-20T01:40:08.983Z
@AndyDrucker I thought $SAT$ needs to have at least a quadratic time algorithm http://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat.
Turbo
CC BY-SA 4.0
2023-09-22T00:53:33.137Z
Even if their is a linear time SAT algorithm, could their be a function that is O(n) to compute one way and O(n^10) to compute the other way or reduce to SAT? With say a 16384 bit key
Colonizor48
<cr.crypto-security>
Cryptography without assumptions -- seeking an overview
Andy Drucker
# Cryptography without assumptions -- seeking an overview

(Asked by: username_0 on 2013-12-04)

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](http://cseweb.ucsd.edu/~russell/average.ps) by Impagliazzo), but some things remain possible: communication with a [one-time pad](http://en.wikipedia.org/wiki/One-time_pad); distributed [secret sharing](http://en.wikipedia.org/wiki/Secret_sharing); [private info retrieval](http://en.wikipedia.org/wiki/Private_information_retrieval); and some other nice things.
(Certain kinds of physical mechanisms such as [locked boxes](http://en.wikibooks.org/wiki/Cryptography/Public_Key_Overview), devices implementing [oblivious transfer](http://en.wikipedia.org/wiki/Oblivious_transfer), and [quantum states](http://en.wikipedia.org/wiki/Quantum_key_distribution) 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](http://itsecurity.orgfree.com) of information-theoretic security (which, for my purposes, is unmanageably long and disparate).

**Tags:** cr.crypto-security

> **Comments:**
> **username_1**: 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"](http://anotherlook.ca/) 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](http://cstheory.stackexchange.com/a/7299/1037), but I am not sure if this is too applied of an approach.  
> **username_2**: I would suspect that one can use such a SAT algorithm itself to find alternatives to current PKCs and unconditionally secure systems.  
> **username_3**: Note that RSA is not NP-Complete, so requiring P=NP to factor might be overkill.  
> **username_4**: 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](http://crypto.stackexchange.com/)  
> **username_4**: see also [why isnt there crypto based on NP hard problems](http://cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard) cs.se  
> **username_2**: @AndyDrucker I thought $SAT$ needs to have at least a quadratic time algorithm http://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat.  
> **username_5**: Even if their is a linear time SAT algorithm, could their be a function that is O(n) to compute one way and O(n^10) to compute the other way or reduce to SAT? With say a 16384 bit key  

---

## 3 answers

### Answer by username_6 on 2013-12-04. Score: 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 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.

> **Comments:**
> **username_0**: Thanks username_6  I know it's too much ground to summarize in an answer; I'm hoping to find useful books or surveys.  
> **username_6**: @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.  
> **username_0**: 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.  

---

### Answer by username_7 on 2013-12-06. Score: 4

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.)

> **Comments:**
> **username_2**: " 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?  
> **username_8**: @J.A I believe he means Bellare and Rogaway's random oracle model, see e.g. http://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: http://arxiv.org/abs/cs/0010019  
> **username_2**: 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?  
> **username_7**: 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.  

---

### Answer by username_9 on 2013-12-05. Score: 3

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.


---

