Amos Fiat

Fiat earned his Ph.D. in 1987 from the Weizmann Institute of Science under the supervision of Adi Shamir.{{mathgenealogy|id=19320}} After postdoctoral studies with Richard Karp and Manuel Blum at the University of California, Berkeley, he returned to Israel, taking a faculty position at Tel Aviv University.

Many of Fiat's most highly cited publications concern cryptography, including his work with Adi Shamir on digital signatures (leading to the Fiat–Shamir heuristic for turning interactive identification protocols into signature schemes){{citation

| last1 = Fiat | first1 = Amos

| last2 = Shamir | first2 = Adi | author2-link = Adi Shamir

| contribution = How to prove yourself: practical solutions to identification and signature problems

| doi = 10.1007/3-540-47721-7_12

| location = London, UK

| pages = 186–194

| publisher = Springer-Verlag

| series = Lecture Notes in Computer Science

| title = Advances in Cryptology — CRYPTO' 86

| volume = 263

| year = 1987| isbn = 978-3-540-18047-0

| doi-access = free

}}. and his work with David Chaum and Moni Naor on electronic money, used as the basis for the ecash system.{{citation

| last1 = Chaum | first1 = D.

| last2 = Fiat | first2 = A.

| last3 = Naor | first3 = M.

| contribution = Untraceable electronic cash

| location = London, UK

| pages = 319–327

| publisher = Springer-Verlag

| series = Lecture Notes in Computer Science

| title = Proceedings on Advances in Cryptology – CRYPTO '88

| volume = 403

| year = 1990}}. With Shamir and Uriel Feige in 1988, Fiat invented the Feige–Fiat–Shamir identification scheme, a method for using public-key cryptography to provide challenge–response authentication.

