Adi Shamir
Encyclopedia
Adi Shamir is an Israel
i cryptographer
. He is a co-inventor of the RSA algorithm (along with Ron Rivest
and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identification scheme (along with Uriel Feige
and Amos Fiat), one of the inventors of differential cryptanalysis
and has made numerous contributions to the fields of cryptography
and computer science
.
, Shamir received a BS
degree in Mathematics
from Tel Aviv University
in 1973 and obtained his MSc
and PhD
degrees in Computer Science
from the Weizmann Institute in 1975 and 1977 respectively. His thesis was titled, "Fixed Points of Recursive Programs and their Relation in Differential Agard Calculus". After a year postdoc at University of Warwick
, he did research at MIT
from 1977–1980 before returning to be a member of the faculty of Mathematics
and Computer Science
at the Weizmann Institute. Starting from 2006, he is also an invited professor at École Normale Supérieure
in Paris.
scheme, the breaking of the Merkle-Hellman knapsack cryptosystem, visual cryptography
, and the TWIRL
and TWINKLE
factoring
devices. Together with Eli Biham
, he discovered differential cryptanalysis
, a general method for attacking block cipher
s. (It later emerged that differential cryptanalysis was already known — and kept a secret — by both IBM
and the NSA.)
Shamir has also made contributions to computer science outside of cryptography, such as finding the first linear time algorithm for 2-satisfiability
and showing the equivalence of the complexity classes
PSPACE
and IP
.
Israel
The State of Israel is a parliamentary republic located in the Middle East, along the eastern shore of the Mediterranean Sea...
i cryptographer
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. He is a co-inventor of the RSA algorithm (along with Ron Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identification scheme (along with Uriel Feige
Uriel Feige
Uriel Feige is an Israeli computer scientist who was a doctoral student of Adi Shamir. He is notable for co-inventing the Feige–Fiat–Shamir identification scheme along with Amos Fiat and Adi Shamir...
and Amos Fiat), one of the inventors of differential cryptanalysis
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
and has made numerous contributions to the fields of cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
.
Education
Born in Tel AvivTel Aviv
Tel Aviv , officially Tel Aviv-Yafo , is the second most populous city in Israel, with a population of 404,400 on a land area of . The city is located on the Israeli Mediterranean coastline in west-central Israel. It is the largest and most populous city in the metropolitan area of Gush Dan, with...
, Shamir received a BS
Bachelor of Science
A Bachelor of Science is an undergraduate academic degree awarded for completed courses that generally last three to five years .-Australia:In Australia, the BSc is a 3 year degree, offered from 1st year on...
degree in Mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
from Tel Aviv University
Tel Aviv University
Tel Aviv University is a public university located in Ramat Aviv, Tel Aviv, Israel. With nearly 30,000 students, TAU is Israel's largest university.-History:...
in 1973 and obtained his MSc
Master of Science
A Master of Science is a postgraduate academic master's degree awarded by universities in many countries. The degree is typically studied for in the sciences including the social sciences.-Brazil, Argentina and Uruguay:...
and PhD
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
degrees in Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
from the Weizmann Institute in 1975 and 1977 respectively. His thesis was titled, "Fixed Points of Recursive Programs and their Relation in Differential Agard Calculus". After a year postdoc at University of Warwick
University of Warwick
The University of Warwick is a public research university located in Coventry, United Kingdom...
, he did research at MIT
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
from 1977–1980 before returning to be a member of the faculty of Mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at the Weizmann Institute. Starting from 2006, he is also an invited professor at École Normale Supérieure
École Normale Supérieure
The École normale supérieure is one of the most prestigious French grandes écoles...
in Paris.
Research
In addition to RSA, Shamir's other numerous inventions and contributions to cryptography include the Shamir secret sharingShamir's Secret Sharing
Shamir's Secret Sharing is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret....
scheme, the breaking of the Merkle-Hellman knapsack cryptosystem, visual cryptography
Visual cryptography
Visual cryptography is a cryptographic technique which allows visual information to be encrypted in such a way that the decryption can be performed by the human visual system, without the aid of computers....
, and the TWIRL
TWIRL
In cryptography and number theory, TWIRL is a hypothetical hardware device designed to speed up the sieving step of the general number field sieve integer factorization algorithm. During the sieving step, the algorithm searches for numbers with a certain mathematical relationship...
and TWINKLE
TWINKLE
TWINKLE is a hypothetical integer factorization device described in 1999 by Adi Shamir and purported to be capable of factoring 512-bit integers. The name is an acronym of "The Weizmann Institute Key Locating Engine"...
factoring
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
devices. Together with Eli Biham
Eli Biham
Eli Biham is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion Israeli Institute of Technology Computer Science department. Starting from October 2008, Biham is the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate...
, he discovered differential cryptanalysis
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
, a general method for attacking block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s. (It later emerged that differential cryptanalysis was already known — and kept a secret — by both IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
and the NSA.)
Shamir has also made contributions to computer science outside of cryptography, such as finding the first linear time algorithm for 2-satisfiability
2-satisfiability
In computer science, 2-satisfiability is the problem of determining whether a collection of two-valued variables with constraints on pairs of variables can be assigned values satisfying all the constraints...
and showing the equivalence of the complexity classes
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
and IP
IP (complexity)
In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985...
.
Awards
Shamir has received a number of awards, including the following:- the 2002 ACMAssociation for Computing MachineryThe Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
Turing AwardTuring AwardThe Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
, together with Rivest and AdlemanLeonard AdlemanLeonard Max Adleman is an American theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. He is known for being a co-inventor of the RSA cryptosystem in 1977, and of DNA computing...
, in recognition of his contributions to cryptography - the Paris Kanellakis Theory and Practice Award;
- the Erdős PrizeErdős Prize- References :*...
of the Israel Mathematical Society, - the 1986 IEEE W.R.G. Baker Award
- the UAP Scientific Prize;
- The Vatican's PIUS XI Gold Medal;
- the 2000 IEEE Koji Kobayashi Computers and Communications AwardIEEE Koji Kobayashi Computers and Communications AwardThe IEEE Koji Kobayashi Computers and Communications Award is a Technical Field Award of the IEEE established in 1986. This award has been presented annually since 1988 for outstanding contributions to the integration of computers and communications....
- the Israel PrizeIsrael PrizeThe Israel Prize is an award handed out by the State of Israel and is largely regarded as the state's highest honor. It is presented annually, on Israeli Independence Day, in a state ceremony in Jerusalem, in the presence of the President, the Prime Minister, the Knesset chairperson, and the...
, in 2008, for computer sciences. - an honorary DMath (Doctor of Mathematics) degree from the University of WaterlooUniversity of WaterlooThe University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
See also
- Important publications in cryptography
- List of Israel Prize recipients
- NDS GroupNDS GroupNDS Group Plc. is a developer of pay TV technology. NDS was established in 1988 as an Israeli start up company. It was acquired by News Corporation in 1992. The company is currently headquartered in Staines, United Kingdom...