Amos Fiat

Last updated
Amos Fiat
BornDecember 1, 1956
Haifa, Israel
NationalityIsraeli
Alma mater Weizmann Institute of Science
University of California, Berkeley
Tel Aviv University
Scientific career
Fields Computer Science, Cryptography
Institutions Tel Aviv University
Doctoral advisor Adi Shamir
Richard Karp
Manuel Blum

Amos Fiat (born December 1, 1956) [1] is an Israeli computer scientist, a professor of computer science at Tel Aviv University. He is known for his work in cryptography, online algorithms, and algorithmic game theory.

Contents

Biography

Fiat earned his Ph.D. in 1987 from the Weizmann Institute of Science under the supervision of Adi Shamir. [2] 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.

Research

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) [3] and his work with David Chaum and Moni Naor on electronic money, used as the basis for the ecash system. [4] 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. [5] 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. [6]

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, [7] call control, [8] data management, [9] and the assignment of files to servers in distributed file systems. [10]

Fiat's interest in game theory stretches back to his thesis research, which included analysis of the children's game Battleship. [11] He has taken inspiration from the game Tetris in developing new job shop scheduling algorithms, [12] as well as applying competitive analysis to the design of game-theoretic auctions. [13]

Bibliography

Honours and awards

Related Research Articles

<span class="mw-page-title-main">Adi Shamir</span> Israeli cryptographer (born 1952)

Adi Shamir is an Israeli cryptographer and inventor. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm, a co-inventor of the Feige–Fiat–Shamir identification scheme, one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer science.

<span class="mw-page-title-main">Ron Rivest</span> American cryptographer

Ronald Linn Rivest is a cryptographer and computer scientist whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity. He is an Institute Professor at the Massachusetts Institute of Technology (MIT), and a member of MIT's Department of Electrical Engineering and Computer Science and its Computer Science and Artificial Intelligence Laboratory.

<span class="mw-page-title-main">David Chaum</span> American computer scientist and cryptographer

David Lee Chaum is an American computer scientist, cryptographer, and inventor. He is known as a pioneer in cryptography and privacy-preserving technologies, and widely recognized as the inventor of digital cash. His 1982 dissertation "Computer Systems Established, Maintained, and Trusted by Mutually Suspicious Groups" is the first known proposal for a blockchain protocol. Complete with the code to implement the protocol, Chaum's dissertation proposed all but one element of the blockchain later detailed in the Bitcoin whitepaper. He has been referred to as "the father of online anonymity", and "the godfather of cryptocurrency".

Ecash was conceived by David Chaum as an anonymous cryptographic electronic money or electronic cash system in 1982. It was realized through his corporation Digicash and used as micropayment system at one US bank from 1995 to 1998.

In cryptography, a random oracle is an oracle that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted.

In cryptography, an oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred.

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

