bits. Then, RSA decryption involves exponentiation by a
l3-bit exponent—i.e., about l3 multiplications. Even if
one uses fast Fourier multiplication, this exponentiation
requires l6 • polylog(l) computation. Also, unlike RSA, the
decryption function in our scheme is highly parallelizable, which may make an enormous difference in some
implementations.
References
� ��
1. boneh, D., Lipton, r. J. Algorithms for
black-box fields and their application
to cryptography (extended abstract).
6. rivest, r.L., shamir, A., Adleman,
L.M. A method for obtaining
digital signatures and public-key
cryptosystems. Commun. ACM 21, 2
ACM and its Partners are Proud to Announce
In CRYPTO (1996), 283–297.
2. Gentry, C. A fully Homomorphic
(1978), 120–126.
Encryption Scheme. Ph. D. thesis,
stanford university, 2009. crypto.
stanford.edu/craig.
7. smart, n. P., Vercauteren, F. Fully
homomorphic encryption with
relatively small key and ciphertext
sizes, 2009. http://eprint.iacr.
org/2009/571.
Computer Science Education Week
3. Gentry, C. Fully homomorphic
encryption using ideal lattices. STOC.
7. ePILoGue
M. Mitzenmacher ed. ACM, 2009,
8. van Dam, W., hallgren, s., Ip, L.
169–178.
The morning after her dream, Alice explains her glovebox
solution to her workers. They are not happy, but they wish
to remain employed. As the day progresses, it becomes clear
that the gloveboxes are slowing down the pace of jewelry
construction considerably. The main problem seems to be
the thick gloves, which multiply the time needed for each
assembly step. After a few days of low output, Alice curtails
her use of the gloveboxes to pieces that contain the most
valuable diamonds.
4. Goldwasser, s., Micali, s. Probabilistic
Quantum algorithms for some hidden
shift problems. SIAM J. Comp. 36, 3
encryption. J. Comp. Syst. Sci. 28, 2
(2006), 763–778.
(1984), 270–299.
9. van Dijk, M., Gentry, C., halevi, s.,
To encourage increased participation in
5. rivest, r. L., Adleman, L. M., Dertouzos,
M.L. on data banks and privacy
homomorphisms. In Foundations of
Vaikuntanathan, V. Fully homomorphic
encryption over the integers,
2009. http://eprint.iacr.org/2009/
Secure Computations (1978), 169–180.
616.
computer science at all educational levels
Craig Gentry ( cbgentry@us.ibm.com),
IbM T. J. Watson research Center,
hawthorne, ny.
December 6 - 12, 2009
Alice loses her suit against Acme Glovebox Company,
because, as far as anyone knows in Alice’s parallel world,
gloves in gloveboxes are always very stiff and stiffen completely after moderate use. The old judge explains this to her
in a patronizing tone.
Join the Conversation at:
But Alice refuses to give up. She hires a handsome young
glovebox researcher, and tasks him with developing a glove
flexible enough to permit the nimble assembly of jewels and
unlocking of boxes, but sturdy enough to prevent the boxes
from being easily compromised. The researcher, amazed at
his good fortune, plunges into the problem.
� ��
CSEDWEEK.ORG
�� �
© 2010 ACM 0001-0782/10/0300 $10.00
Announcing ACM’s New
Career & Job Center!
Are you looking for your next IT job? Do you need Career Advice?
Visit ACM’s newest career resource at http://www.acm.org/careercenter
The ACM Career & Job Center offers ACM members
a host of career-enhancing benefits!:
• A highly targeted focus on job opportunities in the computing industry
• Access to hundreds of corporate job postings
• Resume posting – stay connected to the employment market and maintain full control over
your confidential information
• An advanced Job Alert system that notifies you of new opportunities matching your criteria
• Live career advice to assist you in resume development, creating cover letters,
company research, negotiating an offer and more
The ACM Career & Job Center is the perfect place to
begin searching for your next employment opportunity!
Visit today at http://www.acm.org/careercenter
