Notes On Shamir’s Secret Sharing Scheme

Lagrange Interpolation Within Shamir’s Secret Sharing Scheme

dù hǔ fú (杜虎符) unearthed at Shanmenkou, Nanjiao, Xi’an (西安南郊山). The tiger talisman is a metal tiger-shaped military mobilization certificate originating from China, and later spread to Korea and Vietnam. Legend has it that it was invented by Jiang Ziya in the Western Zhou Dynasty, and it was a symbol of military power in the ancient Chinese imperial system. The tiger talisman was issued by the central government to the general in charge of the army. There was an inscription on the back of the tiger talisman, which was divided into two halves. The right half was kept in the court, and the left half was issued to the general or local governor. When mobilizing troops, the two halves needed to be matched with the inscription to take effect. The tiger talisman was used for a specific purpose, and each army had a corresponding tiger talisman. The idiom “stealing the talisman to save Zhao” (窃符救赵, qiè fú jiù zhào) refers to stealing tiger talisman to hijack authority to save a situation.

Civilizations have relied on methods to protect sensitive information and ensure the proper delegation of authority. One such example is the tiger talisman (虎符, hǔ fú) from ancient China, a military mobilization certificate divided into two halves. The central government kept one half, while the other was issued to a general. Troop mobilization required matching the two halves, ensuring the integrity and authenticity of commands.

This concept of dividing authority to safeguard critical assets echoes in modern cryptographic techniques like Shamir’s Secret Sharing Scheme (SSSS). Just as the tiger talisman safeguarded military power, Shamir’s scheme protects sensitive information, such as encryption keys, by splitting it into multiple pieces. Only when a predefined number of these pieces are combined can the original secret be reconstructed.

SSSS ensures secure distribution of a secret among multiple participants such that a subset of them can recover it, but less than the required number cannot gain any information about the secret.

Mechanics of Shamir’s Secret Sharing

From Polynomials to Privacy