# Major step ahead for cryptography

##### May 26, 2010

Imagine you could work out the answer to a question, without knowing what the question was. For example, suppose someone thinks of two numbers and then asks another person to work out their sum, without letting them know what the two numbers are. However, they are given an encryption of the two numbers but not told how to decrypt them.

Nigel Smart, Professor of Cryptology in the Department of Computer Science at the University of Bristol, will present a paper in Paris today, which makes a step towards a fully practical system to compute on encrypted data. The work could have wide ranging impact on areas as diverse as database access, electronic auctions and electronic voting.

Professor Smart said: "We will present a major improvement on a recent encryption scheme invented by IBM in 2009."

"Our scheme allows for computations to be performed on , so it may eventually allow for the creation of systems in which you can store data remotely in a secure manner and still be able to access it."

This system could be used in medical care research. Hospitals or drug companies could perform statistical calculations on their shared databases without needing to reveal information about the individual patients. This would enable more efficient research in medical care and drug testing, without compromising patient privacy.

As another example, imagine a person is participating in an but doesn't want the auctioneer to find out what their bid is in case it is used to encourage higher bids. Encrypted bids could be sent to the auctioneer and then, using a fully homomorphic scheme, the auctioneer could work out who won and what the winning bid was without learning what all the other bids were.

Alternatively in an electronic election all voters could encrypt their votes. The outcome of the election could then be computed by the returning officer whilst still ensuring the voter's privacy.

For nearly 30 years one cryptographic dream has been to come up with an for which you can "add" and "multiply" ciphertexts. Ciphertext is the encrypted result. This is a so-called fully homomorphic scheme. As soon as you can "add" and "multiply" you can compute any function.

Over the years many encryption schemes have been proposed which either have the "add" operation or the "multiply" operation, but not both.
It was one of the Holy Grail's of cryptography to find a scheme where you could perform both operations.

In 2009 Craig Gentry from IBM came up with the first scheme which simulataneously allows you to "add" and "multiply" ciphertexts. Gentry's scheme, although an amazing theoretical breakthrough is not practical.

In the paper to be presented, Professor Nigel Smart and Dr Frederik Vercauteren, from the Katholieke University Leuven in Belgium, have devised a way of simplifying Gentry's scheme so that it becomes more practical. Whilst the new scheme is not fully practical it is an important step along the way to forming a system which is truly practical.

Professor Smart and Dr Vercauteren's scheme also provides an intriguing new application of objects in an area of Pure Mathematics called Class Groups of Number Fields. Such objects have been studied in pure mathematics for around two century's with little possibility of impact on everyday life. This work is another example of the unexpected applicability of years of curiosity driven research.

The research is published at the 13th IACR workshop on Public Key Cryptography in Paris.

## Related Stories

#### Researcher Discovers Method to Fully Process Encrypted Data Without Knowing its Content

Jun 25, 2009

(PhysOrg.com) -- An IBM Researcher has solved a thorny mathematical problem that has confounded scientists since the invention of public-key encryption several decades ago. The breakthrough, called "privacy homomorphism," ...

#### Computer scientists deploy first practical, Web-based, secure, verifiable voting system

Mar 05, 2009

Computer scientists affiliated with the Center for Research on Computation and Society (CRCS), based at the Harvard School of Engineering and Applied Sciences (SEAS), in collaboration with scientists at the Université ...

#### Experts advise caution over new incentive scheme for NHS hospitals

Jan 22, 2010

The English NHS should "proceed cautiously" in introducing payment for performance schemes aimed at improving the quality of care in hospitals, warn researchers from the University of York on bmj.com today.

#### NEC Develops World's Most Efficient Privacy Preserving Authentication Scheme

Jul 22, 2005

NEC Corporation announced that it has developed the world's most efficient privacy preserving authentication scheme (or group signature scheme ) in terms of signature length and computational complexity, social infrastructure ...

#### Cyber hacking could be a thing of the past

Dec 07, 2009

(PhysOrg.com) -- High-profile websites are constantly under threat from hackers attempting to paralyse their websites but new research could make such attacks computationally impossible. This research will ...

