Graph-Coloring Problem, Who raise this problem, why?

Rome Alphabet -- Latin Alphabet

http://en.wikipedia.org/wiki/Roman_alphabet

Greek Alphabet

http://en.wikipedia.org/wiki/Greek_alphabet

NP-co Problems

NP-complete problems refer to decision problems.

Eg: set cover problem. The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard.
http://en.wikipedia.org/wiki/Set_cover_problem



Why the reduction started from CIRCUIT-SAT?

is CIRCUIT-SAT meaningful? useful?


The concept of NP-complete was introduced by Stephen Cook(Turing receiver)in 1971. In 1972, Richard Karpg (Turing receiver) proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems);





Dominating Set Problem:
http://en.wikipedia.org/wiki/Dominating_set_problem

Karp's 21 NP-complete problems:

http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems


List of NP-complete problems:

http://en.wikipedia.org/wiki/List_of_NP-complete_problems

History

http://en.wikipedia.org/wiki/History

Knowledge, Civilization

anthropology http://en.wikipedia.org/wiki/Anthropology

Game Theory

 Game Theory : A branch of applied mathematics. 

HB series

Henri Gilbert -- on RFID

Strange....No articles of him can be found on http://www.avoine.net/rfid/

Most cited papers on RFID-- By whom, Why are they frequently cited?

Gildas Avoine -- on RFID

Brief Bio：


Now  professor of information security and cryptography at the UCL in Louvain-la-Neuve (Belgium)


Previously  worked as a researcher at MIT  hosted by Ron Rivest in the CSAIL 


EPFL (Switzerland) in the LASEC， PHD   advisor:  Serge Vaudenay

PHD thesis:  Cryptography in radio frequency identification and fair exchange protocols.

http://library.epfl.ch/en/theses/?nr=3407

University of Caen (France)  Bachelor degree in mathematics and Bachelor and Master degrees in computer science


Research Area：


"My research activities relate to cryptography and information security, especially cryptographic protocols. My recent works addressed fair exchange protocols, time-memory trade-offs, non-adjacent form representations, but also and mostly authentication in radio-frequency (RFID) systems, from both theoretical and practical approaches."  


Homepage: http://www.avoine.net/

Works on RFID:


2010 6 2009 5 2008 3 2007 1 2006 1 2005 5  2004 1


2010


Gildas Avoine, Muhammed Ali Bingol, Suleyman Kardas, Cédric Lauradoux And Benjamin Martin.
A Framework For Analyzing RFID Distance Bounding Protocols.
(JCS, August 2010)