In 1994, he was one of the first, with Moni Naor, to formally study the problem of practical broadcast encryption.{{cite book|author1=Amos Fiat|author2=Moni Naor|chapter=Broadcast Encryption |year=1994|chapter-url=http://www.wisdom.weizmann.ac.il/~naor/PAPERS/broad_abs.html|title=Advances in Cryptology – CRYPTO '93|type=Extended abstract|series=Lecture Notes in Computer Science|volume=773|pages=480–491|doi=10.1007/3-540-48329-2_40|isbn=978-3-540-57766-9|doi-access=free}} Along with Benny Chor, Moni Naor and Benny Pinkas, he made a contribution to the development of Traitor tracing, a copyright infringement detection system which works by tracing the source of leaked files rather than by direct copy protection.{{cite journal|last=Naor|first=Moni|author2=Benny Chor|author2-link= Benny Chor |author3=Amos Fiat|author4=Benny Pinkas|date=May 2000|title=Tracing Traitors|journal=Information Theory|volume=46|issue=3|pages=893–910|doi=10.1109/18.841169|s2cid=11699689 }}

With Gerhard Woeginger, Fiat organized a series of Dagstuhl workshops on competitive analysis of online algorithms, and together with Woeginger he edited the book Online Algorithms: The State of the Art (Lecture Notes in Computer Science 1442, Springer-Verlag, 1998). His research papers include methods for applying competitive analysis to paging,{{citation

| last1 = Fiat | first1 = Amos

| last2 = Karp | first2 = Richard M. | author2-link = Richard Karp

| last3 = Luby | first3 = Michael | author3-link = Michael Luby

| last4 = McGeoch | first4 = Lyle A.

| last5 = Sleator | first5 = Daniel D. | author5-link = Daniel Sleator

| last6 = Young | first6 = Neal E.

| arxiv = cs.DS/0205038

| doi = 10.1016/0196-6774(91)90041-V

| issue = 4

| journal = Journal of Algorithms

| pages = 685–699

| title = Competitive paging algorithms

| volume = 12

| year = 1991| s2cid = 3260905

}}. call control,{{citation

| last1 = Awerbuch | first1 = Baruch | author1-link = Baruch Awerbuch

| last2 = Bartal | first2 = Yair

| last3 = Fiat | first3 = Amos

| last4 = Rosén | first4 = Adi

| contribution = Competitive non-preemptive call control

| pages = 312–320

| title = Proceedings of the Fifth ACM-SIAM Symposium on Discrete Algorithms (SODA '94)

| url = http://dl.acm.org/citation.cfm?id=314464.314510

| year = 1994| isbn = 9780898713299 }}. data management,{{citation

| last1 = Bartal | first1 = Yair

| last2 = Fiat | first2 = Amos

| last3 = Rabani | first3 = Yuval

| doi = 10.1006/jcss.1995.1073

| issue = 3

| journal = Journal of Computer and System Sciences

| mr = 1368903

| pages = 341–358

| title = Competitive algorithms for distributed data management

| volume = 51

| year = 1995| doi-access = free

}}. and the assignment of files to servers in distributed file systems.{{citation

| last1 = Awerbuch | first1 = Baruch | author1-link = Baruch Awerbuch

| last2 = Bartal | first2 = Yair

| last3 = Fiat | first3 = Amos

| contribution = Competitive distributed file allocation

| doi = 10.1145/167088.167142

| pages = 164–173

| title = Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing (STOC '93)

| year = 1993| isbn = 978-0897915915 | s2cid = 7421364 }}.

Fiat's interest in game theory stretches back to his thesis research, which included analysis of the children's game Battleship.{{citation

| last1 = Fiat | first1 = Amos

| last2 = Shamir | first2 = Adi

| doi = 10.1002/net.3230190306

| issue = 3

| journal = Networks

| mr = 996587

| pages = 361–371

| title = How to find a battleship

| volume = 19

| year = 1989}}. He has taken inspiration from the game Tetris in developing new job shop scheduling algorithms,{{citation

| last1 = Bartal | first1 = Yair

| last2 = Fiat | first2 = Amos

| last3 = Karloff | first3 = Howard

| last4 = Vohra | first4 = Rakesh

| contribution = New algorithms for an ancient scheduling problem

| doi = 10.1145/129712.129718

| pages = 51–58

| title = Proceedings of the Twenty-Fourth ACM Symposium on Theory of Computing (STOC '92)

| year = 1992| isbn = 978-0897915113

| citeseerx = 10.1.1.32.3173

| s2cid = 15741871

}}. as well as applying competitive analysis to the design of game-theoretic auctions.{{citation

| last1 = Fiat | first1 = Amos

| last2 = Goldberg | first2 = Andrew V. | author2-link = Andrew V. Goldberg

| last3 = Hartline | first3 = Jason D.

| last4 = Karlin | first4 = Anna R. | author4-link = Anna Karlin

| contribution = Competitive generalized auctions

| doi = 10.1145/509907.509921

| pages = 72–81

| title = Proceedings of the Thirty-Fourth ACM Symposium on Theory of Computing (STOC '02)

| year = 2002| isbn = 978-1581134957

| s2cid = 14688502

}}.

• Amos Fiat and Moni Naor, Rigorous Time/Space Tradeoffs for Inverting Functions, SIAM J. Computing 29(3), 1999, pp. 790–803.
• Benny Chor, Amos Fiat, Moni Naor and Benny Pinkas, Tracing Traitors, IEEE Transactions on Information Theory, Vol. 46(3), pp. 893–910, 2000.
• David Chaum, Amos Fiat and Moni Naor, Untraceable Electronic Cash, 1990.{{Citation|last1=Chaum|first1=David|title=Untraceable Electronic Cash|date=1990|work=Advances in Cryptology – CRYPTO’ 88|volume=403|pages=319–327|editor-last=Goldwasser|editor-first=Shafi|publisher=Springer New York|language=en|doi=10.1007/0-387-34799-2_25|isbn=9780387971964|last2=Fiat|first2=Amos|last3=Naor|first3=Moni|doi-access=free}}
• Amos Fiat and Moni Naor, Broadcast Encryption, 1994.
• Amos Fiat and Moni Naor, Implicit O(1) Probe Search, SIAM J. Computing 22: 1–10 (1993).

• 2016 (with Moni Naor) Paris Kanellakis Theory and Practice Award of the Association for Computing Machinery{{cite web|url=http://awards.acm.org/kanellakis/|title=ACM Paris Kanellakis Award|publisher= ACM|access-date= 6 June 2017}}
• EATCS Award (2023){{cite web |url=https://eatcs.org/index.php/component/content/article/1-news/2939-the-eatcs-award-2023-laudatio-for-amos-fiat |title=The EATCS Award 2023 - Laudatio for Amos Fiat |publisher=EATCS |access-date=March 31, 2023}}

{{reflist|colwidth=30em}}

{{Kanellakis Award laureates |state=autocollapse}}

{{EATCS Award laureates}}

{{authority control}}

{{DEFAULTSORT:Fiat, Amos}}

Category:1956 births

Category:Living people

Category:Israeli cryptographers

Category:Academic staff of Tel Aviv University

Category:Israeli theoretical computer scientists

Category:Public-key cryptographers