Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2006
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/cs/0610036 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909853095559168 |
|---|---|
| author | Nuida, Koji Hagiwara, Manabu Watanabe, Hajime Imai, Hideki |
| author_facet | Nuida, Koji Hagiwara, Manabu Watanabe, Hajime Imai, Hideki |
| contents | It is known that Tardos's collusion-secure probabilistic fingerprinting code (Tardos code; STOC'03) has length of theoretically minimal order with respect to the number of colluding users. However, Tardos code uses certain continuous probability distribution in codeword generation, which creates some problems for practical use, in particular, it requires large extra memory. A solution proposed so far is to use some finite probability distributions instead. In this paper, we determine the optimal finite distribution in order to decrease extra memory amount. By our result, the extra memory is reduced to 1/32 of the original, or even becomes needless, in some practical setting. Moreover, the code length is also reduced, e.g. to about 20.6% of Tardos code asymptotically. Finally, we address some other practical issues such as approximation errors which are inevitable in any real implementation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_cs_0610036 |
| institution | arXiv |
| publishDate | 2006 |
| record_format | arxiv |
| spellingShingle | Optimization of Memory Usage in Tardos's Fingerprinting Codes Nuida, Koji Hagiwara, Manabu Watanabe, Hajime Imai, Hideki Cryptography and Security Numerical Analysis K.4.4; G.1.4 It is known that Tardos's collusion-secure probabilistic fingerprinting code (Tardos code; STOC'03) has length of theoretically minimal order with respect to the number of colluding users. However, Tardos code uses certain continuous probability distribution in codeword generation, which creates some problems for practical use, in particular, it requires large extra memory. A solution proposed so far is to use some finite probability distributions instead. In this paper, we determine the optimal finite distribution in order to decrease extra memory amount. By our result, the extra memory is reduced to 1/32 of the original, or even becomes needless, in some practical setting. Moreover, the code length is also reduced, e.g. to about 20.6% of Tardos code asymptotically. Finally, we address some other practical issues such as approximation errors which are inevitable in any real implementation. |
| title | Optimization of Memory Usage in Tardos's Fingerprinting Codes |
| topic | Cryptography and Security Numerical Analysis K.4.4; G.1.4 |
| url | https://arxiv.org/abs/cs/0610036 |