0:02

We have learnt the importance of intellectual property protection, and

Â the basics of digital watermarking.

Â Now, we will show a couple of examples to see how to

Â embed digital watermarks into hardware design intellectual properties.

Â [SOUND] The first example is on Boolean expression optimization.

Â The problem, is to rewrite a Boolean formula don't care

Â conditions using the minimum number of literals.

Â Our goal is to protect, to minimize the formula,

Â which is the design intellectual property in this case.

Â 1:00

For example, to had, to hide the message 01, we make the first

Â don't care condition to be zero, and, the second don't care condition, after that

Â condition the formula will be evaluated at one, and thus, the formula becomes,

Â 1:20

this new form, which has a well additional term, abcd,

Â corresponds to the second don't care condition.

Â And we can find, the optimal solution in this case,

Â which F becomes a prime, b, c prime plus bd.

Â And similarly to hide message 10, we can include the first don't care condition

Â into the Boolean formula and then leave the second don't care condition away, so

Â this is because the second bit is 0, and, as a result we

Â upturn this solution which is distinct or different from the first one.

Â 2:25

However, we see some of the solutions are better than others.

Â For example, the solution with 01, and 11 as watermark, they both have five

Â letters as the solution, and, however, the other two have nine literals.

Â This is one of the challenges for watermarking,

Â which is known as fairness, and we will talk about this later.

Â 2:55

This example is a radix-4 to binary encoder, what we have here is,

Â this is the truth table where we have each of the four symbols,

Â the radix-4 member system, and

Â we'll convert each of the symbols into a binary representation, with fo, two bits.

Â 3:56

The first thing we do is,

Â we represent this, these two letters into, binary information.

Â And what we do is, we consider that ASCII code, D and A, and then we

Â also add a parity bit at the end, so this gives us a 15 bit watermark.

Â And we embedded this 15 bit watermark into the original truth table for the original

Â design, what we do here is, we see there are 12 don't care conditions.

Â 4:28

With don't care con, 12 don't care conditions we can embed three bits, this

Â is because, if you want embed four bits, we may end up with the situation that,

Â it does not exist in these 12 don't care conditions, because 12 can

Â represent 8 different combinations for, of 3 bits, but not 4 bits.

Â So what we do is we consider the last 3 bits of

Â the watermark which is 010, which is a binary 2, so what we do is we come to

Â our list of don't care conditions, see zero, one, and the two.

Â So this is the don't care condi, condition,

Â we are going to specify a deterministic value to embed our signature.

Â And, what value should the system output in this don't care condition,

Â that depends on what is the message you want to embed here.

Â So, what we see in the original watermark, the next two bits, which because, our,

Â our output has two bits.

Â So, the next two bits are 00, so that is why,

Â I replace these don't cares by two zeroes.

Â And similarly, I can move out to the next three bits, I can do this because now,

Â the don't care table has 11 don't cares, I can still do, three bits.

Â So this 3-bit is 100, which is the binary four, so what I do is I count zero,

Â one, two, three, four, so this is the don't care condition,

Â I'm going to force a value, and the value happens to again to be 00,

Â because the next two bits in the watermark are 00.

Â And then, we keep on this process, and then the next one bit is 001,

Â which is the binary of one, so 01, and then the massive logo add,

Â add the, the leading bits, which is 10.

Â So now we have successfully convert, this 15-bit watermark into three pairs

Â of input and output, and we added them into the original truth table, and then

Â we got an augmented truth table, which we called the watermarked truth table.

Â 7:10

So in this case, instead of four literals, two logical gates, we need one, two,

Â three, four, five, six, seven, eight literals.

Â This is something we know called design overhead, and

Â again, we'll discuss about the design overhead later.

Â 8:21

And usually this problem is not that hard to solve, but what is harder is,

Â well we tried to minimize the number of colors we, we need.

Â As a matter of fact,

Â if we consider whether a, a graph can be colored by two colorful nodes,

Â which is known as the two, 2-colorable problem, that problem is trivial to solve.

Â 9:15

So what we ha, have here is, we have a graph with 11 nodes,

Â and a, probably around 20 edges.

Â [COUGH] What we want to do here is, we want to protect our solution to,

Â to a scheme of this graph, and what we do is,

Â by hiding a message 2000 into the solution, to achieve such protection.

Â 9:41

The first thing we do as we show previously, we,

Â we need to convert our signature, well our message into binary, in this case,

Â the decimal number 2000 will be converted into binary bit sequence here.

Â And what I do now is, I want to show you, step by step how I can hide this,

Â bitstream into the graph, and then solve the graph, find a solution.

Â The first thing I do is I take a look, look at note 0,

Â I want to find, the next two note that are not connected to note 0,

Â in this case, I see 0 and 1 they're connected, so 1 is not a candidate, but,

Â both note 2 and 3, they are not connected to note 0,

Â so 2 and 3 will be candidate in this case.

Â And to hide a bit of information, what I'll do is, I'm

Â going to add one additional edge starting from 0, and what is the receiving end or

Â the receiving note of this edge that depends on the [INAUDIBLE] I'm going to

Â invite, so, if want to invite a 1, I'm going to connect a 0 to 3,

Â if I'm going to invite a 0, I'm going to connect the 0 and a 2.In this case,

Â because I want to invite a 2, so what I do is connect a 0 and the 3, and

Â similarly, I move on to the next one, know the 1, 3 and 4, they are the next two

Â nodes that are not connected to 1, and to add another bit-1, I connected 1 and a 4.

Â So I can repeat this process, and at the end, all these 11 bits will

Â be embedded into the, into this new graph, which we called a watermarked graph,

Â 12:05

As a matter of fact, indeed I can also put note 8 as blue,

Â which also satisfies all the requirements, which means that for

Â all notes that are connected to 8, they're not, they're not in

Â the same color in the original graph, but not in the watermarked graph.

Â So, the fact that this solution satisfies a set of additional constraints,

Â will be used as the proof of our authorship.

Â