Cryptarithms: Solve Mathematical Puzzles with Digits and Letters
Cryptarithms are mathematical puzzles where digits in sums are replaced by letters. Can you find unique digit solutions for these puzzles? Explore the challenge of maximizing the sum using digits 1 to 9 exactly once. Visit the provided link for answers and more engaging puzzles from NRICH.
Uploaded on Mar 01, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Fine Grained Hardness in Cryptography Omer Reingold SRA
Fine Grained? Really?!? Our understanding of Computational Hardness is quite coarse. Are we ready for this discussion? Proof of work moderately hard puzzles (with concrete bounds) Gradually increasing hardness? The case of block ciphers (Rackoff s thesis).
Very Hard Puzzles N = P Q 1k P,Q Generating a puzzle and verifying a solution in time k Solving the puzzle is infeasible Cannot be done in any poly(k) time May hope for it to be much harder aka One-Way Functions, beautiful theory
Spam Fighting [Dwork-Naor 93] Send you an email? 1k Sure but this first: Solving the puzzle is feasible but moderately hard Need pretty good bounds Shouldn t be possible to amortize Various natural candidates May be non-interactive
Beyond Spam Protection? Other applications (Denial of Service, Timed Commitments, Digital Currancy, ) Can the solved puzzles be combined to address a problem we really want to solve? (analogy: reCAPTCHA digitizing books) Is there a rich theory to uncover?
Hardness Reduction R < R R-secure R -secure Consider factoring for instance: Born very hard and only weakened by crypto
Gradually Increasing Hardness? plaintext Block ciphers: key P ciphertext For any fixed key, P(key,*) is a permutation For a random key, P(key,*) indistinguishable from uniform permutation Usually constructed as a composition of very weak (completely insecure) permutations
Rackoffs Thesis [1995 or earlier] For any sufficiently expressive family F F of permutations, composing polynomial number of random elements of F F gives a secure block cipher Initial result: Simple Permutations Mix Well [Gowers 1996, Hoory-Magen-Myers-Rackoff 2004, ] What about pseudorandom permutations? Reduce one family F F to another? Understanding how hardness evolve in other context? [HMMR04] For simple permutations, obtaining 4- wise independence -> pseudorandomness?
