Method and System for Performing Permutations with Bit Permutation Instructions

Web Published:
10/31/2014
Description:

Princeton Docket #00-1709-1

 

The present invention provides permutation instructions which can be used in software executed in a programmable processor for solving permutation problems in cryptography, multimedia and other applications. PPERM and PPERM3R instructions are defined to perform permutations by a sequence of instructions with each sequence specifying the position in the source for each bit in the destination. In the PPERM instruction bits in the destination register that change are updated and bits in the destination register that do not change are set to zero. In the PPERM3R instruction bits in the destination register that change are updated and bits in the destination register that do not change are copied from intermediate result of previous PPERM3R instructions. Both PPERM and PPERM3R instruction can individually do permutation with bit repetition. Both PPERM and PPERM3R instruction can individually do permutation of bits stored in more than one register. In an alternate embodiment, a GRP instruction is defined to perform permutations. The GRP instruction divides the initial sequence in the source register into two groups depending on control bits. The first group is combined with the second group to form an intermediate sequence toward the desired final permutation. The total number of GRP instructions for a bit level permutation of n bits is not greater than 1gn. The GRP instruction can be used to permute k-bit subwords packed into an n bits word, where k can be 1, 2, . . . , or n bits, and k*r=n. At most 1gr permutation instructions are used in the permutation instruction sequence, where r is the number of k-bit subwords to be permuted. The GRP instruction can also be used to permute 2n bits stored in two n-bit registers. The total number of instructions for bit permutation of 2n bits is 21gn+4, and two of those instructions are SHIFT PAIR instruction.

Faculty Inventor              

 

Ruby B. Lee is the Forrest G. Hamrick Professor in Engineering and Professor of Electrical Engineering at Princeton University, with an affiliated appointment in the Computer Science Department. She is the director of the Princeton Architecture Laboratory for Multimedia and Security (PALMS). Professor Lee is an expert in hardware-enhanced security and has designed architectures for secure processors, secure caches that do not leak information through side-channel attacks, and secure servers for cloud computing. Her research is in the intersection of computer architecture and cyber security. She is a Fellow of the Association for Computing Machinery (ACM) and a Fellow of the Institute of Electrical and Electronic Engineers (IEEE). She holds over 120 U.S. and international patents.

 

Intellectual Property Status

 

Patents granted:

 

US 7519795 B2

https://www.google.com/patents/US7519795?dq=7519795&hl=en&sa=X&ei=A5VTVMz6McrCsATJ0II4&ved=0CB8Q6AEwAA

 

US 7174014

https://www.google.com/patents/US7174014?dq=US+7174014&hl=en&sa=X&ei=UTjRVPrGM8uCsQTV_YGIBg&ved=0CB0Q6AEwAA

 

 

Princeton is seeking to identify appropriate partners for the further development and commercialization of this technology.

 

Contact

 

Michael Tyerech
Princeton University Office of Technology Licensing

(609) 258-6762• tyerech@princeton.edu

 

Laurie Bagley
Princeton University Office of Technology Licensing

(609) 258-5579• lbagley@princeton.edu

Patent Information:
Category(s):
Computers and Software
For Information, Contact:
John Ritter
Director
Princeton University
609-258-1570
jritter@Princeton.EDU
Inventors:
Ruby Lee
Zhijie Shi
Keywords:
computers/software
cryptography
data security