Secret sharing using Lagrange interpolation polynomial
Learn about secret sharing using Lagrange interpolation polynomial in the context of innovative teaching and education in mathematics. Discover how this concept is applied and explore its significance in mathematical education. Visit the mentioned website for more information.
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
Secret sharing using Lagrange interpolation polynomial iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
Secret sharing Suppose that 1234 is the code to the safe of a bank. For safety reason, the rule is that the safe cannot be open by a single person, but by two together. iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
Secret sharing: first solution As a first solution, we split the code into two parts 12 and 34 and give one part to clerk A and the second to clerk B. Problem: each clerk has only two digits to guess for the secret code, making it easer for them to find the secret. iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
Secret sharing: a better solution We hide the secret in the equation of a line of the form: y=1234+ax where a is any nonzero number, for example y=1234-50 x. Now we give to each clerk a point on the line: (10,734) to clerk A and (20,234) to clerk B. iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
The secret is kept in the y- intercept of the line. The two points given to the clerks define the line uniquely. So together they can find the equation of the secret. iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
The equation of the line through (10,734) and (20,234) is: 234 734 20 10 500 10 = + = = 734 ( 10) 734 ( 10) 1234 50 y x y x y x iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
Safety If clerk A wants to guess the secret code. Does it help that he knows a point on the line? No! There are infinitely many lines passing through one point. In fact for each secret M there is a line going through (0,M) and the point (10,734) of clerk A. So any secret code is possible. iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
Another advantage of this solution What happens if one of the clerks A or B is on vacation? It is not a problem! We can give points on the line to other clerks. Any two of them can find the secret code using their two points. iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
Generalization What happens if the rule says that only 4 clerks together can open the safe? Hiding the secret code in a line will not work because two points are enough to find the line. It will use the fact that four points (with different x s) define a unique = + + + 2 3 y a a x a x a x polynomial of degree 3: 0 1 2 3 iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
Generalization We hide the secret code as the constant term of a = + + + 2 3 1234 y a x a x a x polynomial of degree 3 : 1 2 3 = + + 2 3 23 1 4 7 2 0 y x x x For example iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
Secret sharing using the polynomial Each clerk is given a point on the graph of the polynomial. Any four points define the polynomial. iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
Find the secret How is it possible to find the polynomial using 4 points? Using the Lagrange s interpolation formula which we will learn about in the course! iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
This method for secret sharing is a well known cryptographic protocol due to Adi Shamir (Weizman Institute). In ryptography, the polynomial if defined with coefficient in where p is a prime p number. Shamir, Adi (1979), "How to share a secret", Communications of the ACM, 22 (11): 612 613 iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
"The European Commission support for the production of this publication does not constitute an endorsement of the contents which reflects the views only of the authors, and the Commission cannot be held responsible for any use which may be made of the information contained therein." iTEM: Innovative Teaching Education in Mathematics https://item.chania.teicrete.gr/ https://item.chania.teicrete.gr/