#### Probing Question: How do Ponzi Schemes work?

Jul 02, 2009

Imagine the shock, the horror, and the sheer panic that would come with learning that the financial plan you’d sunk your life savings into was a sham, the financial experts you trusted were crooks, and all your money was ...

## Recommended for you

#### UT Dallas professor to develop framework to protect computers' cores

Apr 18, 2014

UT Dallas cybersecurity expert Dr. Zhiqiang Lin has received funding from the U.S. Air Force to develop a defense framework that burrows deep into a computer system to protect its core.

#### Researcher finds hidden efficiencies in computer architecture

Apr 18, 2014

The computer is one of the most complex machines ever devised and most of us only ever interact with its simplest features. For each keystroke and web-click, thousands of instructions must be communicated ...

#### Scientists apply new graph programming method for evolving exascale applications

Apr 18, 2014

(Phys.org) —Hiding the complexities that underpin exascale system operations from application developers is a critical challenge facing teams designing next-generation supercomputers. One way that computer ...

Apr 17, 2014

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

#### Preventing AI from developing anti-social and potentially harmful behaviour

Apr 17, 2014

Next time you play a computer at chess, think about the implications if you beat it. It could be a very sore loser!

#### Researcher seeks to lessen failures in computerized visual recognition programs

Apr 17, 2014

Computer programs that use facial or image recognition systems—be it security cameras or applications that search databases for everything from photographs of wanted criminals to images of bears – are like any other technological ...

##### gunslingor1
4 / 5 (1) May 26, 2010
It is obvious to me, working in industrial cyber security, that any system that uses either or both multiplication and addition on ENCRYPTED data will not be securely encryted.

Its a trade off. This system makes it a little harder to get the attackers hands on the real data once they get into a system, but it also requires that encryption algorithums are simplified in a PREDICTABLE manner, thus making it easier to decrypt the data if they happen to get their hands on it without actually getting into the system, such as a man in the middle attack. Other opions?

## More news stories

#### Ex-Apple chief plans mobile phone for India

Former Apple chief executive John Sculley, whose marketing skills helped bring the personal computer to desktops worldwide, says he plans to launch a mobile phone in India to exploit its still largely untapped ...

#### Airbnb rental site raises \$450 mn

Online lodging listings website Airbnb inked a \$450 million funding deal with investors led by TPG, a source close to the matter said Friday.

#### Health care site flagged in Heartbleed review

People with accounts on the enrollment website for President Barack Obama's signature health care law are being told to change their passwords following an administration-wide review of the government's vulnerability to the ...

#### A homemade solar lamp for developing countries

(Phys.org) —The solar lamp developed by the start-up LEDsafari is a more effective, safer, and less expensive form of illumination than the traditional oil lamp currently used by more than one billion people ...

#### Tiny power plants hold promise for nuclear energy (Update)

Small underground nuclear power plants that could be cheaper to build than their behemoth counterparts may herald the future for an energy industry under intense scrutiny since the Fukushima disaster, the ...

#### NASA's space station Robonaut finally getting legs

Robonaut, the first out-of-this-world humanoid, is finally getting its space legs. For three years, Robonaut has had to manage from the waist up. This new pair of legs means the experimental robot—now stuck ...

#### Free the seed: OSSI nurtures growing plants without patent barriers

(Phys.org) —Members of the Open Source Seed Initiative this week held a rally and seed giveaway event. The group is concerned over restricting access to seeds through patents. They are stirring up public ...

#### Filipino tests negative for Middle East virus

A Filipino nurse who tested positive for the Middle East virus has been found free of infection in a subsequent examination after he returned home, Philippine health officials said Saturday.

#### Egypt archaeologists find ancient writer's tomb

Egypt's minister of antiquities says a team of Spanish archaeologists has discovered two tombs in the southern part of the country, one of them belonging to a writer and containing a trove of artifacts including reed pens ...

#### Philippines boosts MERS monitoring after UAE nurse scare

The Philippines said Saturday it was stepping up its defences against the deadly MERS virus, with the large numbers of Filipino workers in the Middle East seen as potential carriers.