Visitors to the EU could face digital fingerprinting at airports under plans to beef up border security, EU Justice Commissioner Franco Frattini has said.
He said travellers from outside the EU could face a biometric test as part of their visa while those not needing a permit would be checked on arrival.
There are also plans to improve border surveillance and land and sea patrols.
Rights group Privacy International said the move could create a "fortress Europe" for foreigners.
And the European Council on Refugees in Exile complained that the tighter the restrictions, the harder it would become for people to seek safety from persecution.
'Highest security level'
The proposals for a radical shake-up of the EU's border security were unveiled by Mr Frattini in Brussels.
Mr Frattini says the plans will have to be agreed by member states
He said the measures would apply to all 24 members of the Schengen accord, and it was up to countries such as the UK and Ireland whether to join in.
The commissioner said the EU had to use "the most advanced technology to reach the highest level of security" to stop visitors overstaying their welcome in Europe and to prevent terrorists from coming in.
EU has 1,792 designated external border crossing points with controls
665 air border crossing points, 871 sea borders and 246 land borders
300m crossings per year at these points
160m crossings by EU citizens, 60m by non-EU without visa, 80m by non-EU with visa
Estimated 8m illegal immigrants in EU, half came in legally but overstayed
The plans would also allow for a Registered Traveller Programme to enable EU citizens to pass through customs with only random checks.
That could be extended to include non-EU citizens on multiple visas.
Mr Frattini said he hoped the reforms - if approved by all the EU member states - would be introduced between 2010-2015.
A central aim of the measures is tackling the large number of illegal immigrants who came into the EU legally: "The factor number one is over-stayers in Europe," Mr Frattini said.
Under the proposed entry and exit register, an alert would be sent when a visa expired and no exit had been recorded.
Biometric technology is already being introduced. From 2009, all EU passports will feature a digital fingerprint and photograph and, from 2011 non-EU citizens who apply for a visa will have to give their biometric details.
Currently, anyone crossing a border into the EU's 24 Schengen countries faces a minimum entry and exit check, whether they are an EU citizen or not. Non-EU nationals face a more thorough check, including a search of databases.
As well as improved border controls, the commission also wants to toughen up patrols, focusing particularly on illegal migration routes to the Canary Islands and across the Mediterranean and Black Sea.
HAVE YOUR SAY
No measure is too much if human rights are not tampered with.
Anthony Augustine, UK
A surveillance system (Eurosur) would be set up which would use state-of-the-art technology such as satellites and aerial drones.
"We cannot have mafia or traffickers or terrorists using better technology than our police," Mr Frattini said.
There would also be further operations involving the EU's border agency, Frontex.
The proposals will have to be agreed by member states and MEPs before they can come into effect.