School of Computer Science Professor Wins Award for Influential Cryptography Research

Professor Alexandra Boldyreva has won a Test of Time Award from the International Conference on Practice and Theory in Public Key Cryptography (PKC) for her work on new multi-user digital signatures.

Boldyreva, who is a professor and associate chair in the School of Computer Science, wrote the single-author winning paper, Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, in 2003 as a Ph.D. student at the University of California San Diego.

“My advisor had to convince me to write the paper because I thought the results were too simple to deserve a publication,” Boldyreva said. “Of course, back then I would have never believed that the paper would do so well.”

Her new multi-user digital signature schemes were simpler and more efficient than existing schemes at the time. One of the most useful was a multisignature that allows a number of users to jointly digitally sign the same message while keeping the final signature as short and computationally efficient as a single signature. In effect, the length of the multisignature doesn’t grow as more users sign.

Secure networking protocols as well as blockchains and cryptocurrencies commonly rely on efficient multi-user signatures. Yet, at the same time, the schemes Boldyreva created are still simple enough that introductory cryptography courses teach them.

Boldyreva gave a five-minute presentation on the paper at this year’s virtually held PKC.

“Now, I’m certain that simplicity is a big advantage as long as the result is useful or interesting.”