What can Quantum Cryptographers Learn from History.ppt
《What can Quantum Cryptographers Learn from History.ppt》由会员分享,可在线阅读,更多相关《What can Quantum Cryptographers Learn from History.ppt(60页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、What can Quantum Cryptographers Learn from History?Kenny PatersonInformation Security GroupRoyal Holloway,University of LondonOctober 4th 200610.PrefaceAccording to MIT Technology Review,in 2003,QC was one of:“10 Emerging Technologies That Will Change the World.According to Dr.Burt Kaliski,chief sci
2、entist at RSA Security(and now a member of MagiQs Scientific Advisory Board):“If there are things that you want to keep protected for another 10 to 30 years,you need quantum cryptography.October 4th 20062Quantum CryptographyQC offers unconditional security.Security based only on the correctness of t
3、he laws of quantum physics.Often contrasted with security offered by public key cryptography.Vulnerable to quantum computers.Vulnerable to algorithmic advances in factoring,discrete logs,etc.October 4th 20063Quantum CryptographyQC is often promoted as the alternative to public key cryptography for t
4、he future.For example:“Quantum cryptography offers the only protection against quantum computing,and all future networks will undoubtedly combine both through the air and fibre-optic technologies Dr.Brian Lowans,Quantum and Micro Photonics Team Leader,QinetiQ.October 4th 20064Quantum CryptographyAno
5、ther example:“All cryptographic schemes used currently on the Internet would be broken.Prof.Giles Brassard,Quantum Works launch meeting,University of Waterloo,27th September 2006.October 4th 20065This TalkThe road-side of cryptography is littered with the abandoned wrecks of systems that turned out
6、to be insecure in practice(even when secure in theory).What lessons can the quantum cryptography community learn from this history?October 4th 20066Learning from History“Those who cannot learn from history are doomed to repeat it.George Santayana,Reason in Common Sense,The Life of Reason,Vol.1.“You
7、must learn from the mistakes of others.You cant possibly live long enough to make them all yourself.Sam LevensonOctober 4th 20067Overview1.Security proofs and their limitations2.Theory and practice in cryptography3.Side-channel analysis4.Key management5.The need for dialogue6.Why does this matter to
8、 quantum researchers?7.Closing remarksOctober 4th 200681.Security Proofs and Their LimitationsSecurity proofs can be very valuable in assessing the security offered by cryptographic schemes.Typical approach in the provable security paradigm:Define(generically)the functionality of the scheme.Define t
9、he capabilities of an adversary in terms of a game with a challenger.Propose a concrete scheme.Provide a proof that any adversary against the scheme can be transformed into an algorithm to break some computational problem.Transformation via undetectable simulation of the challenger.October 4th 20069
10、Provable SecurityAssume that the computational problem is well-studied and as hard as we believe it to be.Then,applying the contra-positive:no adversary can exist.A refinement:Relate the adversarys advantage and running time(Adv,t)to the success probability and running time(p,t)of an algorithm to so
11、lve the underlying computational problem.Concrete security analysis.October 4th 200610LimitationsThis approach has its limitations:The proof of security may not be correct.The reduction from the adversary to the computational problem may not be“tight,so the proof of doubtful meaning in practice.(The
12、 model of security may not be comprehensive enough to take into account all practical attacks.)(The security proof may not compose well with further protocols to produce a secure system.)The two following examples come from a series of studies by Koblitz and Menezes.October 4th 200611Example 1:RSA-O
13、AEPRSA-OAEP:RSA=RSA!OAEP=Optimal Asymmetric Encryption PaddingA method for transforming“raw RSA encryption into a method offering suitably strong security guarantees.Solving a long-standing open problem.Proposed and proved secure by Bellare and Rogaway(1994).Widely standardised(e.g.in SET).October 4
14、th 200612Example 1:RSA-OAEPmrs=(m|0)+G(r)t=r+H(s)s0txe modulo NxPaddingEncryptionOctober 4th 200613Example 1:RSA-OAEPBellare and Rogaway(1994)proved that an adversary who can break RSA-OAEP(in a well-defined and strong sense)can solve the RSA-inversion problem.Proof actually works for any trapdoor o
15、ne-way function.The proof was well-written,the construction simple and the result was rightly celebrated.October 4th 200614Example 1:RSA-OAEPBut Shoup(2001)discovered a flaw in Bellare and Rogaways proof.The proof was in the literature for seven years before the problem was spotted.Fortunately,Shoup
16、 and Fujiskai et al.were able to repair the proof.Simpler constructions and tighter proofs were subsequently discovered.Proofs are not static objects.October 4th 200615Example 2:Blum-Blum-ShubBlum-Blum-Shub pseudo-random bit generator:N=pq is an RSA modulus with p,q=3 mod 4.Initial seed x_0 xi=(xi-1
17、)2 mod NOutput the j least significant bits of xiThe larger j is,the faster we can generate bits.Security result:assuming factoring N is intractable,j=O(loglogN)bits can be securely extracted per iteration.Vazirani and Vazirani;Alexi,Chor,Goldreich and Schnorr;Fischlin and Schnorr;Sidorenko and Scho
18、enmakers.October 4th 200616Example 2:Blum-Blum-ShubIETF RFC 1750(Eastlake et al.)states:“If you use no more than the log2log2(xi)low order bits,then predicting any additional bits from a sequence generated in this manner is provable sic as hard as factoring N.Is this statement justified by the secur
19、ity proof?October 4th 200617Example 2:Blum-Blum-ShubAnalysis by Koblitz and Menezes:Take the best bounds on security and hardness of factoring known in the literature.Apply them for j=9 and N with 768 bits,extracting M=109 bits from the generator.Allowing a success probability of 0.01 for the advers
20、ary,what is the time bound on the adversary?Answer:2-264Yes,that is a negative sign in the exponent!Concrete security analysis does not always give us results that are useful in practice.October 4th 200618Lessons for Quantum CryptographyWe also model adversarial capabilities and provide mathematical
21、 proofs for quantum protocols.Those models and proofs evolve too.For example,initial proofs of security for QKD only considered limited attack scenarios and perfect devices.Early proposal for quantum bit commitment?What value does a claim of unconditional security have in this evolving context?Octob
22、er 4th 200619Lessons for Quantum Cryptography“If its provably secure,its probably notLars KnudsenOctober 4th 2006202.Theory and PracticeA show of hands please:Question:Does using the one-time pad to encrypt provide confidentiality?Answer:Of course it does!Shannon told us that!October 4th 2006212.The
23、ory and PracticeA show of hands please:Question:Does using the one-time pad to encrypt provide confidentiality?A better answer:It depends on the adversarys capabilities and on the system characteristics.October 4th 200622IPsecIPsec:a suite of protocols for providing security to IP packets.Widely use
24、d in Virtual Private Networking systems.Also used today in some quantum cryptographic products.Standardised by IETF in:RFCs 2401-2411(second generation)RFCs 4301-4309(third generation)More than 200 pages of documentation.October 4th 200623Encryption in IPsecESP=Encapsulating Security Protocol.IPsecs
25、 protocol for providing confidentiality.Defined in RFCs 2406 and 4303.Encrypts and optionally integrity-protects IP packets.Typically using CBC-mode of a block cipher such as AES or DES for encryption.HMAC-SHA-1 or HMAC-MD5 for integrity protection.October 4th 200624Theory and PracticeIt is very wel
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- What can Quantum Cryptographers Learn from History
链接地址:https://www.deliwenku.com/p-75985067.html
限制150内