Recent And Future Trends In Cryptography - University Of Chicago
Recent and Future Trendsin CryptographyCMSC 23200/33250, Winter 2021, Lecture 23David Cash and Blase UrUniversity of Chicago
A Sampling of Recent and Future Trends in Crypto1. End-to-End Messaging2. Snowden Revelations3. Homomorphic Encryption ( Post Quantum)4. Zero-Knowledge Proofs Password-Authenticated Key Exchange5. ORAM (Alex)
A Sampling of Recent and Future Trends in Crypto1. End-to-End Messaging2. Snowden Revelations3. Homomorphic Encryption ( Post Quantum)4. Zero-Knowledge Proofs Password-Authenticated Key Exchange5. ORAM (Alex)
Traditional Diffie-Hellman Deployment (e.g. TLS)X’XYKFacebookY’K’
End-to-End Diffie-HellmanXFacebookYK
Why End-to-End?KKKKFacebookKKKKKKKK
Why not End-to-End?KKKKFacebookKKKKKKKK
Why not End-to-End?KKKKFacebookKKKKKKKK
A Sampling of Recent and Future Trends in Crypto1. End-to-End Messaging2. Snowden Revelations3. Homomorphic Encryption ( Post Quantum)4. Zero-Knowledge Proofs Password-Authenticated Key Exchange5. ORAM (Alex)
The Snowden Revelations
2013 Snowden Revelations Included:1. Collected millions of images from Yahoo! messenger tobuild facial recognition system (2008-2010)2. Recorded audio of every call in the Bahamas (2009-?)3. Tapped internal lines for Google and Yahoo! data centers4. Likely built a crypto backdoor into a NIST algorithm, thenpaid a company 10 million to use that algorithm
Dual EC DRBG: A Pseudorandom GeneratorPseudorandom generator: Algorithm for “stretching” a random string.
From: John Kelsey [mailto:john.kelsey@nist.gov]Sent: Wednesday, October 27, 2004 11:17 AMTo: Don JohnsonSubject: Minding our Ps and Qs in Dual ECDo you know where Q comes from in Dual EC DRBG?Thanks,-John
Subject: RE: Minding our Ps and Qs in Dual ECFrom: "Don Johnson"Date: Wed, October 27, 2004 11:42 amTo: "John Kelsey"John,P G.Q is (in essence) the public key for somerandom private key.It could also be generated like a(nother)canonical G, but NSA kyboshed this idea, and Iwas not allowed to publicly discuss it, just incase you may think of going there.Don B. Johnson
Dual EC DRBG Development Process*We need a good number!Q 2q mod pQBroke usingknowledgeof qQpublisheddeployedQ*Actual math is over elliptic curves, and attack is complicated!
A Sampling of Recent and Future Trends in Crypto1. End-to-End Messaging2. Snowden Revelations3. Homomorphic Encryption ( Post Quantum)4. Zero-Knowledge Proofs Password-Authenticated Key Exchange5. ORAM (Alex)
Malleable EncryptionC Enc(PK,M)CC’Dec(SK,C’mod N) M*xC’ [(xe)*C mod N]- Malleability is usually a bad thing for Plain RSA Enc/Signatures- Allows adversaries to predictably change plaintexts withoutpermission, and without even knowing the original message
Homomorphic Encryption Very Malleable EncryptionDoes not have SK,cannot decrypt!- A bug becomes a feature!PK,φC Enc(PK,M)CHomomorphicEvaluationC’Dec(SK,C’) φ(M)- RSA is homomorphic for multiplication by some fixed x:φx(M) (x*M mod N)- RSA does not appear to homomorphic for addition by some fixed x:φx(M) (x M mod N)?
Homomorphic Encryption Very Malleable EncryptionDoes not have SK,cannot decrypt!- A bug becomes a feature!PK,φC Enc(PK,M)C- Multiple-ciphertext version:C1 Enc(PK,M1)C1, ,Cn Cn Enc(PK,Mn)HomomorphicEvaluationC’Dec(SK,C’) φ(M)PK,φHomomorphicEvaluationC’Dec(SK,C’) φ(M1, ,Mn)
Homomorphic Encryption: The Grand Vision (1978)
Homomorphic Encryption: The Grand Vision (1978)- Suppose Enc is homomorphic for φ using HomEvalThanks!PK,C1, ,CnφC’Ci Enc(PK,Mi)C’ HomEval(PK,φ,C1, ,Cn)φ(M1, ,Mn) Dec(SK,C’)- Client learns φ applied to its own data M1, ,Mn- Client does not learn φ- Server does not learn M1, ,Mn
Homomorphic Encryption: The Grand Vision (1978)- Suppose Enc is homomorphic for φ using HomEvalThanks!PK,C1, ,CnφC’Ci Enc(PK,Mi)C’ HomEval(PK,φ,C1, ,Cn)φ(M1, ,Mn) Dec(SK,C’)- Train private machine-learning models- Run expensive simulations- Client learns φ applied to its own data M1, ,Mn- Query databases without decrypting- Client does not learn φ- Server does not learn M1, ,Mn
For which φ can we build homomorphic encryption?- RSA (’78): φ multiplication mod N of plaintexts and/or constants- Paillier (’99): φ addition mod N of plaintexts and/or constants- Observation: If an encryption is homomorphic for both additionsand multiplications mod N, then it is homomorphic for any φ!- BGN (’06): φ many additions but only one multiplication- - Gentry (’09): Any φ! Via new techniques.
Homomorphic Encryption and Lattices (Gentry’09)- Based on different math (not RSA/Diffie-Hellman)- Uses lattices, i.e. high-dimension integer grids- Original construction was too slow- Tons of research on making it faster
Underlying Hard Problem: Shortest Vector ProblemInput: An n-by-m integer matrix B (m n)Output: The smallest non-zero y such that Bx y for some integer x.- Easy for small n- Appears hard for large n - Even for quantum computers!
A Sampling of Recent and Future Trends in Crypto1. End-to-End Messaging2. Snowden Revelations3. Homomorphic Encryption ( Post Quantum)4. Zero-Knowledge Proofs Password-Authenticated KeyExchange5. ORAM (Alex)
Switching gears: Mathematical ProofsFermat’s lasttheorem is true!No way!Prove it! 100 page proof - Convinced theorem is true- Learns why it’s true (i.e. because allsemi-stable curves are modular )This graph G has aHamiltonian cycle!No way!Prove it!Hey, that’s private Question: Can one prove something is true without revealing anything about why?
Zero-Knowledge Proofs (Goldwasser,Micali,Rackoff’85)- Prover claims: There is a one-way door that opens between A and B- Wants to hide: Which direction the door opens (A B vs B A)
Protocol:1. Prover walks into cave withoutVerifier watching2. Verifier flips a coin and asksProver to come out A or B side3. Prove comes out that side, usingdoor if necessary4. Repeat 100 times. If prover is evercaught lying, REJECT.Soundness: If there is (in fact) no door, then Proveronly has 1/2100 chance to cheat.- Key insights:- InteractionZero-knowledge: Even if Verifier tries to cheat, it won’tlearn anything about which way the door opens.- Randomness
Application: Password-Authenticated Key Exchange
Application: Password-Authenticated Key ExchangeXYFacebookhpwpwI know a passwordcorresponding to thaty,rKH(pw) h?- Hash stored at FB.- Compromise at serverallows stealing pw,even if very strongXYFacebooky,rpwKCheckproof!- pw never sent to FB,even at registration- Compromise at serverwon’t allow stealing pw(assuming it is strong)What are the downsides, if any?
A Sampling of Recent and Future Trends in Crypto1. End-to-End Messaging2. Snowden Revelations3. Homomorphic Encryption ( Post Quantum)4. Zero-Knowledge Proofs Password-Authenticated Key Exchange5. ORAM (Alex)
The End
Recent and Future Trends in Cryptography CMSC 23200/33250, Winter 2021, Lecture 23 University of Chicago. A Sampling of Recent and Future Trends in Crypto 1. End-to-End Messaging 2. Snowden Revelations 3. Homomorphic Encryption ( Post Quantum) 4. Zero-Knowledge Proofs Password-Authenticated Key Exchange 5. ORAM (Alex)
long trends. Trends shaping the future of work Earlier Deloitte research identified seven disruptive trends that are shaping the future of work (see Figure 1). these trends can be grouped into two categories: socio-demographic trends and enabling technology trends. For example, the diversity of the workforce is increasing as we live longer and
project a continuation of recent trends (1990-2010) in forest loss across six New England states from 2010 to 2060. Recent trends were estimated using a continuous change detec-tion algorithm applied to twenty years of Landsat images. We addressed three questions: (1) What would be the consequences of a continuation of the recent trends in .
Trends in Care Delivery and Community Health State Public Health Leadership Webinar Deloitte Consulting LLP June 20, 2013. . Current state of Accountable Care Organizations (ACOs) and trends. Current state of Patient-Centered Medical Homes (PCMHs) and trends. Introduction.File Size: 2MBPage Count: 38Explore further2020 Healthcare Trends and How to Preparewww.healthcatalyst.comFive Health Care Trends For 2020 Health Affairswww.healthaffairs.orgTop 10 Emerging Trends in Health Care for 2021: The New .trustees.aha.orgRecommended to you b
Data Center Trends And Design. Data Center Trends & Design Agenda IT Trends Cooling Design Trends Power Design Trends. IT Trends Virtualization . increasing overall electrical efficiency by 2%. Reduces HVAC requirements by 6 tons/MW. Reduces the amount of equipment needed to support the load,
1 QUARTERLY CONSUMER CREDIT TRENDS: RECENT TRENDS IN DEBT SETTLEMENT & CREDIT COUNSELING This is part of a series of quarterly reports on consumer credit trends produced by the Consumer Financial Protection Bureau using a longitudinal, nationally representative sample of
recent trends and the role of the WTO The World Trade Report 2014 looks at how many developing economies are successfully leveraging trade for rapid growth. It focuses on four recent trade trends - the rise of new global players, the spread of production chains, increasing commodity prices, and growing economic interdependence. These trends
Defining "recent" trends We used the most recent 3-6 years of available data for each indicator to calculate the recent trend. In many cases, the time periods for various indicators do not overlap. The available data from all of the monitoring made it difficult to select a single time period as the definition of recent. For example,
Introduction to Magnetic Fields 8.1 Introduction We have seen that a charged object produces an electric field E G at all points in space. In a similar manner, a bar magnet is a source of a magnetic field B G. This can be readily demonstrated by moving a compass near the magnet. The compass needle will line up