Gildas Avoine, Xavier Carpent And Benjamin Martin.
Strong Authentication And Strong Integrity (SASI) Is Not That Strong.
(RFIDSec'10, June 2010)


Gildas Avoine, Benjamin Martin And Tania Martin.
Tree-Based RFID Authentication Protocols Are Definitively Not Privacy-Friendly.
(RFIDSec'10, June 2010)


Gildas Avoine, Iwen Coisel And Tania Martin.
Time Measurement Threatens Privacy-Friendly RFID Authentication Protocols.
(RFIDSec'10, June 2010)


Orhun Kara, Suleyman Kardas, Muhammed Ali Bingol And Gildas Avoine.
Optimal Security Limits Of RFID Distance Bounding Protocols.
(RFIDSec'10, June 2010)


Rolando Trujillo Rasua, Benjamin Martin And Gildas Avoine.
The Poulidor Distance-Bounding Protocol.
(RFIDSec'10, June 2010)


2009


Chong Hee Kim And Gildas Avoine.
RFID Distance Bounding Protocol With Mixed Challenges To Prevent Relay Attacks.
(CANS'09, December 2009, Former Version: IACR EPrint At "Http://Eprint.Iacr.Org/2009/310.Pdf")


Gildas Avoine, Christian Floerkemeier And Benjamin Martin.
RFID Distance Bounding Multistate Enhancement.
(IndoCrypt'09, December 2009)


Gildas Avoine And Aslan Tchamkerten.
An Efficient Distance Bounding RFID Authentication Protocol: Balancing False-Acceptance Rate And Memory Requirement.
(ISC'09, September 2009)


Gildas Avoine, Cédric Lauradoux And Tania Martin.
When Compromised Readers Meet RFID.
(WISA'09, August 2009)


Gildas Avoine, Cédric Lauradoux And Tania Martin.
When Compromised Readers Meet RFID (Extended Version).
(RFIDSec'09, July 2009)


2008


Chong Hee Kim, Gildas Avoine, François Koeune, François-Xavier Standaert And Olivier Pereira.
The Swiss-Knife RFID Distance Bounding Protocol.
(ICISC 2008, December 2008)




Gildas Avoine And Aslan Tchamkerten.
An Asymptotically Optimal RFID Protocol Against Relay Attacks.
(IACR EPrint, September 2008)


Gildas Avoine, Kassem Kalach And Jean-Jacques Quisquater.
EPassport: Securing International Contacts With Contactless Chips.
(FC'08, January 2008)


2007


Gildas Avoine, Levente Buttyán, Tamás Holczer, And István Vajda.
Group-Based Private Authentication.
(TSPUC 2007, June 2007)


2006 


Claude Castelluccia And Gildas Avoine.
Noisy Tags: A Pretty Good Key Exchange Protocol For RFID Tags.
(CARDIS'06, April 2006)


2005


Gildas Avoine.
Cryptography In Radio Frequency Identification And Fair Exchange Protocols.
(PhD Thesis, December 2005)


Gildas Avoine.
Adversary Model For Radio Frequency Identification.
(Technical Report LASEC-REPORT-2005-001, EPFL, Lausanne, Switzerland, September 2005)


Gildas Avoine, Etienne Dysli, And Philippe Oechslin.
Reducing Time Complexity In RFID Systems.
(Selected Areas In Cryptography, August 2005)


Gildas Avoine And Philippe Oechslin.
A Scalable And Provably Secure Hash-Based RFID Protocol.
(PerSec, March 2005)


Gildas Avoine And Philippe Oechslin.
RFID Traceability: A Multilayer Problem.
(FC'05, February-March 2005)


2004




Gildas Avoine.
Privacy Issues In RFID Banknote Protection Schemes.
(CARDIS'04, August 2004)

First tier papers on RFID -- by whom, Why they are first tier ones

Complexity theory, Number theory?

Philosophy Logic Math

Some one related this three things together!  His students are powerful too.

http://en.wikipedia.org/wiki/Hao_Wang_(academic)

Another guy

http://en.wikipedia.org/wiki/Kurt_G%C3%B6del

http://en.wikipedia.org/wiki/Gottlob_Frege



Philosophy: http://en.wikipedia.org/wiki/Philosophy

Logic: http://en.wikipedia.org/wiki/Logic

Math: http://en.wikipedia.org/wiki/Math

Millennium Technology Prize

http://en.wikipedia.org/wiki/Millennium_Technology_Prize

Millennium Prize problems in Math

http://en.wikipedia.org/wiki/Millennium_Prize_Problems

Why these problems deserve the prize?

Due to the complexity to tackle the problem, or the influence of the problem to real applications?

Are the problems meaningful?

Broad & Deep

How broad is "broad"?

How deep is "deep"?

Ari Juels-- On RFID

Homepage: http://www.rsa.com/rsalabs/node.asp?id=2029

" In 2004, MIT's Technology Review Magazine named Dr. Juels one of the world's top 100 technology innovators under the age of 35. Computerworld honored him in its "40 Under 40" list in 2007. " 


technology innovator? 

"Ari's dozens of research publications span a range of topics, including biometric security, RFID security and privacy, electronic voting, browser security, combinatorial optimization, and denial-of-service protection."

Publication:
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/j/Juels:Ari.html


Works on RFID:

2009 1   2008  2   2007 3   2006  2  2005  7  2004 4  2003 2

Among these works, which are the influential ones?


Which group or person he cooperated with on RFID？


2009

Mastooreh Salajegheh, Shane Clark, Benjamin Ransford, Kevin Fu And Ari Juels.
CCCP: Secure Remote Storage For Computational RFIDs.
(USENIX'09, August 2009)




2008


Karl Koscher, Ari Juels, Tadayoshi Kohno And Vjekoslav Brajkovic.
EPC RFID Tags In Security Applications: Passport Cards, Enhanced Drivers Licenses, And Beyond.
(Manuscript, 2008)


Ari Juels, Ravikanth Pappu And Bryan Parno.
Unidirectional Key Distribution Across Time And Space With Applications To RFID Security.
(USENIX Security Symposium, July 2008)


2007


Ari Juels And Stephen Weis.
Defining Strong Privacy For RFID.
(PerCom'07, March 2007, Former Version: IACR EPrint At "Http://Eprint.Iacr.Org/2006/137.Pdf")


Benessa Defend, Kevin Fu And Ari Juels.
Cryptanalysis Of Two Lightweight RFID Authentication Schemes.
(PerSec'07, March 2007)


Thomas S. Heydt-Benjamin, Dan V. Bailey, Kevin Fu, Ari Juels, And Tom O'Hare.
Vulnerabilities In First-Generation RFID-Enabled Credit Cards.
(FC'07, February 2007)


2006


John Halamka, Ari Juels, Adam Stubblefield, And Jonathan Westhues.
The Security Implications Of VeriChip Cloning.
(Manuscript In Submission, March 2006)


Ari Juels.
RFID Security And Privacy: A Research Survey.
(IEEE Journal On Selected Areas In Communications, February 2006, Former Version)


2005


Ari Juels, David Molnar, And David Wagner.
Security And Privacy Issues In E-Passports.
(SecureComm, September 2005)


Ari Juels And Stephen Weis.
Authenticating Pervasive Devices With Human Protocols.
(Crypto, August 2005)


Steve Bono, Matthew Green, Adam Stubblefield, Ari Juels, Avi Rubin, And Michael Szydlo.
Security Analysis Of A Cryptographically-Enabled RFID Device.
(USENIX Security Symposium, July-August 2005)


Ari Juels, Paul Syverson, And Dan Bailey.
High-Power Proxies For Enhancing RFID Privacy And Utility.
(Workshop On Privacy Enhancing Technologies - PET, May-June 2005)




Simson Garfinkel, Ari Juels, And Ravi Pappu.
RFID Privacy: An Overview Of Problems And Proposed Solutions.
(IEEE Security And Privacy, May-June 2005)


Ari Juels.
Strengthening EPC Tags Against Cloning.
(Manuscript, March 2005)


Ari Juels.
RFID Privacy: A Technical Primer For The Non-Technical Reader.
(Book Chapter, Draft, February 2005)


2004


Ari Juels And John Brainard.
Soft Blocking: Flexible Blocker Tags On The Cheap.
(Workshop On Privacy In The Electronic Society - WPES, October 2004)


Ari Juels.
Minimalist Cryptography For Low-Cost RFID Tags.
(International Conference On Security In Communication Networks - SCN, September 2004)


Ari Juels.
"Yoking-Proofs" For RFID Tags.
(Workshop On Pervasive Computing And Communications Security - PerSec, March 2004)


Philippe Golle, Markus Jakobsson, Ari Juels, And Paul Syverson.
Universal Re-Encryption For Mixnets.
(The Cryptographers' Track At The RSA Conference - CT-RSA, February 2004)




2003


Ari Juels, Ronald Rivest, And Michael Szydlo.
The Blocker Tag: Selective Blocking Of RFID Tags For Consumer Privacy.
(Conference On Computer And Communications Security - ACM CCS, October 2003)


Ari Juels And Ravikanth Pappu.
Squealing Euros: Privacy Protection In RFID-Enabled Banknotes.
(FC'03, January 2003)