Receiver Anonymity by Incomparable Public Keys - Revision history

Mfuessel: /* Achievements & Shortcomings */

2007-07-30T15:10:57Z

Achievements & Shortcomings

← Older revision		Revision as of 15:10, 30 July 2007
Line 112:		Line 112:
	''Incomparable Public Keys'' meets the requirements stated [[#Requirements\|above]], which Waters, Felten and Sahai prove in their paper.		''Incomparable Public Keys'' meets the requirements stated [[#Requirements\|above]], which Waters, Felten and Sahai prove in their paper.

	However, though this algorithm does scale better with the number of receivers than other methods, the idea of sending all messages to ''all'' potential receivers doesn't work well for large groups of receivers. And if there are only few receivers, the level of anonymity granted by ''any'' procedure is not very high.		However, though this algorithm does scale better with the number of receivers than other methods do, the idea of sending all messages to ''all'' potential receivers doesn't work well for large groups of receivers. And if there are only few receivers, the level of anonymity granted by ''any'' procedure is not very high.

	So there will be not many use-cases for which using ''Incomparable Public Keys'' on its own will be both useful and practicable. In most cases you will be better off by using a method that provides anonymity within a ''small'' group of receivers each time ''multiple'' times for each message. On the other hand, routing algorithms that does so are much more complex and difficult to implement.		So there will be not many use-cases for which using ''Incomparable Public Keys'' on its own will be both useful and practicable. In most cases you will be better off by using a method that provides anonymity within a ''small'' group of receivers each time ''multiple'' times for each message. On the other hand, routing algorithms that does so are much more complex and difficult to implement.

Mfuessel: /* Achievements & Shortcomings */

2007-07-30T15:09:10Z

Achievements & Shortcomings

← Older revision		Revision as of 15:09, 30 July 2007
Line 110:		Line 110:

	== Achievements & Shortcomings ==		== Achievements & Shortcomings ==
	''Incomparable Public Keys'' meets the requirements stated [[#Requirements\|above]].		''Incomparable Public Keys'' meets the requirements stated [[#Requirements\|above]], which Waters, Felten and Sahai prove in their paper.

	However, though this algorithm does scale better with the number of receivers than other methods, the idea of sending all messages to ''all'' potential receivers doesn't work well for large groups of receivers. And if there are only few receivers, the level of anonymity granted by ''any'' procedure is not very high.		However, though this algorithm does scale better with the number of receivers than other methods, the idea of sending all messages to ''all'' potential receivers doesn't work well for large groups of receivers. And if there are only few receivers, the level of anonymity granted by ''any'' procedure is not very high.

Mfuessel: /* References */

2007-07-30T15:07:54Z

References

← Older revision		Revision as of 15:07, 30 July 2007
Line 122:		Line 122:
	== References ==		== References ==
	* Waters, Felten, Sahai: [http://citeseer.ist.psu.edu/waters03receiver.html ''Receiver Anonymity via Incomparable Public Keys'']. in ''Proceedings of the 10th ACM conference on Computer and communication security'', ACM Press, 2003		* Waters, Felten, Sahai: [http://citeseer.ist.psu.edu/waters03receiver.html ''Receiver Anonymity via Incomparable Public Keys'']. in ''Proceedings of the 10th ACM conference on Computer and communication security'', ACM Press, 2003
	* Danezis: ''Better Anonymous Communications''. University of Cambridge, Computer Laboratory, 2004		* Danezis: [http://citeseer.ist.psu.edu/danezis04better.html ''Better Anonymous Communications'']. University of Cambridge, Computer Laboratory, 2004
	* Menezes, Oorschot, Vanstone: [http://www.cacr.math.uwaterloo.ca/hac/ ''Handbook of Applied Cryptography''], 1996, CRC Press		* Menezes, Oorschot, Vanstone: [http://www.cacr.math.uwaterloo.ca/hac/ ''Handbook of Applied Cryptography''], 1996, CRC Press
	* Wikipedia articles: [http://en.wikipedia.org/wiki/ElGamal ElGamal Encryption], [http://en.wikipedia.org/wiki/Decisional_Diffie-Hellman_assumption Decisional Diffie-Hellman assumption], [http://en.wikipedia.org/wiki/Semantic_security Semantic Security], [http://en.wikipedia.org/wiki/Chosen_ciphertext_attack Chosen-Ciphertext Attack], [http://en.wikipedia.org/wiki/Malleability_%28cryptography%29 Malleability].		* Wikipedia articles: [http://en.wikipedia.org/wiki/ElGamal ElGamal Encryption], [http://en.wikipedia.org/wiki/Decisional_Diffie-Hellman_assumption Decisional Diffie-Hellman assumption], [http://en.wikipedia.org/wiki/Semantic_security Semantic Security], [http://en.wikipedia.org/wiki/Chosen_ciphertext_attack Chosen-Ciphertext Attack], [http://en.wikipedia.org/wiki/Malleability_%28cryptography%29 Malleability].

Mfuessel: /* References */

2007-07-30T15:05:56Z

References

← Older revision		Revision as of 15:05, 30 July 2007
Line 123:		Line 123:
	* Waters, Felten, Sahai: [http://citeseer.ist.psu.edu/waters03receiver.html ''Receiver Anonymity via Incomparable Public Keys'']. in ''Proceedings of the 10th ACM conference on Computer and communication security'', ACM Press, 2003		* Waters, Felten, Sahai: [http://citeseer.ist.psu.edu/waters03receiver.html ''Receiver Anonymity via Incomparable Public Keys'']. in ''Proceedings of the 10th ACM conference on Computer and communication security'', ACM Press, 2003
	* Danezis: ''Better Anonymous Communications''. University of Cambridge, Computer Laboratory, 2004		* Danezis: ''Better Anonymous Communications''. University of Cambridge, Computer Laboratory, 2004
	* Menezes, Oorschot, Vanstone: [http://www.cacr.math.uwaterloo.ca/hac/\|''Handbook of Applied Cryptography''], 1996, CRC Press		* Menezes, Oorschot, Vanstone: [http://www.cacr.math.uwaterloo.ca/hac/ ''Handbook of Applied Cryptography''], 1996, CRC Press
	* Wikipedia articles: [http://en.wikipedia.org/wiki/ElGamal\|ElGamal Encryption], [http://en.wikipedia.org/wiki/Decisional_Diffie-Hellman_assumption Decisional Diffie-Hellman assumption], [http://en.wikipedia.org/wiki/Semantic_security Semantic Security], [http://en.wikipedia.org/wiki/Chosen_ciphertext_attack Chosen-Ciphertext Attack], [http://en.wikipedia.org/wiki/Malleability_%28cryptography%29 Malleability].		* Wikipedia articles: [http://en.wikipedia.org/wiki/ElGamal ElGamal Encryption], [http://en.wikipedia.org/wiki/Decisional_Diffie-Hellman_assumption Decisional Diffie-Hellman assumption], [http://en.wikipedia.org/wiki/Semantic_security Semantic Security], [http://en.wikipedia.org/wiki/Chosen_ciphertext_attack Chosen-Ciphertext Attack], [http://en.wikipedia.org/wiki/Malleability_%28cryptography%29 Malleability].

Mfuessel: /* References */

2007-07-30T15:04:46Z

References

← Older revision		Revision as of 15:04, 30 July 2007
Line 121:		Line 121:

	== References ==		== References ==
	* Waters, Felten, Sahai: ''Receiver Anonymity via Incomparable Public Keys''. in ''Proceedings of the 10th ACM conference on Computer and communication security'', ACM Press, 2003		* Waters, Felten, Sahai: [http://citeseer.ist.psu.edu/waters03receiver.html ''Receiver Anonymity via Incomparable Public Keys'']. in ''Proceedings of the 10th ACM conference on Computer and communication security'', ACM Press, 2003
	* Danezis: ''Better Anonymous Communications''. University of Cambridge, Computer Laboratory, 2004		* Danezis: ''Better Anonymous Communications''. University of Cambridge, Computer Laboratory, 2004
	* Menezes, Oorschot, Vanstone: [[http://www.cacr.math.uwaterloo.ca/hac/\|''Handbook of Applied Cryptography'']], 1996, CRC Press		* Menezes, Oorschot, Vanstone: [http://www.cacr.math.uwaterloo.ca/hac/\|''Handbook of Applied Cryptography''], 1996, CRC Press
			* Wikipedia articles: [http://en.wikipedia.org/wiki/ElGamal\|ElGamal Encryption], [http://en.wikipedia.org/wiki/Decisional_Diffie-Hellman_assumption Decisional Diffie-Hellman assumption], [http://en.wikipedia.org/wiki/Semantic_security Semantic Security], [http://en.wikipedia.org/wiki/Chosen_ciphertext_attack Chosen-Ciphertext Attack], [http://en.wikipedia.org/wiki/Malleability_%28cryptography%29 Malleability].
	* Wikipedia articles

Mfuessel at 14:52, 30 July 2007

2007-07-30T14:52:45Z

← Older revision		Revision as of 14:52, 30 July 2007
Line 119:		Line 119:

	The very strong requirement of the ''sender'' being unable to relate messages to the same receiver will often be wasted because the sender in many cases will need sufficient information about the receiver for doing the matching based on ''this'' information in order to send something useful/provide a useful service.		The very strong requirement of the ''sender'' being unable to relate messages to the same receiver will often be wasted because the sender in many cases will need sufficient information about the receiver for doing the matching based on ''this'' information in order to send something useful/provide a useful service.

			== References ==
			* Waters, Felten, Sahai: ''Receiver Anonymity via Incomparable Public Keys''. in ''Proceedings of the 10th ACM conference on Computer and communication security'', ACM Press, 2003
			* Danezis: ''Better Anonymous Communications''. University of Cambridge, Computer Laboratory, 2004
			* Menezes, Oorschot, Vanstone: [[http://www.cacr.math.uwaterloo.ca/hac/\|''Handbook of Applied Cryptography'']], 1996, CRC Press
			* Wikipedia articles

Mfuessel: /* Achievements & Shortcomings */

2007-07-30T14:39:10Z

Achievements & Shortcomings

← Older revision		Revision as of 14:39, 30 July 2007
Line 110:		Line 110:

	== Achievements & Shortcomings ==		== Achievements & Shortcomings ==
			''Incomparable Public Keys'' meets the requirements stated [[#Requirements\|above]].

			However, though this algorithm does scale better with the number of receivers than other methods, the idea of sending all messages to ''all'' potential receivers doesn't work well for large groups of receivers. And if there are only few receivers, the level of anonymity granted by ''any'' procedure is not very high.

			So there will be not many use-cases for which using ''Incomparable Public Keys'' on its own will be both useful and practicable. In most cases you will be better off by using a method that provides anonymity within a ''small'' group of receivers each time ''multiple'' times for each message. On the other hand, routing algorithms that does so are much more complex and difficult to implement.

			''Incomparable Public Keys'' (or similar methods) may be of use, however, in combination with or as part of other algorithms. For instance, it may be useful to use it for providing anonymity for each layer in multi-layer routing algorithms.

			The very strong requirement of the ''sender'' being unable to relate messages to the same receiver will often be wasted because the sender in many cases will need sufficient information about the receiver for doing the matching based on ''this'' information in order to send something useful/provide a useful service.

Mfuessel: /* Performance */

2007-06-27T09:47:57Z

Performance

← Older revision		Revision as of 09:47, 27 June 2007
Line 107:		Line 107:
	In this system, every receiver has to decrypt ''every'' message in the system with ''one'' (his) private key. The work per receiver scales linearly with the number of receivers and linearly with the number of messages per receiver and maximal answer time of a sender. While this doesn't work well for large systems, it is considerably better than most of the comparable methods of receiver anonymity that have been suggested, which scale ''quadratically'' with the number of messages per receiver and maximal answer time of sender.		In this system, every receiver has to decrypt ''every'' message in the system with ''one'' (his) private key. The work per receiver scales linearly with the number of receivers and linearly with the number of messages per receiver and maximal answer time of a sender. While this doesn't work well for large systems, it is considerably better than most of the comparable methods of receiver anonymity that have been suggested, which scale ''quadratically'' with the number of messages per receiver and maximal answer time of sender.

	More precisely, the authors point out that decryption takes about the same time as standard ElGamal decryption if the message is rejected (and not maliciously created), and roughly twice the time of standard ElGamal decryption if the message is indeed intended for the receiver. Encryption takes approximately the same time as standard ~~ElGaml~~ encryption.		More precisely, the authors point out that decryption takes about the same time as standard ElGamal decryption if the message is rejected (and not maliciously created), and roughly twice the time of standard ElGamal decryption if the message is indeed intended for the receiver. Encryption takes approximately the same time as standard ElGamal encryption.

	== Achievements & Shortcomings ==		== Achievements & Shortcomings ==

Mfuessel: /* Performance */

2007-06-27T09:46:52Z

Performance

← Older revision		Revision as of 09:46, 27 June 2007
Line 105:		Line 105:

	=== Performance ===		=== Performance ===
			In this system, every receiver has to decrypt ''every'' message in the system with ''one'' (his) private key. The work per receiver scales linearly with the number of receivers and linearly with the number of messages per receiver and maximal answer time of a sender. While this doesn't work well for large systems, it is considerably better than most of the comparable methods of receiver anonymity that have been suggested, which scale ''quadratically'' with the number of messages per receiver and maximal answer time of sender.

			More precisely, the authors point out that decryption takes about the same time as standard ElGamal decryption if the message is rejected (and not maliciously created), and roughly twice the time of standard ElGamal decryption if the message is indeed intended for the receiver. Encryption takes approximately the same time as standard ElGaml encryption.

	== Achievements & Shortcomings ==		== Achievements & Shortcomings ==

Mfuessel: /* Security */

2007-06-27T09:07:27Z

Security

← Older revision		Revision as of 09:07, 27 June 2007
Line 96:		Line 96:

	=== Security ===		=== Security ===
	A ''sender'' (or a group of conspiring senders) can aggregate information about a receiver as long as the receiver uses the same Incomparable Public Key. Their means of identification is, however, limited to a given public key: They ''cannot'' relate knowledge they have about a participant as long as it is spread over different Incomparable Public Keys of that participant. So the participant can choose the level of anonymity be choosing when to use a new Incomparable Public Key.		A ''sender'' (or a group of conspiring senders) can aggregate information about a receiver as long as the receiver uses the same Incomparable Public Key. Their means of identification is, however, limited to a given public key: They ''cannot'' relate knowledge they have about a participant as long as it is spread over different Incomparable Public Keys of that participant. So the participant can choose the level of anonymity by choosing when to use a new Incomparable Public Key.

			That is because nobody is able to determine whether two given public keys belong to the same private key or not. This holds even if the receiver can be tricked into responding to every correctly encrypted message (e.g. because it is an automatic system), thus indicating that the encryption has been correct. (This attack is the reason why the receiver has to make sure that only messages encrypted with a public key he has actually given away are accepted: If (and ''only'' if) two public keys correspond to the same private key, you can combine them to get a third (new!) public key corresponding to the very same private key. So without that precaution, given the receiver inadvertently acknowledges the correctness of keys, this would be a reliable test to find out whether two public keys are related.

	An ''eavesdropper'' cannot determine if two messages are intended for the same receiver even if they are encrypted with the same Incomparable Public Key. He even cannot relate messages encrypted with the same public key if he knows the message's plain text (for instance, if the messages are automatically generated standard messages), because they will be encrypted using a different symmetric key ''K''. Of course, he cannot relate messages for the same participant encrypted with ''different'' Incomparable Public Keys.		An ''eavesdropper'' cannot determine if two messages are intended for the same receiver even if they are encrypted with the same Incomparable Public Key. He even cannot relate messages encrypted with the same public key if he knows the message's plain text (for instance, if the messages are automatically generated standard messages), because they will be encrypted using a different symmetric key ''K''. Of course, he cannot relate messages for the same participant encrypted with ''different'' Incomparable Public Keys.

			In the paper, the authors point out that Incomparable Public Keys meets Key-Privacy as defined by Bellare et al. (this is only a very small extension, since Bellare et al. already showed that ElGamal meets Key-Privacy). They also show in the [http://en.wikipedia.org/wiki/Random_oracle_model Random Oracle model] that determining whether two public keys correspond to the same private key is as hard as the [http://en.wikipedia.org/wiki/Diffie-Hellman_problem Decisional Diffie-Hellman problem], which is assumed to be hard. Finally, they outline an Incomparable Public Key scheme using ''two'' key pairs, that can proven to be hard even without using the Random Oracle Model.

	=== Performance ===		=== Performance ===