Traitor tracing schemes help trace the source of leaks when secret or proprietary data is sold to many customers. In a traitor tracing scheme, each customer is given a different personal decryption key. (Traitor tracing schemes are often combined with conditional access systems so that, once the traitor tracing algorithm identifies a personal decryption key associated with the leak, the content distributor can revoke that personal decryption key, allowing honest customers to continue to watch pay television while the traitor and all the unauthorized users using the traitor's personal decryption key are cut off.)

Broadcast encryption is the cryptographic problem of delivering encrypted content over a broadcast channel in such a way that only qualified users can decrypt the content. The challenge arises from the requirement that the set of qualified users can change in each broadcast emission, and therefore revocation of individual users or user groups should be possible using broadcast transmissions, only, and without affecting any remaining users. As efficient revocation is the primary objective of broadcast encryption, solutions are also referred to as revocation schemes.

ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.

In cryptography the standard model is the model of computation in which the adversary is only limited by the amount of time and computational power available. Other names used are bare model and plain model.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

Secure two-party computation (2PC) a.k.a. Secure function evaluation is sub-problem of secure multi-party computation (MPC) that has received special attention by researchers because of its close relation to many cryptographic tasks. The goal of 2PC is to create a generic protocol that allows two parties to jointly compute an arbitrary function on their inputs without sharing the value of their inputs with the opposing party. One of the most well known examples of 2PC is Yao's Millionaires' problem, in which two parties, Alice and Bob, are millionaires who wish to determine who is wealthier without revealing their wealth. Formally, Alice has wealth , Bob has wealth , and they wish to compute without revealing the values or .

The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis. In this problem, an online algorithm must control the movement of a set of kservers, represented as points in a metric space, and handle requests that are also in the form of points in the space. As each request arrives, the algorithm must determine which server to move to the requested point. The goal of the algorithm is to keep the total distance all servers move small, relative to the total distance the servers could have moved by an optimal adversary who knows in advance the entire sequence of requests.

Task systems are mathematical objects used to model the set of possible configuration of online algorithms. They were introduced by Borodin, Linial and Saks (1992) to model a variety of online problems. A task system determines a set of states and costs to change states. Task systems obtain as input a sequence of requests such that each request assigns processing times to the states. The objective of an online algorithm for task systems is to create a schedule that minimizes the overall cost incurred due to processing the tasks with respect to the states and due to the cost to change states.

<span class="mw-page-title-main">Moni Naor</span> Israeli computer scientist (born 1961)

Moni Naor is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His advisor was Manuel Blum.

<span class="mw-page-title-main">Cynthia Dwork</span> American computer scientist

Cynthia Dwork is an American computer scientist best known for her contributions to cryptography, distributed computing, and algorithmic fairness. She is one of the inventors of differential privacy and proof-of-work.

In cryptography, the Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital signature based on it. This way, some fact can be publicly proven without revealing underlying information. The technique is due to Amos Fiat and Adi Shamir (1986). For the method to work, the original interactive proof must have the property of being public-coin, i.e. verifier's random coins are made public throughout the proof protocol.

<span class="mw-page-title-main">Toniann Pitassi</span> Canadian-American computer scientist

Toniann Pitassi is a Canadian-American mathematician and computer scientist specializing in computational complexity theory. She is currently Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University and was Bell Research Chair at the University of Toronto.

Dahlia Malkhi is an Israeli-American computer scientist who works on distributed systems and cryptocurrency.

References

  1. ↑ Fiat's home page at Tel Aviv University, retrieved 2012-02-19.
  2. ↑ Amos Fiat at the Mathematics Genealogy Project
  3. ↑ Fiat, Amos; Shamir, Adi (1987), "How to prove yourself: practical solutions to identification and signature problems", Advances in Cryptology — CRYPTO' 86, Lecture Notes in Computer Science, vol. 263, London, UK: Springer-Verlag, pp. 186–194, doi: 10.1007/3-540-47721-7_12 , ISBN   978-3-540-18047-0 .
  4. ↑ Chaum, D.; Fiat, A.; Naor, M. (1990), "Untraceable electronic cash", Proceedings on Advances in Cryptology – CRYPTO '88, Lecture Notes in Computer Science, vol. 403, London, UK: Springer-Verlag, pp. 319–327.
  5. 1 2 Amos Fiat; Moni Naor (1994). Broadcast Encryption (Extended abstract). Lecture Notes in Computer Science. Vol. 773. pp. 480–491. doi: 10.1007/3-540-48329-2_40 . ISBN   978-3-540-57766-9.{{cite book}}: |journal= ignored (help)
  6. 1 2 Naor, Moni; Benny Chor; Amos Fiat; Benny Pinkas (May 2000). "Tracing Traitors". Information Theory. 46 (3): 893–910. doi:10.1109/18.841169. S2CID   11699689.
  7. ↑ Fiat, Amos; Karp, Richard M.; Luby, Michael; McGeoch, Lyle A.; Sleator, Daniel D.; Young, Neal E. (1991), "Competitive paging algorithms", Journal of Algorithms, 12 (4): 685–699, arXiv: cs.DS/0205038 , doi:10.1016/0196-6774(91)90041-V, S2CID   3260905 .
  8. ↑ Awerbuch, Baruch; Bartal, Yair; Fiat, Amos; Rosén, Adi (1994), "Competitive non-preemptive call control", Proceedings of the Fifth ACM-SIAM Symposium on Discrete Algorithms (SODA '94), pp. 312–320, ISBN   9780898713299 .
  9. ↑ Bartal, Yair; Fiat, Amos; Rabani, Yuval (1995), "Competitive algorithms for distributed data management", Journal of Computer and System Sciences, 51 (3): 341–358, doi: 10.1006/jcss.1995.1073 , MR   1368903 .
  10. ↑ Awerbuch, Baruch; Bartal, Yair; Fiat, Amos (1993), "Competitive distributed file allocation", Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing (STOC '93), pp. 164–173, doi:10.1145/167088.167142, ISBN   978-0897915915, S2CID   7421364 .
  11. ↑ Fiat, Amos; Shamir, Adi (1989), "How to find a battleship", Networks, 19 (3): 361–371, doi:10.1002/net.3230190306, MR   0996587 .
  12. ↑ Bartal, Yair; Fiat, Amos; Karloff, Howard; Vohra, Rakesh (1992), "New algorithms for an ancient scheduling problem", Proceedings of the Twenty-Fourth ACM Symposium on Theory of Computing (STOC '92), pp. 51–58, CiteSeerX   10.1.1.32.3173 , doi:10.1145/129712.129718, ISBN   978-0897915113, S2CID   15741871 .
  13. ↑ Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R. (2002), "Competitive generalized auctions", Proceedings of the Thirty-Fourth ACM Symposium on Theory of Computing (STOC '02), pp. 72–81, doi:10.1145/509907.509921, ISBN   978-1581134957, S2CID   14688502 .
  14. ↑ Chaum, David; Fiat, Amos; Naor, Moni (1990), Goldwasser, Shafi (ed.), "Untraceable Electronic Cash", Advances in Cryptology – CRYPTO’ 88, Springer New York, vol. 403, pp. 319–327, doi: 10.1007/0-387-34799-2_25 , ISBN   9780387971964
  15. ↑ "ACM Paris Kanellakis Award". ACM. Retrieved 6 June 2017.
  16. ↑ "The EATCS Award 2023 - Laudatio for Amos Fiat". EATCS. Retrieved March 31, 2023.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.