Transcript Document
Symbiosis Among Cryptography, Coding Theory, Distributed Algorithms and Quantum Computing Kannan Srinathan IIIT Hyderabad Our Focus • Achieving secure communication over an insecure channel adversary Sender Insecure channel Receiver Our Focus (Contd.) • A fundamental and practical problem • Initial set-back: Shannon’s pessimistic theorem • Circumventing Shannon: Independently achieved by all four fields Our Focus (Contd.) • Each of these four solutions has its own set of advantages and limitations • Each solution is “better” than the other three, in some sense. • These solutions are based on “orthogonal” assumptions and can be used together yielding improved security What’s So Difficult About the Problem? • Classically, a perfect solution is impossible! Shannon [1] proved that secure communication over an insecure channel is impossible. • The impossibility stems from the invariant that adversary knows all that receiver knows. [1] Shannon, Claude. "Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.28(4), page 656–715, 1949. Shannon’s Solution: Assume a Secure Channel! adversary Sender Insecure channel Receiver Secure channel Perfectly secure channels are necessary for perfectly secure communication How fast should the secure channel be? • Shannon proved that even if there is a secure shared key between sender and receiver, theoretically unbreakable ciphers must use a key at least as big as the message. This is impractical. • Conclusion: We need very fast secure channels Solution is Impractical! adversary Overall secure throughput: 1 Mbps Sender Insecure channel (1Gbps) Receiver Secure channel (1Mbps) • The secure communication throughput of the entire system is same as the cumulative bandwidth of truly secure channels in the system The Main Issue • Fast secure channels are required for efficient secure communication “Chicken-and-Egg” problem! Solving the Issue –Some sort of “assumptions” are necessary to resolve the main issue –Different assumptions lead to different “paradigms” of security Paradigm #1: Modern Cryptography • Shannon’s impossibility holds if the message is to be kept secure forever, however for all practical purposes it is enough to keep a message secure for a very long (finite) time • This paradigm is based on complexity theory • Assumption: Everybody’s (including adversary’s) computing power is polynomialtime bounded Solution #1: Modern Cryptographic Solution One-way functions – For simulating “slow” secure channel over a insecure channel – For example, Diffie-Hellman Key exchange, RSA etc. • Psedorandom generators (stream ciphers) and pseudorandom functions (block ciphers) – For simulating a fast secure channel over a slow secure channel – For example, Blum-Blum-Shub, DES, AES, etc. Diffie-Hellman Key Exchange [2] • Based on the hardness of the Discrete Logarithm problem [2] New Directions in Cryptography W. Diffie and M. E. Hellman, IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: 644654. The Protocol • Public information: A prime p and a generator g of the cyclic (multiplicative) group Z*p • Sender S chooses a random element ‘a’ from Z*p and sends (ga mod p) to R. • Receiver R chooses a random element ‘b’ from Z*p and sends (gb mod p) to S. • S computes K = (gb)a = gab (mod p) • R computes K = (ga)b = gab (mod p) Paradigm #2: Distributed Algorithmic Solution Distributed Algorithmic Solution • Shannon’s impossibility holds if the adversary possesses complete access to the channel • However for all practical purposes, the channel consists of a huge network of nodes and it may be assumed that not all of the network is simultaneously accessible to the adversary • This paradigm is based on Network theory • Key ingredient: Secret Sharing • Assumption: Everybody’s (including adversary’s) Bandwidth is bounded t-Secret Sharing • Shamir’s Protocol – Choose a t-degree polynomial p() over a (large enough) finite field – Let Secret s = p(0) – Shares are p(1), p(2), …p(n) for some n Ref: Adi Shamir. How to Share a Secret. CACM, 1979 Perfectly Secure Communication • Dolev et al. [3] Protocol: – – Sender shares the message using secret sharing and sends the shares to Receiver along different paths. Receiver collects all the shares, and reconstructs the message. [3] Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung Perfectly secure message transmission, J. ACM 40, 1 (1993), 17-47. Paradigm #3 Quantum Mechanical Solution Quantum Secret Key Establishment Protocol The Standard Setting Quantum Secret Key Establishment Protocol • • • • Sender S and receiver R share a quantum communication channel, via which quantum states can be transmitted. Two conjugate bases are used, say b1 and b2.as shown in the table. S chooses a random base, and based on the bit to send, it sends a qubit prepared in the corresponding state. R measures the qubit received, with a random base. If the base is different from what S used, the bit is lost, else R measures the actual bit. Bit b1 b2 0 1 Quantum SKEP (Contd.) • • • • • This process is repeated for all the bits. S and R publicly compare (through a classical channel) their respective bases, and discard all those bits where their bases were different. The bases are same for nearly half the number of bits. S and R now check whether adversary has intercepted (measured) any of these bits, by comparing a certain subset of the remaining bit strings. If more than p bits differ, they abort the key and repeat the process. Quantum SKEP (Contd.) • Eve will use the wrong basis approximately 50% of the time (while resending) • Bob measures a resent qubit with the correct basis there will be a 25% probability that he measures the wrong value. Paradigm #4 Coding Theoretic Solution Noise-based Secrecy • Shannon’s impossibility holds if the adversary can access all information that the receiver can access • However in practical scenarios, the channel is noisy and therefore it may be assumed that the noisy data received by the adversary is different from the noisy data received by the receiver • This paradigm is based on Information/Coding Theory • Assumption: Everybody (including adversary) receives different noisy versions of the data Intuitively … • Noise is bad for any system because – it can affect the system’s functionality, efficiency, accuracy and so on … Can Noise be Useful? • Usually NO – by definition (naturally, it is termed as ‘noise’ typically because of its adversarial nature!) Can Noise be Useful? (Contd.) • Rarely YES … but how? – Perhaps in situations where we need to simultaneously deal with another adversarial entity apart from noise – We may then hope that the two adversaries would fight among themselves making it easier for us to tackle them together, than each one individually Does Our ‘Hope’ Come True? • Are there real examples for such a ‘comedy of errors’ by the adversarial entities? • YES Who’s Are Our Adversaries? • The First Adversary – Responsible for injecting noise in the communication channel • The ‘Other’ Adversary – The Cryptographic Eavesdropper • Responsible for listening/reading critical information from channel/nodes Revisiting Secure Communication • Shannon’s Result: Information-theoretically Secure Communication is Impossible in a Noiseless Insecure Channel • Information-theoretically Secure Communication is possible in an appropriately Noisy Insecure Channel adversary Is it noisy? Sender Insecure channel Receiver Another Fundamental Problem Oblivious Transfer Can A learn only the bit bi without revealing ‘i’ to B? A Index i B Bit-Array: b0,b1,…bn • Information-theoretically Secure Oblivious Transfer is Impossible in a Noiseless Channel • Information-theoretically Secure Oblivious Transfer is possible in an appropriately Noisy Insecure Channel Yet Another Fundamental Problem Securely Computing AND • Securely Computing x y in GF(2) A Input: x B Input: y For simplicity assume the following channel noise: Any 1 bit out of every block of 4 bits sent will be toggled Fact: Perfectly Secure AND is impossible in a noiseless channel Protocol for Secure AND • A chooses four random bits, r0,r1,r2,r3 and sends them to B, who receives s0,s1,s2,s3 – One of the ri is different from si – Three of the others are equal • A and B compute the following 3-tuples respectively 0 0 0 M= 0 1 0 1 0 0 1 1 1 • A (respectively B) multiplies the ith row of matrix M with ri (respectively si) to obtain a matrix MA (resp. MB) • A (resp. B) adds up the resultant 4 by 3 matrix MA (resp. MB) column-wise to obtain a 3-tuple TA = (a0, b0, c0) (resp. TB = (a1,b1,c1)) Protocol for Secure AND (Contd.) • Let x = x0 x1 and y = y0 y1 • A sends x1 to B and retains x0 • B sends y0 to A and retains y1 Now, • A has: x0, y0, a0, b0 and c0 • B has: x1, y1, a1, b1 and c1 Protocol for Secure AND (Contd.) • A publishes (x0a0) and (y0b0) • B publishes (x1a1) and (y1b1) • Both of them compute the bits P and Q: P = (x0a0) (x1a1) Q = (y0b0) (y1b1) • A computes the bit z0 as follows: z0 = (b0 P) (a0 Q) (P Q) c0 • Similarly B computes z1 as: z1 = (b1 P) (a1 Q) (P Q) c1 It can be showed that (z0 z1) = (x y) Securely Computing Any Function in GF(2) • Express the function by a Boolean circuit using only AND and XOR gates (fan-in 2 and fan-out 1) • Protocol for Secure AND securely transforms two ‘shared’ inputs (x and y) to a ‘shared’ output (z) of a single AND gate • Protocol for secure XOR is simple: just locally XOR the input shares • Any circuit can thus be securely evaluated gate-by-gate till the output wire is reached; the output shares can be XORed to obtain f(x,y) Protocol for Oblivious Transfer Can A learn only the bit bi without revealing ‘i’ to B? B A Index i Bit-Array: b0,b1,…bn For n=2: We may securely compute ((i1)b0) (i b1) Protocol for Secure Communication adversary Sender Insecure channel Receiver • To securely send a bit m, the receiver chooses uniformly at random a permutation of [0,1] and executes an Oblivious Transfer of the mth index bit to the Sender. • Upon receipt of the obliviously transferred bit, the Sender reliably sends that bit to the receiver who recovers m from it Conclusions Modern cryptography – Based on complexity theory’s currently unproven hardness assumptions – Contemporary mathematicians suggest that these assumptions are (a) likely to be true and (b) unlikely to be proven in the near future – Very fast and scalable once a secret-key is established (symmetric-key cryptography) Distributed Algorithmic Solution – Based on adversary’s inability to simultaneously corrupt several routers – Necessitates highly connected networking – Can tolerate active adversaries too Quantum Mechanical Solution – Based on the postulates of quantum mechanics – Currently secure transmission is achieved to about 100km – Is physically unbreakable, however several side-channel attacks are plausible Noisy Channel Solution – It assumes that natural noise is not under the cryptographic adversary’s control – It is an intriguing recycling of noise in to productive use – Noise is ubiquitous Thank You